算法设计与分析习题答案1-6章

1、1.习题1图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉 提出并解决了该问题。七桥问题是这样描述的： 一个人是否能在一次步行中穿越哥尼斯堡（现 在叫加里宁格勒，在波罗的海南岸）城中全部 的七座桥后回到起点，且每座桥只经过一次， 图是这条河以及河上的两个岛和七座桥的草 图。请将该问题的数据模型抽象出来，并判断 此问题是否有解。(Leonhard Euler ,1707 1783)七桥问题属于一笔画问题。输入：一个起点输出：相同的点一次步行经过七座桥，且每次只经历过一次回到起点1，2，3，该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个 奇点的图形。2 .在欧几里德提出

2、的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法=m-n2.循环直到r=0m=nn=rr=m-n3输出m3 .设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代 码和C+描述。编写程序，求n至少为多大时，n个“ 1”组成的整数能被 2013整除。#in clude<iostream> using n ames pace std;int mai n()double value=0;for(int n=1;n<=10000 ;+n) value=value*10+1;if(value%2013=0)cout&

3、lt;<"n 至少为 :"<<n<<endl; break;计算n值的问题能精确求解吗？编写程序，求解满足给定精度要求的#include <iostream> using namespace std;int main ()double a,b;double arctan(double x); 圣经上说：神 6 天创造天地万有，第 7 日安歇。为什么是 6 天呢？任何一个自然数的因数中都有 1 和它本身，所有小于它本身的因数称为这个数的真 因数， 如果一个自然数的真因数之和等于它本身，这个自然数称为完美数。 例如， 6=1+2+3，因

4、此 6 是完美数。神 6 天创造世界，暗示着该创造是完美的。设计算法，判断给定的自然 数是否是完美数#include<iostream> using namespace std;int main()int value, k=1; cin>>value;for (int i = 2;i!=value;+i) while (value % i = 0 )k+=i; 有 4 个人打算过桥，这个桥每次最多只能有两个人同时通过。他们都 在桥的某一端，并且是在晚上，过桥需要一只手电筒，而他们只有一只手电筒。这就意味 着两个人过桥后必须有一个人将手电筒带回来。 每个人走路的速度是不同

5、的： 甲过桥要用 1 分钟，乙过桥要用 2 分钟，丙过桥要用 5 分钟，丁过桥要用 10 分钟，显然，两个人走路的 速度等于其中较慢那个人的速度，问题是他们全部过桥最少要用多长时间？ 由于甲过桥时间最短，那么每次传递手电的工作应有甲完成甲每次分别带着乙丙丁过桥例如：第一趟：甲，乙过桥且甲回来第二趟：甲，丙过桥且甲回来第一趟：甲，丁过桥一共用时 19 小时9欧几里德游戏：开始的时候，白板上有两个不相等的正整数，两个玩家交替行动， 每次行动时，当前玩家都必须在白板上写出任意两个已经出现在板上的数字的差，而且这 个数字必须是新的，也就是说，和白板上的任何一个已有的数字都不相同，当一方再也写 不出新数

6、字时，他就输了。请问，你是选择先行动还是后行动？为什么？factor 。设最初两个数较大的为a,较小的为b两个数的最大公约数为一共则最终能出现的数包括 : factor, factor*2, factor*3, ., factor*(a/factor)=a. a/factor 个。如果 a/factor 是奇数，就选择先行动；否则就后行动。习题 41. 分治法的时间性能与直接计算最小问题的时间、合并子问题解的时间以及子问题的个数有关，试说明这几个参数与分治法时间复杂性之间的关系2. 证明：如果分治法的合并可以在线性时间内完成，则当子问题的规模之和小于原问 题的规模时，算法的时间复杂性可达到O(

7、n)。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);3. 分治策略一定导致递归吗？如果是，请解释原因。如果不是，给出一个不包含递归的 分治例子，并阐述这种分治和包含递归的分治的主要不同。不一定导致递归。 如非递归的二叉树中序遍历。 这种分治方法与递归的二叉树中序遍历主要区别是：应用了栈这个数据结构。4. 对于待排序序列 (5, 3, 1, 9) ，分别画出归并排序和快速排序的递归运行轨迹。归并排序：第一趟：(5,3)(1,9 )；第二趟：(3,

8、5,1,9 )；第三趟：（1,3,5,9 ）；快速排序：第一趟： 5（ ,3,1,9 ）；设计分治算法求一个数组中的最大元素，并分析时间性能。设计分治算法，实现将数组A n中所有元素循环左移k个位置，要求时间复杂性为O（n） ，空间复杂性为 O（1） 。例如，对 abcdefgh 循环左移 3位得到 defghabc。设计递归算法生成 n 个元素的所有排列对象。 #include <iostream> using namespace std;int data100;设计分治算法求解一维空间上 n个点的最近对问题。参见 4.4.1 最近对问题的算法分析及算法实现9.在有序序列（ri,

