算法设计与分析王红梅胡明习题答案

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&l

3、t;<"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、字时，他就输了。请问，你是选择先行动还是后行动？为什么？一共设最初两个数较大的为a,较小的为b两个数的最大公约数为factor。则最终能出现的数包括：factor, factor*2, factor*3,，factor*(a/factor)=a.a/factor 个。如果a/factor 是奇数，就选择先行动；否则就后行动。习题21.如果 Ti(n)=qf ( n) , T2(n)=qg(n)，解答下列问题： (1 )证明加法定理：Ti(n) + T2(n)=maxC(f ( n), C(g(n)；(2) 证明乘法定理：T1(n) XT2(n)=Cf ( n) x Cg(n);(3) 举例说明

7、在什么情况下应用加法定理和乘法定理(3)比如在for (f(n)for(g( n)中应该用乘法定理如果在“讲两个数组合并成一个数组时”，应当用加法定理2 考虑下面的算法，回答下列问题：算法完成什么功能？算法的基本语句是什么？基本 语句执行了多少次？算法的时间复杂性是多少？(2) int Q(int n)if (n = 1)return 1;elsereturn Q(n-1) + 2 * n - 1;(1) int Stery(int n) int S = 0;for (int i = 1; i <= n;i+)(1)完成的是* i1-n的平方和基本语句S; s+=i*i，执行了 n次时间

8、复杂度0(n)(2)完成的是n的平方-1，执行了 n次基本语句：return Q( n-1) + 2 * n时间复杂度0(n)3. 分析以下程序段中基本语句的执行次数是多少，要求列出计算公式。(1) for (i = 1; i <= n; i+)if (2*i <= n)for (j = 2*i; j <= n;(2) m = 0;for (i = 1; i <= n; i+) for (j = 1; j <= 2*i;<=j+)(1) 基本语句2*i<n执行了基本语句y = y + i * j 一共执行次数=n/2+n/2=0 (n)(2) 基本语句

9、 m+=1 执行了 (n/2)*n=0(n*n)4. 使用扩展递归技术求解下列递推关系式：n/2次执行了 2/n门)T(n)3T( n4n 11) n 1(2)T(n)1n 12T(n/3) n n 1(1) int T(i nt n)if(n=1)return 4;else if(n >1) return 3*T( n-1); int T(i nt n)if(n=1)return 1;else if(n >1) return 2*T( n/3)+n; 5.求下列问题的平凡下界,(1)(2)(3)(4)并指出其下界是否紧密。求数组中的最大元素；判断邻接矩阵表示的无向图是不是完全图;

10、 确定数组中的元素是否都是惟一的； 生成一个具有n个元素集合的所有子集Q (n) 紧密?Q (n*n)Q （logn+n）（先进行快排，然后进行比较查找）Q （2人n）发明的，当他把该发明献给国王时，国Shashi要求以这种方式给他一些&国际象棋是很久以前由一个印度人Shashi王很高兴，就许诺可以给这个发明人任何他想要的奖赏。 粮食：棋盘的第1个方格内只放1粒麦粒，第2格2粒，第3格4粒，第4格8粒, 以此类推，直到64个方格全部放满。这个奖赏的最终结果会是什么样呢？#in clude<iostream>using n ames pace std;int mai n()l

11、ong double result=1; double j=1;for(i nt i=1;i<=64;+i) j=j*2;result+=j;j+;cout<<result<<e ndl;return 0;1的平凡情形）。=05. 设计算法求解an mod m其中a、n和超出int型的表示范围，应该每做一次乘法之后对m均为大于1的整数。（提示：为了避免 an n取模）习题31.假设在文本"ababcabccabccacbab"中查找模式"abccac"，写出分别采用 BF算法和 KMP算法的串匹配过6/8化简为3/4 。式化

12、简。设计算法，将一个给定的真分数化简为最简分数形式。例如，将 #in clude<iostream> using n ames pace std;int mai n()intn;数字游戏。把数字1,2,9这9个数字填入以下含有加、减、乘、除的四则运算式中，使得该等式成立。要求9个数字均出现一次且仅出现一次，且数字 1不能出现在乘和除的一位数中（即排除运算式中一位数为X +-#in clude<iostream> using n ames pace std;int square(i nt x) return x*x;设计算法，在数组 r n中删除所有元素值为 x的元素，要

13、求时间复杂性为 Qn),空间 复杂性为 O(1) 。7. 设计算法，在数组 rn 中删除重复的元素，要求移动元素的次数较少并使剩余元素 间的相对次序保持不变。#include <iostream> using namespace std;void deletere(int a,int N)int b100=0;int i,k;k=0;static int j=0;for(i=0;i<N;i+) bai+;for(i=0;i<100;i+)if(bi!=0)if(bi=2)k+;aj=i; j+;for(i=0;i<N-k;i+)cout<<ai<

14、<endl;int main()int a=1,2,1,3,2,4; deletere(a,6); return 0;设表A=ai, a2,an，将A拆成B和C两个表，使A中值大于等于0的元素存入表B,值小于0的元素存入表 C要求表B和C不另外设置存储空间而利用表A的空间。荷兰国旗问题。要求重新排列一个由字符 RVVB( R代表红色，W代表白色，B代表 兰色，这都是荷兰国旗的颜色)构成的数组，使得所有的R都排在最前面， W排在其次，B排在最后。为荷兰国旗问题设计一个算法，其时间性能是qn)。设最近对问题以k维空间的形式出现，k维空间的两个点pi=(xi, X2,xk)和p2=(yi,ij

15、Ky2,yk)的欧几里德距离定义为：d(p 1, P2) I (yj-Xj)2。对k维空间的最近对问题设'Y i1''计蛮力算法，并分析其时间性能。(1) x+yw 4; (2)11.设计蛮力算法求解小规模的线性规划问题。假设约束条件为: x+3y w 6; (3) x> 0且y0;使目标函数3x+5y取得极大值。#in clude<iostream> using n ames pace std;int mai n()int x,y,x0,y0;int summax=0,te mp=0;for(x0=0;x0<=4;+x0)for(y0=0;(x

