算法设计与分析习题答案6章.docx
- 文档编号:9632686
- 上传时间:2023-05-20
- 格式:DOCX
- 页数:19
- 大小:123.17KB
算法设计与分析习题答案6章.docx
《算法设计与分析习题答案6章.docx》由会员分享,可在线阅读,更多相关《算法设计与分析习题答案6章.docx(19页珍藏版)》请在冰点文库上搜索。
算法设计与分析习题答案6章
习题1
(LeonhardEuler,1707—1783)
1.图论诞生于七桥问题。
出生于瑞士的伟大数学家欧拉
提出并解决了该问题。
七桥问题是这样描述的:
一个人是否能在一次步行中穿越哥尼斯堡(现在叫加里宁格勒,在波罗的海南岸)城中全部的七座桥后回到起点,且每座桥只经过一次,图是这条河以及河上的两个岛和七座桥的草图。
请将该问题的数据模型抽象出来,并判断此问题是否有解。
七桥问题属于一笔画问题。
输入:
一个起点
输出:
相同的点
1,一次步行
2,经过七座桥,且每次只经历过一次
3,回到起点
该问题无解:
能一笔画的图形只有两类:
一类是所有的点都是偶点。
另一类是只有二个奇点的图形。
2•在欧几里德提出的欧几里德算法中(即最初的欧几里德算法)用的不是除法而是减
法。
请用伪代码描述这个版本的欧几里德算法
=m-n
2.循环直到r=0
m=n
n=r
r=m-n
3输出m
3•设计算法求数组中相差最小的两个元素(称为最接近数)的差。
要求分别给出伪代码和C++描述。
编写程序,求n至少为多大时,n个"1”组成的整数能被2013整除。
#include
intmain()
{
doublevalue=0;
for(intn=1;n<=10000;++n)
{value=value*10+1;
if(value%2013==0)
{
cout<<"n至少为:
"< } }计算n值的问题能精确求解吗编写程序,求解满足给定精度要求的n值 #include intmain() { doublea,b; doublearctan(doublex);圣经上说: 神6天创造天地万有,第7日安歇。 为什么是6天呢任何一个自然数的因数中都有1和它本身,所有小于它本身的因数称为这个数的真因数,如果一个自然数的真因数之和等于它本身,这个自然数称为完美数。 例如,6=1+2+3, 因此6是完美数。 神6天创造世界,暗示着该创造是完美的。 设计算法,判断给定的自然数是否是完美数 #include intmain() { intvalue,k=1; cin>>value; for(inti=2;i! =value;++i) { while(value%i==0) { k+=i;有4个人打算过桥,这个桥每次最多只能有两个人同时通过。 他们都在桥的某一端,并且是在晚上,过桥需要一只手电筒,而他们只有一只手电筒。 这就意味着两个人过桥后必须有一个人将手电筒带回来。 每个人走路的速度是不同的: 甲过桥要用1分钟,乙过桥要用2分钟,丙过桥要用5分钟,丁过桥要用10分钟,显然,两个人走路的速度等于其中较慢那个人的速度,问题是他们全部过桥最少要用多长时间由于甲过桥时间最短,那么每次传递手电的工作应有甲完成 甲每次分别带着乙丙丁过桥 例如: 第一趟: 甲,乙过桥且甲回来 第二趟: 甲,丙过桥且甲回来 第一趟: 甲,丁过桥一共用时19小时 9•欧几里德游戏: 开始的时候,白板上有两个不相等的正整数,两个玩家交替行动,每次行动时,当前玩家都必须在白板上写出任意两个已经出现在板上的数字的差,而且这个数字必须是新的,也就是说,和白板上的任何一个已有的数字都不相同,当一方再也写不出新数字时,他就输了。 请问,你是选择先行动还是后行动为什么 设最初两个数较大的为a,较小的为b,两个数的最大公约数为factor。 则最终能出现的数包括: factor,factor*2,factor*3,…,factor*(a/factor)=a.—共 a/factor个。 如果a/factor是奇数,就选择先行动;否则就后行动。 习题2 1.如果Ti(n)=Qf(n)),T2(n)=Qg(n)),解答下列问题: (1)证明加法定理: 「(n)+T2(n)=max{Qf(n)),Qg(n))}; (2)证明乘法定理: T1(n)xT2(n)=Qf(n))xQg(n)); (3)举例说明在什么情况下应用加法定理和乘法定理 | (1) (2) (3)比如在 for(f(n)) { for(g(n)) } 中应该用乘法定理 如果在“讲两个数组合并成一个数组时”,应当用加法定理 2•考虑下面的算法,回答下列问题: 算法完成什么功能算法的基本语句是什么基本语句 (1) for(i=1;i <=n;i++) (2) m=0; if(2*i<=n) for(i= 1;i<=n;i++) for(j: =2*i;j<=n; for(j= =1;j<=2*i; j++) j++) 3.分析以下程序段中基本语句的执行次数是多少,要求列出计算公式。 (1)基本语句2*i 基本语句y=y+i*j执行了2/n次一共执行次数=n/2+n/2=O(n) (2)基本语句m+=1执行了(n/2)*n=0(n*n) 4.使用扩展递归技术求解下列递推关系式: (1)intT(intn) { if(n==1) return4; elseif(n>1)return3*T(n-1);} ⑵ intT(intn) { if(n==1) return1; elseif(n>1)return2*T(n/3)+n;} 5.求下列问题的平凡下界,并指出其下界是否紧密。 (1)求数组中的最大元素; (2)判断邻接矩阵表示的无向图是不是完全图; (3)确定数组中的元素是否都是惟一的; (4)生成一个具有n个元素集合的所有子集 ⑶Q(logn+n)(先进行快排,然后进行比较查找) ⑷Q(2An) &国际象棋是很久以前由一个印度人Shashi发明的,当他把该发明献给国王时,国 王很高兴,就许诺可以给这个发明人任何他想要的奖赏。 Shashi要求以这种方式给他一些 粮食: 棋盘的第1个方格内只放1粒麦粒,第2格2粒,第3格4粒,第4格8粒,••…以此类推,直到64个方格全部放满。 这个奖赏的最终结果会是什么样呢 #include intmain() { longdoubleresult=1;doublej=1; for(inti=1;i<=64;++i){j=j*2;result+=j; j++; }cout< return0; 习题3 1.假设在文本"ababcabccabccacbab"中查找模式"abccac",写出分别采用BF算法和KMP 算法的串匹配过 式化简。 设计算法,将一个给定的真分数化简为最简分数形式。 例如,将6/8化简为3/4。 #include usingnamespacestd; intmain() { intn;数字游戏。 把数字1,2,…,9这9个数字填入以下含有加、减、乘、除的四则运算式中,使得该等式成立。 要求9个数字均出现一次且仅出现一次,且数字1不能出现 在乘和除的一位数中(即排除运算式中一位数为1的平凡情形)。 x+--=0 5.设计算法求解anmodm其中a、n和m均为大于1的整数。 (提示: 为了避免an超出int型的表示范围,应该每做一次乘法之后对n取模) #include intsquare(intx) { returnx*x; 设计算法,在数组r[n]中删除所有元素值为x的元素,要求时间复杂性为O(n),空间复杂性为O (1)。 7.设计算法,在数组r[n]中删除重复的元素,要求移动元素的次数较少并使剩余元素间的相对次序保持不变。 #include voiddeletere(inta[],intN) { intb[100]={0}; inti,k; k=0; staticintj=0; for(i=0;i b[a[i]]++; for(i=0;i<100;i++) { if(b[i]! =0) { if(b[i]==2) {k++; } a[j]=i;j++; } } for(i=0;i }intmain() { inta[]={1,2,1,3,2,4};deletere(a,6); return0; } 设表A={ai,a2,…,an},将A拆成B和C两个表,使A中值大于等于0的元素存入表 B,值小于0的元素存入表C要求表B和C不另外设置存储空间而利用表A的空间。 荷兰国旗问题。 要求重新排列一个由字符R,VVB(R代表红色,W代表白色,B代表兰色,这都是荷兰国旗的颜色)构成的数组,使得所有的R都排在最前面,W排在其次,B 排在最后。 为荷兰国旗问题设计一个算法,其时间性能是O(n)。 设最近对问题以k维空间的形式出现,k维空间的两个点pi=(xi,X2,…,Xk)和p2=(yi, y2,…,yk)的欧几里德距离定义为: k d(Pi,P2)(yi-xj2。 对k维空间的最近对问题设 'Vi111 计蛮力算法,并分析其时间性能。 (1)x+yw4; (2) 11•设计蛮力算法求解小规模的线性规划问题。 假设约束条件为: x+3y<6;(3)x>0且y》0;使目标函数3x+5y取得极大值。 #include usingnamespacestd; intmain() { intx,y,x0,y0; intsummax=0,temp=0; for(x0=0;x0<=4;++x0) { for(y0=0;(x0+y0<=4)&&(x0+3*y0<=6);++y0) temp=3*x0+5*y0; if(temp>=summax) {summax=temp; x=x0;变位词。 给定两个单词,判断这两个单词是否是变位词。 如果两个单 词的字母完全相同,只是位置有所不同,则这两个单词称为变位词。 例如,eat和tea是变 位词。 分治法的时间性能与直接计算最小问题的时间、合并子问题解的时间以及子问题的个数有关,试说明这几个参数与分治法时间复杂性之间的关系。 2.证明: 如果分治法的合并可以在线性时间内完成,则当子问题的规模之和小于原问题的规模时,算法的时间复杂性可达到C(n)。 O(N)=2*O(N/2)+x O(N)+x=2*O(N/2)+2*x a*O(N)+x=a*(2*O(N/2)+x)+x=2*a*O(N/2)+(a+1)*x由此可知,时间复杂度可达到O(n); 3.分治策略一定导致递归吗如果是,请解释原因。 如果不是,给出一个不包含递归的分治例子,并阐述这种分治和包含递归的分治的主要不同。 不一定导致递归。 如非递归的二叉树中序遍历。 这种分治方法与递归的二叉树中序遍历主要区别是: 应用了栈这个数据结构。 4.对于待排序序列(5,3,1,9),分别画出归并排序和快速排序的递归运行轨迹。 归并排序: 第一趟: (5,3)(1,9); 第二趟: (3,5,1,9); 第三趟: (1,3,5,9);快速排序: 第一趟: 5(,3,1,9);设计分治算法求一个数组中的最大元素,并分析时间性能。 设计分治算法,实现将数组A[n]中所有元素循环左移k个位置,要求时间复杂性为 O(n),空间复杂性为O (1)。 例如,对abcdefgh循环左移3位得到defghabc。 设计递归算法生成n个元素的所有排列对象。 #include usingnamespacestd; intdata[100]; 设计分治算法求解一维空间上n个点的最近对问题。 参见最近对问题的算法分析及算法实现 9.在有序序列(ri,「2,…,rn)中,存在序号i(1 请设计一个分治算法找到这个元素,要求算法在最坏情况下的时间性能为O(log2n)。 在一个序列中出现次数最多的元素称为众数。 请设计算法寻找众数并分析算法的时间复杂性。 设M是一个nxn的整数矩阵,其中每一行(从左到右)和每一列(从上到下)的元素都按升序排列。 设计分治算法确定一个给定的整数x是否在M中,并分析算法的时间复 杂性。 12.设S是n(n为偶数)个不等的正整数的集合,要求将集合S划分为子集Si和虫 使得ISi|=|S2|=n/2,且两个子集元素之和的差达到最大。 设ai,比,…,an是集合{1,2,…,n}的一个排列,如果i 称为该排列的一个逆序。 例如,2,3,1有两个逆序: (3,1)和(2,1)。 设计算法统计给定排列中含有逆序的个数。 循环赛日程安排问题。 设有n=2k个选手要进行网球循环赛,要求设计一个满足以下要求 的比赛日程表: (1)每个选手必须与其他n-1个选手各赛一次; (2)每个选手一天只能赛一次。 采用分治方法。 将2Ak选手分为2Ak-1两组,采用递归方法,继续进行分组,直到只剩下2个选手时,然 后进行比赛,回溯就可以指定比赛日程表了 15.格雷码是一个长度为2n的序列,序列中无相同元素,且每个元素都是长度为n的 二进制位串,相邻元素恰好只有1位不同。 例如长度为23的格雷码为(000,001,011,010,110,111,101,100)。 设计分治算法对任意的n值构造相应的格雷码。 矩阵乘法。 两个nxn的矩阵X和Y的乘积得到另外一个nxn的矩阵Z,且Zj 3 满足(1 可以用分 治法解决矩阵乘法问题,将矩阵X和Y都划分成四个n/2xn/2的子块,从而X和Y的乘积 可以用这些子块进行表达,即 从而得到分治算法: 先递归地计算8个规模为n/2的矩阵乘积AE、BG、AF、BH、CE、DG、 CFDH然后再花费Qn2)的时间完成加法运算即可。 请设计分治算法实现矩阵乘法,并分析时间性能。 能否再改进这个分治算法 习题5 1.下面这个折半查找算法正确吗如果正确,请给出算法的正确性证明,如果不正确,请说明产生错误的原因。 intBinSearch(intr[],intn,intk) { intlow=0,high=n-1; intmid; while(low<=high) { mid=(low+high)/2; if(k elseif(k>r[mid])low=mid; elsereturnmid; } return0; } 错误。 正确算法: intBinSearch1(intr[],intn,intk) { intlow=0,high=n-1; intmid; while(low<=high) { mid=(low+high)/2; if(k elseif(k>r[mid])low=mid+1; elsereturnmid; } return0; } 2.请写出折半查找的递归算法,并分析时间性能。 求两个正整数m和n的最小公倍数。 (提示: m和n的最小公倍数lcm(mn)与m和n的最大公约数gcd(mn)之间有如下关系: lcm(mn)=mxn/gcd(mn)) 插入法调整堆。 已知(ki,k2,…,kn)是堆,设计算法将(ki,k2,…,kn,kn+1)调 整为堆(假设调整为大根堆)。 参照: voidSiftHeap(intr[],intk,intn) { 设计算法实现在大根堆中删除一个元 inti,j,temp; i=k;j=2*i+1; 素,要求算法的时间复杂性为Olog2n)。 50 65 25 130 130 12 260 6 520 3 1040 1040 1 2080 2080 nm 3250 图俄式乘法 计算两个正整数n和m的乘积有一个很有名的算法称 为俄式乘法,其思想是利用了一个规模是n的解和一个规 模是n/2的解之间的关系: nxm=n/2x2m(当n是偶数)或: nxm=(n-1)/2x2m^m(当n是奇数),并以1xm=m作为算法结束的条件。 例如,图给出了利用俄式乘法计算50x65的例子。 据说十九世纪的俄国农夫使用该算法并因此得名,这个算法也使得乘法的硬件实现速度非常快,因为只使用移位就可以完成二进制数的折半和加倍。 请设计算法实现俄式乘法。 拿子游戏。 考虑下面这个游戏: 桌子上有一堆火柴,游戏开始时共有n根火柴,两个 玩家轮流拿走1,2,3或4根火柴,拿走最后一根火柴的玩家为获胜方。 请为先走的玩家设计一个制胜的策略(如果该策略存在)。 如果桌上有小于4根的火柴,先手必胜,如果是5根,先手必输;依次类推,同理15、 20、25…….都是必输状态;所有每次把对手逼到15、20、25…….等必输状态,就可以获 胜。 9.竞赛树是一棵完全二叉树,它反映了一系列“淘汰赛”的结果: 叶子代表参加比赛的n个选手,每个内部结点代表由该结点的孩子结点所代表的选手中的胜者,显然,树的根结点就代表了淘汰赛的冠军。 请回答下列问题: (1)这一系列的淘汰赛中比赛的总场数是多少 (2)设计一个高效的算法,它能够利用比赛中产生的信息确定亚军。 (1)因为n人进行淘汰赛,要淘汰n-1人,所有要进行n-1场比赛。 (2) 10.在120枚外观相同的硬币中,有一枚是假币,并且已知假币与真币的重量不同,但不知道假币与真币相比较轻还是较重。 可以通过一架天平来任意比较两组硬币,最坏情况下,能不能只比较5次就检测出这枚假币 将120枚平均分为三组,记为: A,B,C;先将A,B比较,如果A,B重量不同(假如B比A 重),再将B与C比较,如果B,C相同,则A有假币;如果B,C不同,再将A,C比较,如果 A,C相同,则B有假币;如果A,C不同,贝UB有假币;如果A,B相同,则C有假币; 习题6 1.动态规划法为什么都需要填表如何设计表格的结构 在填写表格过程中,不仅可以使问题更加清晰,更重要的是可以确定问题的存储结构;设计表格,以自底向上的方式计算各个子问题的解并填表。 将该多段图分为四段; 首先求解初始子问题,可直接获得: d(0,1)=coi=5(0t1) d(0,2)=5=3(0t1) 再求解下一个阶段的子问题,有: d(0,3)=d(0,1)+C13=6(1t3) 最短路径为: 0t1t3t8t11T12 d(0,4)=min{d(0,1)+c14,d(0,2)+c24}=8(1t4) 0000000 。 (以此类推) 3•用动态规划法求如下0/1背包问题的最优解: 有5个物品,其重量分别为(3,2,1, 4,5),价值分别为(25,20,15,40,50),背包容量为6。 写出求解过程。 (x1,x2,x3,x4,x5)t(1,1,1,0,0)(过程略) 4.用动态规划法求两个字符串A="xzyzzyx"和B="zxyyzxz"的最长公共子序列。 写出 求解过程。 略 5.给定模式"grammer"和文本"grameer",写出动态规划法求解K-近似匹配的过程。 略 6.对于最优二叉查找树的动态规划算法,设计一个线性时间算法,从二维表R中生成 最优二叉查找树。 7.Ackermann函数A(m,n)的递归定义如下: n1m0 A(m,n)A(m1,1)m0,n0 A(m1,A(m,n1))m0,n0 设计动态规划算法计算A(m,n),要求算法的空间复杂性为O(m)。 考虑下面的货币兑付问题: 在面值为(Vi,V2,…,Vn)的n种货币中,需要支付y值的 nn货币,应如何支付才能使货币支付的张数最少,即满足xiViy,且使xi最小(xi是 i1i1 非负整数)。 设计动态规划算法求解货币兑付问题,并分析时间性能和空间性能。 #include #defineN100000 #defineM20 inta[N][M]; intValue[M]; usingnamespacestd; intmain() { while(true) { inti,j,k; intx,y,z; cout<<"输入货币种类的个数: "< cin>>x; cout<<"从小到大输入货币的价值,其中第一个必须为一: "< for(i=1;i<=x;i++)多边形游戏。 多边形游戏是一个单人玩的游戏,开始时有一 个由n个顶点构成的多边形,每个顶点具有一个整数值,每条边具有一个运算符“+”或“X”。 游戏规则是每次选择一条边e以及和e相关联的两个顶点i和j,用一个新的顶点k取代边 e、顶点i和j,顶点k的整数值是顶点i和j的整数值通过边e上的运算符计算得到的结果。 当所有边都删除时,游戏结束,游戏的得分就是所剩顶点的整数值。 设计动态规划算法,对于给定的多边形计算最高得分。 (1)Q(n)紧密 (2)Q(n*n)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 分析 习题 答案
![提示](https://static.bingdoc.com/images/bang_tan.gif)