证明: F(s)的一切添加s的有限子集于F所得子域的并集`F是一个域。
第1题
问题描述;设S是正整数集合.S是一个无和集,当且仅当蕴含.对于任意正整数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.
第4题
设采用实现如教材48页代码2.21所示的二分查找binSearch()算法版本A,针对独立均匀分布于[0,2n]内的整数目标,在固定的有序向量(1,3,5,...,2n-1)中查找。
a)若将平均的成功和失败查找长度分别记作S和F,试证明:(S+1)•n=F•(n+1);
b)上述结论,是否适用于binSearch()算法的其它版本?为什么?
c)上述结论,是否适用于fibSearch()算法的各个版本?为什么?
d)若待查找的整数按照其它的随机规律分布,以上结论又应如何调整?
第6题
设< S, ≤>是模格,a,b∈S,作X={x|x∈S,且a*b ≤x ≤a},Y={y|y∈s.且,证明下面的f,g
是X和Y之间的两个同构。
第9题
问题描述:子集和问题的一个实例为.其中,是一个正整数的集合,c是一个正整数.子集和问题判定是否存在S的一个子集S1,使得.试设计一个解子集和问题的回溯法.
算法设计:对于给定的正整数的集合和正整数c,计算S的一个了集S1,使得
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和c,n表示S的大小,c是子集和的目标值.接下来的1行中,有n个正整数,表示集合S中的元素.
结果输出:将子集和问题的解输出到文件output.txt.当问题无解时,输出“NoSolution!".
第10题
第11题
证明存在而且有限的充分必要条件是:对于任意正无穷大量{xn},相应的函数值数列{f(xn)}收敛.