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

算法设计与分析(第2版)-王红梅-胡明- 习题答案 习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉 （Leonhard Euler，17071783）提出并解决了该问题。七桥 问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯 堡（现在叫加里宁格勒，在波罗的海南岸）城中全部的七座 桥后回到起点，且每座桥只经过一次，图1.7是这条河以及 河上的两个岛和七座桥的草图。请将该问题的数据模型抽象 出来，并判断此问题是否有解。 图1.7 七桥问题 北区 东区 岛区 南区 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行 2， 经过七座桥，且每次只经历过一次 3， 回到起点 该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶 点。另一类是只有二个奇点的图形。 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+描述。 /采用分治法 /对数组先进行快速排序 /在依次比较相邻的差 #include using namespace 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; for(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天呢？ 任何一个自然数的因数中都有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) 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; 5. 求下列问题的平凡下界，并指出其下界是否紧密。 （1）求数组中的最大元素； （2）判断邻接矩阵表示的无向图是不是完全图； （3）确定数组中的元素是否都是惟一的； （4）生成一个具有n个元素集合的所有子集 (1) (n) 紧密？ (2) (n*n) (3) (logn+n)（先进行快排，然后进行比较查找） (4) (2n) 7画出在三个数a, b, c中求中值问题的判定树。 a 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 = index; j = 0; if (Tj = 0) return index + 1; else 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; len-) /相等子串的最大长度为j-1 for (i = 0; i using namespace std; int main() int n;/分子 int m;/分母 int factor;/最大公因子 int factor1; coutnm; int r = m % n;/因为是真分数 所以分母一定大于分子 factor1=m; factor=n; while (r != 0) factor1 =factor; factor = r; r = factor1% factor; cout using namespace std; int main() int a9=5,6,2,8,4,3,7,4,8; int result=0; /result为题目要求的各位之和 for(int i=0;i!=9;+i) if(i%2=0) result+=ai; /i 为偶数位时，结果加上其对应数组数的本身 else result+=ai*10; /i 为奇数位时，结果加上对应数组数的10倍 if(result%11=0) cout using namespace std; int square(int x) return x*x; /用递归思想 int resultmod(int a, int n) if(n= 0) return 1; if(n%2 = 0) return square(resultmod(a, n/2);/n为偶数的时，取n的一半防止溢 出 else return a*resultmod(a, n-1);/n为奇数时，取n-1； int main() int a, n, m; coutanm; cout 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 using namespace std; int main() int a=1,2,1,5,3,2,9,4,5,5,3,5; int i,j; for( i=0;i using namespace std; int partions(int l,int low,int high) int prvotkey=llow; l0=llow; while (low=prvotkey) -high; llow=lhigh; while (low using namespace std; const int N = 20; void swap_ab ( int *p , int *q ) int tmp = *p; *p = *q; *q = tmp; void process ( int a, int n ) int *p, *q; p = q = a; while ( p != a+n-1 ) /p向前遍历，直到便利完毕 if ( *(p+1) using namespace std; int main() int x,y,x0,y0; int summax=0,temp=0; for(x0=0;x0=summax) summax=temp; x=x0;/符合sum最大值的x y=y0;/符合sum最大值得y /for cout0的元素进行判断 1.1 循环变量i从1n重复进行下述操作： 1.1.1计算矩阵i次方，如果矩阵对角线上有0的元素，则跳转到1.2 1.1.2否则+i; 1.2 如果矩阵对角线有0的元素，则输出该回路 2 输出无解信息； 13找词游戏。要求游戏者从一张填满字符的正方形表中，找出包含 在一个给定集合中的所有单词。这些词在正方形表中可以横着读、竖 着读、或者斜着读。为这个游戏设计一个蛮力算法 14. 变位词。给定两个单词，判断这两个单词是否是变位词。如果 两个单词的字母完全相同，只是位置有所不同，则这两个单词称为变 位词。例如，eat和tea是变位词。 /判断qwer和rewq是否是变位词 #include #include using namespace std; int main() char s5=“qwer“; char t5=“rewq“; for(int i=0;i!=4;+i) if(si!=t3-i) cout using namespace std; extern const int n=6;/声明 int main() int an=0,6,1,2,3,5;/初始化 int mid=n; int num_max1=0,num_max2=0; for(int i=0;inum_max1) num_max1=ai; for(int j=n+1;jnum_max2) num_max2=aj; if(num_max1=num_max2) cout using namespace std; void LeftReverse(char *a, int begin, int end) for(int i=0;i using namespace std; int data100; /在m个数中输出n个排列数（n using namespace std; void Findnum(int *a,int n) int low=0; int high=n-1; while(lowmid) high=mid-1; else low=mid+1; int main() int a7=1,0,2,5,6,7,9; Findnum(a,7); return 0; 时间复杂度为O(log2n)。 10. 在一个序列中出现次数最多的元素称为众数。请设计算法寻找 众数并分析算法的时间复杂性。 /先对序列进行快速排序 /再进行一次遍历 /输出众数的重复次数 #include using namespace std; int partions(int b,int low,int high) int prvotkey=blow; b0=blow; while (low=prvotkey) -high; blow=bhigh; while (lowmax) max=count; count=0; /while cout using namespace std; const int n=8; void partions(int a,int low,int high) /进行一趟快排 int prvotkey=alow; a0=alow; while (low=prvotkey) +low; ahigh=alow; alow=prvotkey; /如果s1（大的数集）的的个数大于n/2 if(low=n/2) for(int i=0;iak-1) int temp1=ak; ak=ak-1; ak-1=temp1; /for int main() int an=1,3,5,9,6,0,-11,-8; partions(a,0,n-1); for(int i=0;iaj，则 序偶(ai, aj)称为该排列的一个逆序。例如，2, 3, 1有两个逆序：(3, 1)和 (2, 1)。设计算法统计给定排列中含有逆序的个数。 /用归并进行排序 /当一个子集的一个数大于第二个子集的一个数，为逆序，即aiaj /则逆序数为end-j+1; #include using namespace std; int count; void Merge(int a,int a1,int begin,int mid,int end)/合并子序列 int i=begin,j=mid+1,k=end; while(i using namespace std; int n; char a100; void gelei(int k) if(k=n) coutn /初始化，全部置零 an =0; gelei(0); cout rmid) low = mid; else return mid; return 0; 错误。 正确算法： int BinSearch1(int r , int n, int k) int low = 0, high = n - 1; int mid; while (low rmid) low = mid + 1; else return mid; return 0; 2. 请写出折半查找的递归算法，并分析时间性能。 /折半查找的递归实现 #include using namespace std; int digui_search(int a,int low,int high,int x) if (low high) return 0; int mid = (low+high)/2; if (amid = x) return mid; else if (amid using namespace std; /折半进行范围查找函数： void digui_search(int min, int max, int a, int low, int high) int mid; mid=(low+high)/2; if(amidmax) digui_search(min, max, a, low, mid); else for(int i=mid; ai=min i-) coutri; coutminmax; digui_search(min, max, r, 0, 5); cout using namespace std; int main (void) int a,b; int i=1; cinab; while(i%a!=0)|(i%b!=0) +i; cout rj) /根结点已经大于左右孩子中的较大者 break; else temp = ri; ri = rj; rj = temp; /将被筛结点与结点j交换 i = j; j = 2 * i + 1; /被筛结点位于原来结点j的位置 进行调堆！ 6. 设计算法实现在大根堆中删除一个元素，要求算法的时间复杂 性为O(log2n)。 /将要删除的ak与最后一个元素an-1交换 /然后进行调堆 void de_SiftHeap(int r , int k, int n) int i, j, temp,temp1; i = k; j = 2 * i + 1; if(in-1) return error; else if(i=n-1) free(ai); else /置i为要筛的结点，j为i的左孩子 while (j rj) /根结点已经大于左右孩子中的较大者 break; else temp = ri; ri = rj; rj = temp; /将被筛结点与结点j交换 i = j; j = 2 * i + 1; /被筛结点位于原来结点j的位置 7. 计算两个正整数n和m的乘积有一个很有名的算法称为俄式乘 法，其思想是利用了一个规模是n的解和一个规模是n/2的解之间的关 系：nmn/22m（当n是偶数）或：nm(n-1)/22mm（当n是奇 数），并以1mm作为算法结束的条件。例如，图5.15给出了利用俄 式乘法计算5065的例子。据说十九世纪的俄国农夫使用该算法并因此 得名，这个算法也使得乘法的硬件实现速度非常快，因为只使用移位 就可以完成二进制数的折半和加倍。请设计算法实现俄式乘法。 n m 50 65 25 130 130 12 260 6 520 3 1040 1040 1 2080 2080 3250 图5.15 俄式乘法 + /俄式乘法 #include using namespace std; int fun(int m,int n) int sum=0; int temp=n; while(m!=1) if(m%2=0)/如果n是偶数 n=n*2; m=m/2; else/如果n是奇数 n=n*2; sum+=temp; m=(m-1)/2; temp=n;/记录倒数第二个n的值 return sum+n; int m