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

第 1 页 共 41 页算法设计与分析(第 2 版)-王红梅- 胡明-习题答案习题 11. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler，17071783）提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，图 1.7 是这条河以及河上的两个岛和七座桥的草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。七桥问题属于一笔画问题。输入：一个起点输出：相同的点1， 一次步行2， 经过七座桥，且每次只经历过一次3， 回到起点该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。2在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法1.r=m-n2.循环直到 r=02.1 m=n2.2 n=r2.3 r=m-n3 输出 m 3设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和 C+描述。/采用分治法/对数组先进行快速排序/在依次比较相邻的差图 1.7 七桥问题北区东区岛区南区第 2 页 共 41 页#include using namespace std;int partions(int b,int low,int high)int prvotkey=blow;b0=blow;while (low=prvotkey)-high;blow=bhigh;while (lowusing namespace std;int main()int a=1,2,3,6,4,9,0;int mid_value=0;/将“既不是最大也不是最小的元素”的值赋值给它for(int i=0;i!=4;+i)if(ai+1aicoutusing namespace std;int main()double value=0;for(int n=1;nusing namespace std;int main ()double a,b;double arctan(double x);/声明a = 16.0*arctan(1/5.0);b = 4.0*arctan(1/239);cout 1e-15)/定义精度范围 f = e/i;/f 是每次 r 需要叠加的方程r = (i%4=1)?r+f:r-f; e = e*sqr;/e 每次乘于 x 的平方 i+=2;/i 每次加 2 /whilereturn r;7. 圣经上说：神 6 天创造天地万有，第 7 日安歇。为什么是 6 天呢？任何一个自然数的因数中都有 1 和它本身，所有小于它本身的因数称为这个数的真因数，如果一个自然数的真因数之和等于它本身，这个自然数称为完美数。例如，6=1+2+3，因此 6 是完美数。神6 天创造世界，暗示着该创造是完美的。设计算法，判断给定的自然数是否是完美数#includeusing namespace std;int main()int value, k=1;cinvalue;for (int i = 2;i!=value;+i)while (value % i = 0 ) k+=i;/k 为该自然数所有因子之和value = value/ i;/forif(k=value)cout1)return 3*T(n-1);(2)int T(int n) if(n=1)return 1;else if(n1)return 2*T(n/3)+n;（1 ） for (i = 1; i using namespace std;int main()long double result=1;double j=1;for(int i=1;iusing namespace std;int BF(char S, char T)int index = 0; int i = 0, j = 0; while (Si != 0) j+; else +index; i = index; j = 0; if (Tj = 0) return index + 1; else 第 10 页 共 41 页return 0;int main()char s119=“ababcabccabccacbab“;char s27=“abccac“;coutusing namespace std;void GetNext(char T , int next ) /求模式 T 的 next 值int i, j, len;next0 = -1;for (j = 1; Tj!=0; j+) /依次求 nextjfor (len = j - 1; len = 1; len-) /相等子串的最大长度为 j-1for (i = 0; i len; i+) /依次比较 T0Tlen-1与 Tj-lenTj-1if (Ti != Tj-len+i) break; if (i = len) nextj = len; break;/forif (len 1) nextj = 0; /其他情况，无相等子串/forint KMP(char S , char T