算法设计与分析(第2版)-王红梅-胡明-习题答案

1、算法设计与分析(第2版)-王红梅-胡明-习题答案生于瑞士的伟大数学家欧拉（Euler，了该问题。七桥问题是这样描述的：一个人加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，图是这条河以及河上的两个岛和七座桥的草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。七桥问题属于一笔画问题。输入：一个起点输出：相同的点，一次步行，经过七座桥，且每次只经历过一次，回到起点该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。最初的欧几里德算法用伪代码描述这个版本的欧几里德算法2.循环直到设计算法求数组中相差最小的两个元素C+描述。/采用

2、分治法/对数组先进行快速排序/在依次比较相邻的差#includeusingnamespacestd;intpartions(intb,intlow,inthigh)intprvotkey=blow;b0=blow;while(lowhigh)while(low=prvotkey)-high;blow=bhigh;while(lowhigh&blow=prvotkey)+low;bhigh=blow;blow=b0;returnlow;voidqsort(intl,intlow,inthigh)intprvotloc;if(lowhigh)prvotloc=partions(l,low,high

3、);/将第一次排序的结果作为枢轴qsort(l,low,prvotloc-1);/递归调用排序由low到prvotloc-1qsort(l,prvotloc+1,high);/递归调用排序由prvotloc+1到highvoidquicksort(intl,intn)qsort(l,1,n);/第一个作为枢轴，从第一个排到第n个intmain()inta11=0,2,32,43,23,45,36,57,14,27,39;intvaluefor(intb=1;b11;b+)coutab;coutendl;quicksort(a,11);for(inti=0;i!=9;+i)if(ai+1-ai)

4、=(ai+2-ai+1)value=ai+1-ai;elsevalue=ai+2-ai+1;coutvalueendl;return0;设数组中的元素均不相等，设计算法找出中一个既不是最大也不是最小的元出伪代码和C+描述。#includeusingnamespacestd;intmain()inta=1,2,3,6,4,9,0;intmid_value=0;/将“既不是最大也不是最小的元素”的值赋值给它for(inti=0;i!=4;+i)if(ai+1ai&ai+1ai+2)mid_value=ai+1;coutmid_valueendl;break;elseif(ai+1ai+2)mid_

5、value=ai+1;coutmid_valueendl;break;/forreturn0;编写程序，求至少为多大时，个“”组成的整数能被整除。至少为0;计算值的问题能精确求解吗？编写程序，求解满足给定精度要求的值声明=；定义四个变量初=x;定义精度范围=是每次需要叠加的方程=每次乘于的平方每次加r;圣经上说：神天创造天地万有，第日天呢？任何一个自然数的因数中都有等于它本身，这个自然数称为完美数。例如，6=1+2+3，因此是完美数。神天创造世界，自然数是否是完美数i=%i=为该自然数所有因子之和=i;该自然数是完美数该自然数不是完美数0;.有人将手电筒带回来。每个人走路的速度是不同的：甲过桥

6、要用分钟，乙过桥要用分钟，丙过桥要用分钟，丁过桥要用分钟，显然，两个人走路的速度等于其中较慢那个人的速度，问题是他们全部过桥最少要用多长时间？应有甲完成甲每次分别带着乙丙丁过桥例如：第一趟：甲，乙过桥且甲回来第二趟：甲，丙过桥且甲回来第一趟：甲，丁过桥一共用时小时欧几里德游戏：开始的时候，白板上有两么？设最初两个数较大的为a,较小的为b，两个数的最大公约数为factor。则最终能出现的数包括:factor,factor*2,factor*3,.,factor*(a/factor)=a.一共a/factor个。如果a/factor是奇数，就选择先行动；否则就后行动。如果T，Tg，解答下列问题：（

