《算法设计与分析习题答案1-6章》由会员分享，可在线阅读，更多相关《算法设计与分析习题答案1-6章（26页珍藏版）》请在金锄头文库上搜索。
1、习题 11. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler，17071783）提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，图 1.7 是这条河以及河上的两个岛和七座桥的草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。七桥问题属于一笔画问题。输入：一个起点输出：相同的点1， 一次步行2， 经过七座桥，且每次只经历过一次3， 回到起点该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。2在欧几里德提出的欧
2、几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法1.r=m-n2.循环直到 r=02.1 m=n2.2 n=r2.3 r=m-n3 输出 m 3设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和 C+描述。/采用分治法/对数组先进行快速排序/在依次比较相邻的差#include using namespace std;int partions(int b,int low,int high)图 1.7 七桥问题北区东区岛区南区int prvotkey=blow;b0=blow;while (low=prvotkey)-high
3、;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+1ai&ai+1ai+2) mid_value=ai+1;coutusing namespace std;int main()double value=0;for(int n=1;nusing namespace std;int main ()double a,b;double arctan(double x);/声明a =
4、 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 天创造世界，
5、暗示着该创造是完美的。设计算法，判断给定的自然数是否是完美数#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)coutusing namespace std;extern const int n=6;/声明int main()int an=0,6,1,2,3,5;/初始化int mid=n/2;int num_max1=0
6、,num_max2=0;for(int i=0;inum_max1)num_max1=ai;for(int j=n/2+1;jnum_max2)num_max2=aj;if(num_max1=num_max2)coutusing namespace std;void LeftReverse(char *a, int begin, int end)for(int i=0;iusing namespace std;int data100;/在 m 个数中输出 n 个排列数（nusing namespace std;void Findnum(int *a,int n)int low=0;int hi
7、gh=n-1;while(lowmid)high=mid-1;elselow=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)-
8、high;blow=bhigh;while (lowmax) max=count;count=0;/whilecoutusing 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/2if(low=n/2)for(int i=0;iak-1)int temp1=ak;ak=ak-1;ak-1=temp1;/fo
9、rint main()int an=1,3,5,9,6,0,-11,-8;partions(a,0,n-1);for(int i=0;iaj，则序偶(a i, aj)称为该排列的一个逆序。例如，2, 3, 1 有两个逆序：(3, 1)和(2, 1)。设计算法统计给定排列中含有逆序的个数。/用归并进行排序/当一个子集的一个数大于第二个子集的一个数，为逆序，即 aiaj/则逆序数为 end-j+1;#includeusing namespace std;int count;void Merge(int a,int a1,int begin,int mid,int end)/合并子序列int i=b
10、egin,j=mid+1,k=end;while(iusing namespace std;int n;char a100;void gelei(int k)if(k=n)coutn & n != 0)memset(a,0,sizeof(a); /初始化，全部置零 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 =
11、mid + 1; else return mid; return 0; 2. 请写出折半查找的递归算法，并分析时间性能。/折半查找的递归实现#includeusing 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
12、 a, int low, int high)int mid;mid=(low+high)/2; if(amidmax)digui_search(min, max, a, low, mid);elsefor(int i=mid; ai=min & i=low; i-)coutri;coutminmax;digui_search(min, max, r, 0, 5);coutusing namespace std;int main (void)int a,b;int i=1;cinab;while(i%a!=0)|(i%b!=0)+i; cout rj) /根结点已经大于左右孩子中的较大者brea
13、k; 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 /
14、置 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 是偶数）或：n m( n-1)/22mm （当 n 是奇数） ，并以1mm 作为算法结束的条件。例如，图 5.15 给出了利用俄式乘法计算 5065 的例子。据说十九世纪的俄国农夫使用该算法并因此得名，这个算法也使得乘法的硬件实现速度非常快，因为只使用移位就可以完成二进制数的折半和加倍。请设计算法实现俄式乘法。/俄式乘法#includeusing 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;n
