《算法设计与分析(第2版)-王红梅-胡明-习题答案》由会员分享，可在线阅读，更多相关《算法设计与分析(第2版)-王红梅-胡明-习题答案（15页珍藏版）》请在金锄头文库上搜索。
1、习题11. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler, 17071783）提出并解决了该问题。七桥问题是这样描述的： 一个人是否能在一次步行中穿越哥尼斯堡（现 在叫加里宁格勒，在波罗的海南岸）城中全部 的七座桥后回到起点，且每座桥只经过一次， 图是这条河以及河上的两个岛和七座桥的草 图。请将该问题的数据模型抽象出来，并判断 此问题是否有解。七桥问题属于一笔画问题。输入：一个起点输出：相同的点1， 一次步行2，经过七座桥，且每次只经历过一次3，回到起点该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个 奇点的图形。2. 在欧几里德提出
2、的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减 法。请用伪代码描述这个版本的欧几里德算法=m-n2. 循环直到r=0m二nn=rr二m-n3输出m3. 设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代 码和C+描述。.编写程序，求n至少为多大时，n个“1”组成的整数能被2013整除。#includeusing namespace std；int main() double value=0；for(int n=1；n=10000 ；+n)value=value*10+1；if(value%2013=0)coutn 至少为:nendl;break;计算n值的问题
3、能精确求解吗编写程序，求解满足给定精度要求的n值#include using namespace std；int main ()double a,b；double arctan(double x)；圣经上说：神6天创造天地万有，第7日安歇。为什么是6 天呢任何一个自然数的因数中都有1和它本身，所有小于它本身的因数称为这个数的真因 数，如果一个自然数的真因数之和等于它本身，这个自然数称为完美数。例如，6=1+2+3, 因此6是完美数。神6天创造世界，暗示着该创造是完美的。设计算法，判断给定的自然 数是否是完美数#includeusing namespace std；int main()int v
4、alue, k=1；cinvalue；for (int i = 2；i!=value；+i)while (value % i = 0 )k+=i；有4个人打算过桥，这个桥每次最多只能有两个人同时通过。他们都 在桥的某一端，并且是在晚上，过桥需要一只手电筒，而他们只有一只手电筒。这就意味着两个人过桥后必须有一个人将手电筒带回来。每个人走路的速度是不同的：甲过桥要用1 分钟，乙过桥要用2分钟，丙过桥要用5分钟，丁过桥要用10分钟，显然，两个人走路的 速度等于其中较慢那个人的速度，问题是他们全部过桥最少要用多长时间由于甲过桥时间最短，那么每次传递手电的工作应有甲完成甲每次分别带着乙丙丁过桥例如：第一
5、趟：甲，乙过桥且甲回来第二趟：甲，丙过桥且甲回来 第一趟：甲，丁过桥一共用时19小时9.欧几里德游戏：开始的时候，白板上有两个不相等的正整数，两个玩家交替行动， 每次行动时，当前玩家都必须在白板上写出任意两个已经出现在板上的数字的差，而且这 个数字必须是新的，也就是说，和白板上的任何一个已有的数字都不相同，当一方再也写 不出新数字时，他就输了。请问，你是选择先行动还是后行动为什么设最初两个数较大的为a,较小的为b，两个数的最大公约数为factor。则最终能出现的数包括：factor, factor*2, factor*3, ., factor*(a/factor)=a. 一共 a/factor
6、 个。如果a/factor是奇数，就选择先行动；否则就后行动。习题2(1. 如果 Ti(n)=O(f (n)，T2(n)=O(g(n)，解答下列问题:(1) 证明加法定理：T(n)+T2(n)=maxO(f (n), O(g(n)；(2) 证明乘法定理：T：(n)XT：(n)=O(f (n)XO(g(n)；(3) 举例说明在什么情况下应用加法定理和乘法定理。(2) (3)比如在for (f(n)for(g(n)中应该用乘法定理如果在“讲两个数组合并成一个数组时”，应当用加法定理2. 考虑下面的算法，回答下列问题：算法完成什么功能算法的基本语句是什么基本语句执行了多少次算法的时间复杂性是多少(1
7、) int Stery(int n)int S = 0;for (int i = 1; i = n;S = S + i * i;完成rn是;1-n的平方和基本语句：s+=i*i，执行了 n次时间复杂度O (n)(2) (2)完成的是n的平方i+)(1)(2) int Q(int n)if (n = 1)return 1;elsereturn Q(nT) + 2 * n - 1;基本语句：return Q(nT) + 2 * n - 1,执行了 n次 时间复杂度O (n)3. 分析以下程序段中基本语句的执行次数是多少，要求列出计算公式。(1) for (i = 1; i = n; i+)(2)
8、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+)(1) 基本语句2*i 1(2) T(n)=1) return 3*T(nT); (2)int T(int n)if(n=1)return 1；else if(n1)return 2*T(n/3)+n；/5. 求下列问题的平凡下界，并指出其下界是否紧密。(1) 求数组中的最大元素；(2) 判断邻接矩阵表示的无向图是不是完全图；(3) 确定数组中的元素是否都是惟一的；(4) 生成一个具有n个元素集合的所有子集(1) Q(n)紧
9、密(2) (3) Q (n*n)(4) Q(logn+n)(先进行快排，然后进行比较查找)Q(2”n)7.画出在三个数a, b,c中求中值问题的判定树。8.国际象棋是很久以前由一个印度人Shashi发明的，当他把该发明献给国王时，国 王很高兴，就许诺可以给这个发明人任何他想要的奖赏。Shashi要求以这种方式给他一些 粮食：棋盘的第1个方格内只放1粒麦粒，第2格2粒，第3格4粒，第4格8粒， 以此类推，直到64个方格全部放满。这个奖赏的最终结果会是什么样呢#includeusing namespace std；int main()long double result=1；|double j=1
10、;for(int i=1;i=64;+i)j=j*2;result+=j;j+;coutresultendl;return 0;*习题31, 假设在文本ababcabccabccacbab中查找模式abccac,写出分别采用BF算法和KMP 算法的串匹配过式化简。设计算法，将一个给定的真分数化简为最简分数形式。例如，将6/8化简为3/4。#includeusing namespace std;int main() intn ；数字游戏。把数字1,2,“,9这9个数字填入以下含有加、减、乘、除的四则 运算式中，使得该等式成立。要求9个数字均出现一次且仅出现一次，且数字1不能出现 在乘和除的一位数
11、中(即排除运算式中一位数为1的平凡情形)。5.设计算法求解an mod m,其中a、n和m均为大于1的整数。(提示：为了避免& 超出int型的表示范围，应该每做一次乘法之后对取模)(#include using namespace std；*int square(int x)return x*x；设计算法，在数组rn中删除所有元素值为x的元素，要求时间复杂性为O(n)，空间 复杂性为0(1)。#7.设计算法，在数组rn中删除重复的元素，要求移动元素的次数较少并使剩余元素 间的相对次序保持不变。#include using namespace std；void deletere(int a,in
12、t N)(int b100 = 0；int i,k；k=0；static int j=0；for(i=0；iN；i+)bai+； for(i=0；i100；i+) (【if(bi!=0)if(bi=2)k+； aj=i； j+；for(i=0；iN-k；i+)coutaiendl；int main()*int a = 1,2,1,3,2,4； deletere(a,6)；return 0；设表A=aa2，aj,将A拆成B和C两个表，使A中值大于等于0的元素存入表 B,值小于0的元素存入表初 要求表B和C不另外设置存储空间而利用表A的空间。%荷兰国旗问题。要求重新排列一个由字符R, W, B （
13、R代表红色，W代表白色，B代表 兰色，这都是荷兰国旗的颜色）构成的数组，使得所有的R都排在最前面，W排在其次，B 排在最后。为荷兰国旗问题设计一个算法，其时间性能是O（n）。设最近对问题以k维空间的形式出现，k维空间的两个点pi=（xi，x2,，xk）和p2=（yi?Y2，尸的欧几里德距离定义为：d(p ,p ) = * (y-x )2。对k维空间的最近对问题设 12i ii=1计蛮力算法，并分析其时间性能。11. 设计蛮力算法求解小规模的线性规划问题。假设约束条件为：(1)x+yW4； (2) x+3yW6； (3)xN0且yN0；使目标函数3x+5y取得极大值。 #include using namespace std；int main() int x,y,x0,y0；!int summax=0,temp=0；for(x0=0；x0=4；+x0) for(y0=0；(x0+y0=4)&(x0+3*y0=summax) |summax=temp；x=x0；1.1.11.1.2变位词。给定两个单词，判断这两个单词是否是变