9、2,rn）中，存在序号i （1 < i < n）,使得ri=i。请设计一个分 治算法找到这个元素，要求算法在最坏情况下的时间性能为O（log 2n）。在一个序列中出现次数最多的元素称为众数。请设计算法寻找众数并分析算法的时间 复杂性。设M是一个nxn的整数矩阵，其中每一行（从左到右）和每一列（从上到下）的元 素都按升序排列。设计分治算法确定一个给定的整数x是否在M中，并分析算法的时间复杂性。12.设S是n （n为偶数）个不等的正整数的集合，要求将集合S划分为子集 S和虫使得| S1|=| S2|= n/2 ，且两个子集元素之和的差达到最大。设 a1,称为该排列的一个逆序。例如， 排

10、列中含有逆序的个数。比，,an是集合1,2,n的一个排列，如果2, 3, 1 有两个逆序： （3, 1）i <j 且 ai >aj ，则序偶 （ai, aj） 和（2, 1） 。设计算法统计给定循环赛日程安排问题。设有的比赛日程表：（1 ）每个选手必须与其他n-1（2）每个选手一天只能赛一次。kn=2个选手要进行网球循环赛,要求设计一个满足以下要求个选手各赛一次；采用分治方法。采用递归方法，继续进行分组，直到只剩下 2 个选手时，然将2你选手分为2你-1两组，后进行比赛，回溯就可以指定比赛日程表了15.格雷码是一个长度为2n的序列，序列中无相同元素，且每个元素都是长度为n的二进制位

11、串，相邻元素恰好只有 1 位不同。例如长度为 23的格雷码为 （000, 001, 011, 010,110, 111, 101, 100) 。设计分治算法对任意的 n 值构造相应的格雷码。矩阵乘法。两个 nx n的矩阵X和Y的乘积得到另外一个nx n的矩阵Z,且Zj满足(1 w i , j w n),这个公式给出了运行时间为O n3)的算法。可以用分的子块，从而X和Y的乘积治法解决矩阵乘法问题，将矩阵X和Y都划分成四个n/2 x n/2可以用这些子块进行表达，即AE、BG、AF、BH、CE、DG、从而得到分治算法：先递归地计算 8 个规模为 n/2 的矩阵乘积CF DH然后再花费 qn2)的

12、时间完成加法运算即可。请设计分治算法实现矩阵乘法，并分 析时间性能。能否再改进这个分治算法？习题 51. 下面这个折半查找算法正确吗？如果正确，请给出算法的正确性证明，如果不正确，请 说明产生错误的原因。int BinSearch(int r , int n, int k)int low = 0, high = n - 1;int mid;while (low <= high)mid = (low + high) / 2;if (k < rmid) high = mid;else if (k > rmid) low = mid; else return mid;return

13、0;错误。正确算法：int BinSearch1(int r , int n, int k)int low = 0, high = n - 1;int mid;while (low <= high)mid = (low + high) / 2;if (k < rmid) high = mid - 1 ; else if (k > rmid) low = mid + 1 ;return 0;2. 请写出折半查找的递归算法，并分析时间性能。求两个正整数 m和n的最小公倍数。(提示：m和n的最小公倍数lcm( m n)与m和n 的最大公约数 gcd(m n)之间有如下关系：lcm(

14、 m n)=mx n/gcd( m n)插入法调整堆。已知(k1 ,k2,kn)是堆，设计算法将(k1,k2,kn,kn+1 )调整为堆(假设调整为大根堆)。参照：void SiftHea p(i nt r , i nt k, i nt n)设计算法实现在大根堆中删除一个元int i, j, temp;i = k; j = 2 * i + 1;素，要求算法的时间复杂性为qiog 2n)。5065251301301226065203104010401208020603250俄式乘法图n m计算两个正整数n和m的乘积有一个很有名的算法称 为俄式乘法，其思想是利用了一个规模是n的解和一个规模是n/2

