请输入或粘贴题目内容
搜题
拍照、语音搜题，请扫码下载APP
题目内容
（请给出正确答案）
若有两位候选人参选，并争夺n·51个选举人团(50个州和1个特区)的共计2m=538张选举人票，是否可能因两人恰好各得m=269张，而不得不重新选举？
a)试设计并实现一个对应的算法，并分析其时间复杂度;
b)若没有其它(诸如限定整数取值范围等)附加条件，该问题可否在多项式时间内求解？
答案
更多“考查如下问题：设s为一组共n个正整数，其总和为2m，判断是否可将s划分为两个不相交的子集，且各自”相关的问题
第1题
0-1背包问题描述如下;给定n种物品和一个背包.物品i的重量是wi,其价值为vi背包的容量为C.应如何选择装入背包的物品,使装入背包中物品的总价值最大？
在选择装入肯包的物品时,对每种物品i只有2种选择,即装入背包或不装入背包.不能将物品i装入背包多次,也不能只装入部分的物品i.
0-1背包问题形式化描述如下:给定
,要求n元0-1向量
,
使得
而且
达到最大.
算法设计:对于给定的n种物品的重量和价值,以及背包的容量,计算可装入背包的最大价值.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和c,n是物品数,c是背包的容量.接下来的1行中有n个正整数,表示物品的价值.第3行中有n个正整数,表示物品的重量.
结果输出:将计算的装入背包物品的最大价值和最优装入方案输出到文件output.txt
第2题
问题描述:子集和问题的一个实例为
.其中,
是一个正整数的集合,c是一个正整数.子集和问题判定是否存在S的一个子集S1,使得
.试设计一个解子集和问题的回溯法.
算法设计:对于给定的正整数的集合
和正整数c,计算S的一个了集S1,使得
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和c,n表示S的大小,c是子集和的目标值.接下来的1行中,有n个正整数,表示集合S中的元素.
结果输出:将子集和问题的解输出到文件output.txt.当问题无解时,输出“NoSolution!".
第3题
问题描述:给定一个N×N的交通方形网格,设其左上角为起点◎,坐标为(1,1),X轴向右为正,Y轴向下为正,每个方格边长为1,汽车加油行驶问题的交通方形网格如图8-2所示.一辆汽车从起点◎出发驶向右下角终点▲,其坐标为(N,N).在着干个网格交叉点处,设置了油库,可供汽车在行驶途中加油.汽车在行驶过程中应遵守如下规则:
①汽车只能沿网格边行驶,装满油后能行驶K条网格边.出发时汽车已装满油,任起点与终点处不设油库.
②汽车经过一条网格边时,若其X坐标或Y坐标减小,则应付费用B,否则免付费用.
③汽车在行驶过程中遇油库,应加满油并付加油费用A.
④在需要时用在网格点处增设油库,并付增设油库费用C(不含加油费用A).
⑤①~④中的各数N、K、A、B、C均为正整数,且满足约束:2≤N≤100,2≤K≤10.
设计一个算法,求出汽车从起点出发到达终点的一条所付费用最少的行驶路线.
算法设计:对于给定的交通网格,计算汽车从起点出发到达终点的一条所付费用最少的行驶路线.
数据输入:由文件input.txt提供输入数据.文件的第1行是N、K、A、BC的值.第2行起是一个N×N的0-1方阵,每行N个值,至N+1行结束.方阵的第i行第j列处的值为1表示在网格交叉点(,j)处设置了一个油库,为0时表示未设油库.各行相邻两个数以空格分隔.结果输出:将最小费用输出到文件output.txt.
第4题
问题描述:设
是n个互不相同的符号组成的符号集.
1≤i≤k}是Σ中字符组成的长度为k的字符串至体.
是Lk的1个无分隔符字典是指对任意
和
.
无分隔符字典问题要求对给定的n和Σ及正整数k,计算Lk的最大无分隔符字典.
算法设计:设计一个算法,对于给定的正整数n和k,计算Lk的最大无分隔符字典.
数据输入:由文件input.txt给出输入数据.文件第1行有2个正整数n和k.
结果输出:将计算的Lk的最大无分隔符字典的元素个数输出到文件output.txt.
第5题
设x(n)是一个M点(0≤n≤M-1)的有限长序列，其z变换为
令X(z)在单位圆上N个等间隔点上的抽样X(zk)为
这里M和N都是较大的正整数，问如何用CZT算法快速算出全部N点X(zk)值来。
第6题
规则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上.
第7题
考查任意阶的B-树T。
a)若T的初始高度为1，而在经过连续的若干次插入操作之后，高度增加至h且共有n个内部节点，则在此过程中T总共分裂过多少次？
b)在如上过程中，每一关键码的插入，平均引发了多少次分裂操作？
c)若T的初始高度为h且含有n个内部节点，而在经过连续的若干次删除操作之后高度下降至1，则在此过程中T总共合并过多少次？
d)设T的初始高度为1，而且在随后经过若干次插入和删除操作——次序任意，且可能彼此相间。试证明：若在此期间总共做过S次分裂和M次合并，且最终共有n个内部节点，高度为h，则必有：S-M=n-h。
第8题
算法设计:对于给定的实直线上的n个点和闭区向的长度k,计算覆盖点集的最少区间数.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和k,表示有n个点,且固定长度闭区间的长度为k.接下来的1行中有n个整数,在示n个点在实直线上的坐标(可能相同).
结果输出;将计算的最少区间数输出到文件output,txt.
第9题
试设计一个算法,利用T公司提供的m个补丁程序,将原软件修复成一个没有错误的软件,并使修复后的软件耗时最少.
算法设计:对于给定的n个错误和m个补丁程序,找到总耗时最少的软件修复方案.
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和m,n表示错误总数,m表示补丁总数(1≤n≤20,1≤m≤100).接下来m行给出了m个补丁的信息.每行包括一个正整数,表示运行补丁程序i所需时间以及2个长度为n的字符串,中间用个空格符隔开.在第1个字符串中,如果第k个字符bk为“+”,则表示第k个错误属于B1[i],若为“-”,则表示第k个错误属于B2[i],若为“0”,则第k个错误既不属于B1[i]也不属于B2[i],即软件中是否包含第k个错误并不影响补丁i的可用性.在第2个字符串中,如果第k个字符bk为“+”,则表示第k个错误属于F1[i],若为“-”,则表示第k个错误属于F2[i],若为“0”,则第k个错误既不属于F1[i]也不属于F2[i],即软件中是否包含第k个错误不会因使用补丁i而改变.
结果输出:将总耗时数输出到文件output.txt.如果问题无解,则输出0.
第10题
问题描述:设磁盘上有n个文件
每个文件占用磁盘上的1个磁道.这n个文件的检索概率分别是
且
磁头从当前磁道移到被检信息磁道所需的时间可用这两个磁道之间的径向距离来度量.如果文件fi存放在第i(1≤i≤n)道上,则检索这n个文件的期望时间是
.式中,d(i,j)是第i道与第j道之间的径向距离|i-j|.
磁盘文件的最优存储问题要求确定这n个文件在磁盘上的存储位置,使期望检索时间达到最小.试设计一个解此问题的算法,并分析算法的正确性与计算复杂性.
算法设计:对于给定的文件检索概率,计算磁盘文件的最优存储方案.
数据输入:由文件input.txt给出输入数据.第1行是正整数n,表示文件个数.第2行有n个正整数a,表示文件的检索概率.实际上第k个文件的检索概率应为
结果输出:将计算的最小期望检索时间输出到文件output.txt.