7、）证明加法定理：TT),g)；（）证明乘法定理：TTg；（乘法定理。,（）（）（）比如在（）中应该用乘法定理用加法定理（1（1）int（2）intQ(intn)执行了多次成什么功能？算法的基本语句是什么？基本语句Stery(int少n)？算法的时间复杂性是多少？if(n=1)intS=0;return（）完成的是的平方和基本语句：，执行了次时间复杂度（）（）（）完成的是的平方基本语句：-+*，执行了次时间复杂度（）分析以下程序段中基本语句的执行次数是多少，要求列出计算公式。（1）for(i=1;（2）m=0;i=n;i+)for(i=1;（）基本语句执行了次基本语句=+i*j执行了次一共执行次

8、数（）（）基本语句m+=1执行了使用扩展递归技术求解下列递推关系式：（）()(（）T(int4;T(int1;求下列问题的平凡下界，并指出其下界是否紧密。（）求数组中的最大元素；（）判断邻接矩阵表示的无向图是不是完全图；（）确定数组中的元素是否都是惟一的；（）生成一个具有n个元素集合的所有子集紧密？查找）画出在三个数,b,中求中值问题的判定树。abacabcacbacbccCabbcaCb=1;/相等子串的最大长度为(i=0;i/依次比较与(Ti(i=0;/其他情况，无相等子串KMP(char,T/求T在中的序号i=j=0;/假定模式最长为个字符Tj=Tj)j=(j=(Tj=(i/返回本趟匹配

9、的开始位置0;0;分式化简。设计算法，将一个给定的真分数化简为最简分数形式。例如，将化简为。分子分母最大公因子输入一个真分数的分子与分母：r=%n;/因为是真分数所以分母一定大于分子(r=r;r=输出该真分数的最简分数：0;设计算法，判断一个大整数能否被整除。端开始，每两位一组构成一个整数，然后将这些数相加，判断其和能否被整除。例如，将分割成，然后判断能否被整除/将一个大整数看成一个数组/数组的奇数位对应数的倍加上数组偶数对应数的本身/验证结果能否被整除为题目要求的各位之和为偶数位时，结果加上其对应数组数的本身为奇数位时，结果加上对应数组数的倍该整数能被整除该整数不能被整除0;数字游戏。把数字

10、这个数字填入以下含有加、减、乘、除的四则运算式中，个数字均出现一次且仅不能出现在乘和除的一位数中（即排除运算式中一位数为=（设计算法求解m，其中、和m（均为大于的整数。超出型的表示范围，应该每做一次乘法之后对取模）x*x;/用递归思想1;=为偶数的时，取的一半防止溢出；请输入，;=n);的结果为：%0;设计算法，在数组r中删除所有元素值为的元素，要求时间复杂性为，空间复杂性为。r中删除重复的元素，要求移动元素的次数较少并使剩余元素间的相对次序保持不变。i,k;0;/在数组查找相同的元素/把其中一个相同的数值的元素位置设成一个“特殊数值”/输出所求函数i,j;设一个数组不存在的数值;0;设表,，

11、将拆成B和两个表，使中值大于等于的元素存入表B，值小于的元素存入表，要求表B和不另外设置存储空间而利用表的空间。/先对A进行快排/将大于的元素给B，小于的元素给C/将第一次排序的结果作为枢轴/递归调用排序由到/递归调用排序由到/第一个作为枢轴，从第一个排到第个;0;荷兰国旗问题。要求重新排列一个由字符R,W,B（R代表红色，W代表白色，B代表兰色，这都是荷兰国旗的颜色）构成的数组，使得所有的R都排在最前面，W排在其次，B排性能是。/0代表红；代表白；代表蓝=,=*p;=*q;=*q;=a;/p向前遍历，直到便利完毕=);/q指针后移=2;/待处理的数组处理后的数组序列:);N;0的元素进行判断

12、循环变量i从重复进行下述操作：计算矩阵i次方，如果矩阵对角线上有0的元素，则跳转到否则如果矩阵对角线有0的元素，则输出该回路输出无解信息；词。这些词在正方形表中可以横着读、竖着读、或者斜着读。为这个游戏设计一个蛮力算法变位词。给定两个单词，判断这两个单词是否是变位词。如果两个单词的字母完全相词。例如，和是变位词。/判断和是否是变位词和不是变位词0;和是变位词0;在美国有一个连锁店叫店，因为这个商店以前是早晨点开门，晚上点关门。有一天，一个顾客在这个店挑“选了四样东西，然后到付款处去交钱。营“业员拿起计算器，按了一些键，然后说：“总共是“哦？难道因为你们的店名叫，所以我就要付呢？你应该把他们相加

13、才对！”营业员答一遍，将这四样东西的价格加在一起，然而，令他俩更为吃惊的是总和也是。设计蛮力算法找出这四样东西的价格各是多少？该算法为：0;0;分治法的时间性能与直接计算最小问题间的关系。证明：如果分治法的合并可以在线性时规模时，算法的时间复杂性可达到。O(N)=2*O(N/2)+xO(N)+x=2*O(N/2)+2*xa*O(N)+x=a*(2*O(N/2)+x)+x=2*a*O(N/2)+(a+1)*x由此可知，时间复杂度可达到O(n);分治策略一定导致递归吗？如果是，请解不同。不一定导致递归。如非递归的二叉树中序遍历。这种分治方法与递归的二叉树中序遍历主要区别是：应用了栈这个数据结构。对

14、于待排序序列排序和快速排序的递归运行轨迹。归并排序：）（）；）；）；快速排序：第一趟：（）；/5为哨兵，比较和第二趟：（）；/比较和，将挪到相应位置；第三趟：（）比较和；）;设计分治算法求一个数组中的最大元素，并分析时间性能。/简单的分治问题/分别求出这两部分最大值，然后再比较这两个最大值声明初始化前半部分后半部分数组中的最大元素：数组中的最大元素：0;时间复杂度：（）设计分治算法，实现将数组中所有元素循环左移个位置,要求时间复杂性为，空间复杂性为。例如，对循环左移位得到。/采用分治法/将数组分为0-k-1和k-n-1两块/将这两块分别左移/然后再合并左移#includeusingnamesp

15、acestd;voidLeftReverse(char*a,intbegin,intend)for(inti=0;i(end-begin+1)/2;i+)/交换移动inttemp=abegin+i;abegin+i=aend-i;aend-i=temp;voidConverse(char*a,intn,intk)LeftReverse(a,k+1);LeftReverse(a,n+1);LeftReverse(a,n-1);for(inti=0;in;i+)coutai;coutendl;intmain()chara7=a,b,c,d,e,f,g;Converse(a,7,3);return0

16、;设计递归算法生成n个元素的所有排列对象。/在个数中输出个排列数（n=m）;0;设计分治算法求解一维空间上个点的最近对问题。参见最近对问题的算法分析及算法实现在有序序列r,r,r中，存在序号i（i），使得ri=i。请设计一个分治算法找为。/在有序数组中/采用二分法查找符合条件的元素#includeusingnamespacestd;voidFindnum(int*a,intn)intlow=0;inthigh=n-1;while(low=high)intmid=(low+high)/2;if(amid=mid)cout这个数是：amidmid)high=mid-1;elselow=mid+1;

17、intmain()inta7=1,0,2,5,6,7,9;Findnum(a,7);return0;时间复杂度为。在一个序列中出现次数最多的元素称复杂性。/先对序列进行快速排序/再进行一次遍历/输出众数的重复次数#includeusingnamespacestd;intpartions(intb,intlow,inthigh)intprvotkey=blow;b0=blow;while(lowhigh)while(low=prvotkey)-high;blow=bhigh;while(lowhigh&blow=prvotkey)+low;bhigh=blow;blow=b0;returnlow

18、;voidqsort(intl,intlow,inthigh)intprvotloc;if(lowhigh)prvotloc=partions(l,low,high);/将第一次排序的结果作为枢轴qsort(l,low,prvotloc-1);/递归调用排序由low到prvotloc-1qsort(l,prvotloc+1,high);/递归调用排序由prvotloc+1到highvoidquicksort(intl,intn)qsort(l,1,n);/第一个作为枢轴，从第一个排到第n个intmain()inta10=1,2,3,5,3,3,3,2,5,1;inti=0;intcount=0

19、;intmax=0;/max表示出现的次数qsort(a,0,10);while(i10)intj;j=i+1;if(ai=aj&imax)max=count;count=0;/whilecout重复次数：maxendl;return0;时间复杂度nlog(n)设是一个的整数矩阵，其中每一行（从左到右）和每一列（从上到下）的元素数是否在中，并分析算法的时间复杂性。设是（为偶数）个不等的正整数的集合，要求将集合划分为子集和，使得，且两个子集元素之和的差达到最大。/先用快速排序进行一趟排序/如果（大的数集）的的个数大于/将（）个最小的数排到后面/如果（大的数集）的的个数小于/将（小的数集）排到前面

20、/将排好的数组的前个数赋值给/将排好的数组的后个数赋值给/进行一趟快排/如果（大的数集）的的个数大于/如果（大的数集）的的个数小于属于子集的：属于子集的：0;设,是集合,的一个排列，如果ij，则序偶i,j称为该排列的一个逆序。例如，有两个逆序：和个数。/用归并进行排序/当一个子集的一个数大于第二个子集的一个数，为逆序，即aiaj/则逆序数为end-j+1;#includeusingnamespacestd;intcount;voidMerge(inta,inta1,intbegin,intmid,intend)/合并子序列inti=begin,j=mid+1,k=end;while(i=mid

21、&j=end)if(ai=aj)a1k+=ai+;/取ai和aj中较小者放入r1kelsea1k+=aj+;count+=(end-j+1);while(i=mid)a1k+=ai+;while(j=end)a1k+=aj+;voidMergeSort(inta,intbegin,intend)intmid,a11000;if(begin=end)return;elsemid=(begin+end)/2;MergeSort(a,begin,mid);MergeSort(a,mid+1,end);Merge(a,a1,begin,mid,end);intmain()inta6=6,5,4,3,2

22、,1;count=0;MergeSort(a,0,6);coutcountendl;return0;循环赛日程安排问题。设有=2个选手的比赛日程表：（-个选手各赛一次；（）每个选手一天只能赛一次。采用分治方法。将选手分为两组，采用递归方法，进行比赛，回溯就可以指定比赛日程表了格雷码是一个长度为的二进制的格雷码为值构造相应的格雷码。/构造格雷码#includeusingnamespacestd;intn;chara100;voidgelei(intk)if(k=n)coutan&n!=0)memset(a,0,sizeof(a);/初始化，全部置零an=0;gelei(0);coutendl;r

23、eturn0;矩阵乘法。两个的矩阵X和Y的乘积得到另外一个的矩阵Z，且ij满足（i,j了运行时间为的算法。可以用分治法解决矩阵乘法问题，将矩阵X和Y都划分成四个的子块，从而X和Y的乘积可以用这些子块进行表达，即从而得到分治算法：先递归地计算个规模为的矩阵乘积AE、BG、AF、BH、CE、CF、，然后再花费的时间完成加法运时间性能。能否再改进这个分治算法？ij给出算法的正确性证明，如果不正确，请说明产生错误的原因。r,k)=-1;=+/2;(k=0;错误。正确算法：r,k)=-1;=+/2;(k=+1;0;请写出折半查找的递归算法，并分析时间性能。/折半查找的递归实现0;=0;谓范围查找是要找出

24、在给定值和b之间的所有元素（b）修改第二题算法并实现：/折半查找算法使之能够进行范围查找/折半进行范围查找函数：;请输入数组元素：请输入查找范围最小值和最大值：;r,5);（求两个正整数m和的最小公倍数。提（示：m和的最小公倍数m,与m和的最大公约数m,之间有如下关系：m,mm,）/求两个数的最小公倍数最小公倍数为：0;该算法比较直接，要使其改进，可用欧几里得公式再求最小公倍数插入法调整堆。已知（,）是堆，设计算法将（,+1）调整为堆参照：r,k,i,j,i=k;j=*i+1;/置i为要筛的结点，j为i的左孩子(j/筛选还没有进行到叶子(j-rjrj)/根结点已经大于左右孩子中的较大者=ri;

25、ri=rj;rj=/将被筛结点与结点j交换i=j;j=*i+1;/被筛结点位于原来结点j的位置进行调堆！设计算法实现在大根堆中删除一个元素，要求算法的时间复杂性为。/将要删除的与最后一个元素交换/然后进行调堆r,k,i,j,i=k;j=*i+1;error;/置i为要筛的结点，j为i的左孩子(j/筛选还没有进行到叶子/将与交换；(j-rjrj)/根结点已经大于左右孩子中的较大者=ri;ri=rj;rj=/将被筛结点与结点j交换i=j;j=*i+1;/被筛结点位于原来结点j的位置计算两个正整数和m的乘积有一个很有名的算法称为俄式乘法，其思想是利用了一个规模是的解和一个规模nm是的解之间的关系：mm（当是偶数）或：m-mm（当是mm如，图给出了利用俄式乘法计算的半和加倍。请设计算法实现俄式乘法。/俄式乘法如果是偶数如果是奇数记录倒数第二个的值拿子游戏。考虑下面这个游戏：桌子上n家轮流拿走，或根火柴，拿走最后一根如果桌上有小于根的火柴，先手必胜，如果是根，先手必输；依次类推，同理、25.都是必输状态；所有每次把对手逼到、25.等必输状态，就可以获胜。竞赛树是一棵完全二叉树，它反映了一系列“淘汰赛”的结果：叶子代表参加比赛的n表了淘汰赛的冠军。请回答下列问题：（）这一系列的淘汰赛中比赛的总场