设A[0,n)为一个非降的正整数向量。试设计并实现算法expSearch(int x),对于任意给定的正整数x≤A[n-1],从该向量中找出一个元素A[k],使得A[k]≤x≤A[min(n-1,k2)]。若有多个满足这一条件的k,只需返回其中任何一个,但查找时间不得超过o(log(logk))。
第2题
问题描述;设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.
第3题
若有两位候选人参选,并争夺n·51个选举人团(50个州和1个特区)的共计2m=538张选举人票,是否可能因两人恰好各得m=269张,而不得不重新选举?
a)试设计并实现一个对应的算法,并分析其时间复杂度;
b)若没有其它(诸如限定整数取值范围等)附加条件,该问题可否在多项式时间内求解?
第4题
在给定了空间直角坐标系的三维空间中,所有自原点引出的向量添上零向量构成一个三维线性空间R3。
1)问所有终点都在一个平面上的向量是否为子空间?
2)设有过原点的三条直线,这三条直线上的全部向量分别成为三个子空间L1,L2,L3。问L1+L2,L1+L2+L3能构成哪些类型的子空间,试全部列举出来。
3)试用几何空间的例子来说明:若U,V,X,Y是子空间,满足U+V=X,XY,是否一定有Y=Y∩U+Y∩V。
第5题
设V是对于非退化对称双线性函数f(α,β)的n维准欧氏空间,V的一组基ε1,...,εn如果满足
则称为V的一组正交基。如果V上的线性变换满足
则称为V的一个准正交变换。试证:
1)准正交变换是可逆的,且逆变换也是准正交变换;
2)准正交变换的乘积仍是准正交变换;
3)准正交变换的特征向量α,若满足f(α,α)≠0,则其特征值等于1或-1;
4)准正交变换在正交基下的矩阵T满足
第6题
设D是z平面上介于直线x-γ=0与x-y+π/)=0之间的带形域,试求把D映为w平面上的单位圆的一个共形映射.
第7题
问题描述:子集和问题的一个实例为.其中,是一个正整数的集合,c是一个正整数.子集和问题判定是否存在S的一个子集S1,使得.试设计一个解子集和问题的回溯法.
算法设计:对于给定的正整数的集合和正整数c,计算S的一个了集S1,使得
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和c,n表示S的大小,c是子集和的目标值.接下来的1行中,有n个正整数,表示集合S中的元素.
结果输出:将子集和问题的解输出到文件output.txt.当问题无解时,输出“NoSolution!".
第8题
第9题
设静电场中存在这样一个区域(附图虚线所围半扇形部分,扇形响应的圆心为0),域内的静电场线是以O点为心的同心圆弧(如图),试证区域内每点的场强都反比与该点与O的距离。
第10题
规则I:每次只能移动1个圆盘:
规则II:任何时刻都不允许将较大的圆盘压在较小的圆盘之上;
规则III:任何时刻都不允许将同色圆盘叠放在一起:
规则IV:在满足移动规则I~III的前提下,可将圆盘移至A、B、C中任一塔座上.
试设计一个算法,用最少的移动次数将塔座A上的n个圆盘移到塔座B上,并仍按同样顺序叠置.
算法设计:对于给定的正整数n,计算最优移动方案.
数据输入:由文件input.txt给出输入数据.第1行是给定的正整数no.
结果输出:将计算出的最优移动方案输出到文件output.txt.文件的每行由一个正整数k
和2个字符c1和c2组成,表示将第k个圆盘从塔座c1移到塔座c2上.
第11题
设f(x)在[0,1]上非负连续,且f(0)-f(1)=0.试证对于实数c(0<r<1),必存在一点使f(0)= f(x0+c).