16、0+y0<=4)&&( x0+3*y0<=6);+y0)temp=3*x0+5*y0;if(te mp>=summax)summax=te mp;x=x0;1.1.11.1.2变位词。给定两个单词，判断这两个单词是否是变位词。如果两个单词的字母完全相同，只是位置有所不同，则这两个单词称为变位词。例如，eat和tea是变位词。分治法的时间性能与直接计算最小问题的时间、合并子问题解的时间以及子问题的个 数有关，试说明这几个参数与分治法时间复杂性之间的关系Qn)。2.证明：如果分治法的合并可以在线性时间内完成，则当子问题的规模之和小于原问 题的规模时，算法的时间复杂

17、性可达到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) ，分别画出归并排序和快速排序的递归运行轨迹。归并排序：第一趟：第二趟：第三趟： 快速排序：第一趟：

18、 55,3)(1,9 )；3,5,1,91,3,5,9)；)；,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,2,rn)中

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

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

21、只有 1 位不同。例如长度为 23的格雷码为 （000, 001, 011, 010, 110, 111, 101, 100） 。设计分治算法对任意的 n 值构造相应的格雷码。矩阵乘法。两个 nx n的矩阵X和Y的乘积得到另外一个nx n的矩阵Z,且Zj满足（1 < 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）的时间完成

22、加法运算即可。请设计分治算法实现矩阵乘法，并分 析时间性能。能否再改进这个分治算法？习题 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;<=retur

23、n 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 = else if (k > rmid) low = else return mid;mid - 1mid + 1 ;return 0;2. 请写出折半查找的递归算法，并分析时间性能。求两个正整数 m和n的最小公倍数。(提示：m和n的最小公倍数icm( m n)与m和n 的最大公约数 gcd(

24、m n)之间有如下关系：lcm( m n)=mx n/gcd( m n)插入法调整堆。已知(ki,k2,kn)是堆，设计算法将(ki,k2,kn,kn+1 )调整为堆(假设调整为大根堆) 。参照：void SiftHeap(int r , int k, int n)int i, j, temp;i = k; j = 2 * i + 1;设计算法实现在大根堆中删除一个元素，要求算法的时间复杂性为Qlog 2n）。计算两个正整数n和m的乘积有一个很有名的算法称 为俄式乘法，其思想是利用了一个规模是 模是n/2的解之间的关系：nx m= n/2 x 2m (当n是偶数) 或：nX m= (n-1)/

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

26、柴，两个20、25胜。如果桌上有小于4根的火柴，先手必胜，如果是5根，先手必输；依次类推，同理15、.都是必输状态；所有每次把对手逼到15、20、25.等必输状态，就可以获15、20、259.竞赛树是一棵完全二叉树，它反映了一系列“淘汰赛”的结果：叶子代表参加比赛 的n个选手，每个内部结点代表由该结点的孩子结点所代表的选手中的胜者，显然，树的 根结点就代表了淘汰赛的冠军。请回答下列问题：(1) 这一系列的淘汰赛中比赛的总场数是多少？(2) 设计一个高效的算法，它能够利用比赛中产生的信息确定亚军(1) 因为n人进行淘汰赛，要淘汰n-1人，所有要进行 n-1场比赛。(2)10.在120枚外观相同的

27、硬币中，有一枚是假币，并且已知假币与真币的重量不同, 但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，最坏情 况下，能不能只比较 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.动态规划法为什么都需要填表？如何设计表格的结构?在填写表格过程中，不仅可以使问题更加清晰，更重要的是可以确定问题的存储结构; 设计表格

28、，以自底向上的方式计算各个子问题的解并填表。2.对于图所示多段图，用动态规划法求从顶点 程。0到顶点12的最短路径，写出求解过将该多段图分为四段；首先求解初始子问题，可直接获得：d(0, 1)= C01= 5(0 71)d(0, 2)= C02= 3(0 71)再求解下一个阶段的子问题，有：d(0,3)= d(0, 1)+ C13 =6(1 7 3) d(0,4)=mi nd(0,1)+c 14 ,d(0,2)+。(以此类推)最短路径为：07 17 37 87 11 7 12c 24=8(1 7 4)3.用动态规划法求如下0/1背包问题的最优解：有4,5)，价值分别为(25, 20, 15, 40, 50)5个物品，其重量分别为(3, 2, 1,，背包容量为6。写出求解过程。(x1, x2,x3,x4,x5)(1,1,1,