15、的解之间的关系：nx m= n/2 x 2m (当n是偶数) 或：nx m= (n-1)/2 x 2m m (当 n 是奇数)，并以 1 x m= m 作为算法结束的条件。例如，图给出了利用俄式乘法计算 50x 65的例子。据说十九世纪的俄国农夫使用该算法并因 此得名，这个算法也使得乘法的硬件实现速度非常快，因 为只使用移位就可以完成二进制数的折半和加倍。请设计 算法实现俄式乘法。n根火柴，两个拿子游戏。考虑下面这个游戏：桌子上有一堆火柴，游戏开始时共有玩家轮流拿走1, 2, 3或4根火柴，拿走最后一根火柴的玩家为获胜方。请为先走的玩家 设计一个制胜的策略(如果该策略存在)。如果桌上有小于4根

16、的火柴，先手必胜，如果是5根，先手必输；依次类推，同理15、20、25胜。15、20、25.都是必输状态；所有每次把对手逼到15、20、25.等必输状态，就可以获9.竞赛树是一棵完全二叉树，它反映了一系列“淘汰赛”的结果：叶子代表参加比赛 的n个选手，每个内部结点代表由该结点的孩子结点所代表的选手中的胜者，显然，树的 根结点就代表了淘汰赛的冠军。请回答下列问题：(1) 这一系列的淘汰赛中比赛的总场数是多少？(2) 设计一个高效的算法，它能够利用比赛中产生的信息确定亚军10.在120枚外观相同的硬币中，有一枚是假币，并且已知假币与真币的重量不同, 但不知道假币与真币相比较轻还是较重。可以通过一架

17、天平来任意比较两组硬币，最坏情 况下，能不能只比较 5次就检测出这枚假币？将120枚平均分为三组，记为: 重),再将B与C比较，如果 A,C相同，则B有假币；如果A, B, C;先将A,B比较，如果A,B重量不同(假如 B比A B, C相同，则A有假币；如果B,C不同，再将A,C比较，如果 A,C不同，贝y B有假币；如果 A,B相同，则C有假币；习题61.动态规划法为什么都需要填表？如何设计表格的结构?在填写表格过程中，不仅可以使问题更加清晰，更重要的是可以确定问题的存储结构; 设计表格，以自底向上的方式计算各个子问题的解并填表。2.对于图所示多段图，用动态规划法求从顶点 程。0到顶点12的

18、最短路径，写出求解过第2题图图将该多段图分为四段；首先求解初始子问题，可直接获得：d(0, 1)= C01= 5(0 71)d(0, 2)= Co2= 3(0 71)再求解下一个阶段的子问题，有： d(0,3)=d(0, 1)+ C13 =6(1 7 3)C24=8(1 7 4)d(0,4)=mi nd(0,1)+C14 ,d(0,2)+。(以此类推)最短路径为：07 17 37 87 11 7 125个物品，其重量分别为(3, 2, 1,，背包容量为6。写出求解过程。3. 用动态规划法求如下0/1背包问题的最优解：有4,5)，价值分别为(25, 20, 15, 40, 50)(x1, x2,

19、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) 的递归定义如下：n1A(m,n) A(m 1,1)A(m 1, A(m,n1)0,n 00,n 0设计动态规划算法计算 A(m n)，要求算法的空间复杂性为O(m。考虑下面的货币兑付冋题：在面值为(vi, V2,vn)的n种货币中，需要支付 y值的货币，应如何支付才能使货币支付的张数最少，即满足nnxivi y ，且使 xi 最小( xi 是i1 i 1非负整数)。设计动态规划算法求解货币兑付问题，并分析时间性能和空间性能。#include<iostream> #define N 100000 #define M 20int aNM;int