题目内容
（请给出正确答案）
问题描述:子集和问题的一个实例为
.其中,
是一个正整数的集合,c是一个正整数.子集和问题判定是否存在S的一个子集S1,使得
.试设计一个解子集和问题的回溯法.
算法设计:对于给定的正整数的集合
和正整数c,计算S的一个了集S1,使得
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和c,n表示S的大小,c是子集和的目标值.接下来的1行中,有n个正整数,表示集合S中的元素.
结果输出:将子集和问题的解输出到文件output.txt.当问题无解时,输出“NoSolution!".
简答题官方参考答案
（由简答题聘请的专业题库老师提供的解答）
更多“问题描述:子集和问题的一个实例为.其中,是一个正整数的集合,c是一个正整数.子集和问题判定是否”相关的问题
蕴含.对于任意正整数k,如果可将{1.2,...,k}划分为n个无和子集
,则称正整数k是n可分的.记F(n)=max{k|k是n可分的}.试设计一个算法,对任意给定的n,计算F(n)的值.算法设计:对任意给定的n,计算F(n)的值.
数据输入:由文件input.txt给出输入数据.第I行有1个正整数n.
结果输出:将计算的F(n)的值以及{1,2,F(n)}的一个n划分输出到文件output.txt.文件的第1行是F(n)的值.接下来的n行,每行是一个无和子集Si.
假设由语句“x=rnd.Random(n)+1;"产生的整数x∈S的概率为r,证明算法GenRand返回的整数不在S中的概率最多为
其中,集合{{1,2,3,4)}由1个子集组成:集合{{1{,2},{3,4}},{{1,3},{2,4},{{1,4},{2,3}},{{1,2,3},{4}},{{1,2,4},{3}},{{1,3,4},{2}},{2,3,4},{1}}由2个子集组成:集合{{1,2},{3},{4}},({1,3},{2},{4},{{1,4},{2},{3}},{{2,3},{1},{4)},{{2.4},{1},{3}},{{3,4},{1},{2}}由3个子集组成:集合{{1},{2},{3},{4}}由4个子集组成.
算法设计;给定正整数n和m,计算出n个元素的集合{1,2,...,n}可以划分为多少个不同的由m个非空子集组成的集合.
数据输入:由文件input.txt提供输入数据.文件的第1行是元素个数n和非空子集数m.
结果输出:将计算出的不同的由m个非空子集组成的集合数输出到文件output.txt.
蕴含.对于任意正整数k,如果可将{1.2,...,k}划分为n个无和子集,则称正整数k是n可分的.记F(n)=max{k|k是n可分的}.试设计一个算法,对任意给定的n,计算F(n)的值.算法设计:对任意给定的n,计算F(n)的值.
数据输入:由文件input.txt给出输入数据.第I行有1个正整数n.
结果输出:将计算的F(n)的值以及{1,2,F(n)}的一个n划分输出到文件output.txt.文件的第1行是F(n)的值.接下来的n行,每行是一个无和子集Si.
一个关于logn的多项式时间算法.结合教材中素数测试的偏假蒙特卡罗算法,设计一个素数测试的拉斯维加斯算法.
算法设计:设计一个拉斯维加斯算法,对于给定的正整数,判定其是否为素数.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数p.
结果输出:将计算结果输出到文件output.txt.若正整数p是素数,则输出“YES",否则输出“NO".
警告：系统检测到您的账号存在安全风险
为了保护您的账号安全，请在“简答题”公众号进行验证，点击“官网服务”-“账号验证”后输入验证码“”完成验证，验证成功后方可继续查看答案！
都是集合,其中n为正整数.证明:
.
