1、 第 1 页 共 41 页 算法设计与分析 (第 2 版 )-王红梅 -胡明 -习题答案 习题 1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（ Leonhard Euler， 1707 1783）提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越 哥尼斯堡 （现在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，图 1.7 是这条河以及河上的两个岛和七座桥的草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行 2， 经过七座 桥，且每次只经历过一次 3，
2、回到起点 该问题无解： 能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2在欧几里德提出的欧几里德算法中（即 最初的欧几里德算法 ）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n 2.循环直到 r=0 2.1 m=n 2.2 n=r 2.3 r=m-n 3 输出 m 3设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和 C+描述。 /采用分治法 /对数组先进行快速排序 /在依次比较 相邻的差 图 1.7 七桥问题 北区 东区 岛区 南区 第 2 页 共 41 页 #include using namespace
3、 std; int partions(int b,int low,int high) int prvotkey=blow; b0=blow; while (low=prvotkey) -high; blow=bhigh; while (low using 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+1ai cout using namespace std; int main() double value=0; f
4、or(int n=1;n using 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 /while return r; 7. 圣经上说：神 6 天创造天地万有，第 7 日安歇。为什么是 6 天呢？任何一个自然数的因
5、数中都有 1 和它本身，所有小于它本身的因数称为这个数的真因数，如果一个自然数的真因数之和等于它本身，这个自然数称为完美数。例如， 6=1+2+3，因此 6 是完美数。神 6天创造世界，暗示着该创造是完美的。设计算法，判断给定的自然数是否是完美数 #include using 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; /for if(k=value) cou
6、t1) 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;i using namespace std; int BF(char S, char T) int index = 0; int i = 0, j = 0; while (Si != 0) j+; else +index; i =
7、index; j = 0; if (Tj = 0) return index + 1; else 第 10 页 共 41 页 return 0; int main() char s119=“ababcabccabccacbab“; char s27=“abccac“; cout using namespace std; void GetNext(char T , int next ) /求模式 T 的 next 值 int i, j, len; next0 = -1; for (j = 1; Tj!=0; j+) /依次求 nextj for (len = j - 1; len = 1; le
8、n-) /相等子串的最大长度为 j-1 for (i = 0; i len; i+) /依次比较 T0Tlen-1与 Tj-lenTj-1 if (Ti != Tj-len+i) break; if (i = len) nextj = len; break; /for if (len 1) nextj = 0; /其他情况，无相等子串 /for int KMP(char S , char T ) /求 T 在 S 中的序号 int i = 0, j = 0; int next80; /假定模式最长为 80 个字符 GetNext(T, next); while (Si != 0 & Tj != 0) if (Si = Tj)
