算法设计与分析习题答案1

1、精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载算法设计与分析习题答案1习题11.图论诞生于七桥问题。出生于瑞士的伟 大数学家欧拉提出并解决了该问题。七 桥问题是这样描述的：北区一个人是否 能在一次步行中穿越哥尼斯堡城中全部 岛区 的七座桥后回到起点，且每座桥只 经过一次， 南区图是这条河以及河 上的两个岛和七座桥的 图七桥问 题 草图。请将该问题的数据模型抽 象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入： 一个起点 输出：相同的点 1, 一次步 行 2,经过七座桥，且每次只经历 过一次3,回到起点 该问题无解： 能一笔画的图形只有两类：一类是所有 的点都是偶点

2、。另一类是只有二个奇点 的图形。 2.在欧几里德提出的欧 几里德算法中用的不是除法而是减法。 请用伪代码描述这个版本的欧几里德算精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载 1 精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载法 =m-n2.循环宜到 r=0 m=n n=r r=m-n 3输出m 3.设计算 法求数组中相差最小的两个元素的差。要求分别给出伪代码和C+描述。采用分治法对数组先进行快速排序在依次比较相邻的差#includeusing namespace std;intpartions(int b,int low,int high)int prvotk

3、ey=blow;b0=blow; while (lowwhile(low=prvotkey)-high;blow=bhigh;while (lowbhigh=blow; blow=b0;return low; void qsort(int l,int low,int high) int prvotloc; if(low prvotloc=partions(l,low,high); 将 第一 次排序的结果作为枢轴 qsort(l,low,prvotloc-1); 递归调 用排序 low至 Uprvotloc-1qsort(l,prvotloc+1,high); 递归调用排序 prvotloc+1

4、 至U high voidquicksort(int l,int n) qsort(l,1,n); / 精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载 2 第一个作为枢轴，从第一个排到第n个 int main() inta11=0,2,32,43,23,45,36,57,14,27,39; int value=0;/将最小差的值赋值给 value for (int b=1;b quicksort(a,11); for(inti=0;i!=9;+i)if( (ai+1-ai)value=ai+2-ai+1;coutreturn 0; 4,设数组an中的元素均不相等，设计算法找出

5、an中一个 既不是最大也不是最小的元素，并说明 最坏情况下的比较次数。要求分别给出 伪代码和C+描述。#include usingnamespacestd; int main() int a=1,2,3,6,4,9,0;intmid_value=0;/将既不是最大也不是最 小的元素”的值赋值给它 for(int i=0;i!=4;+i)if(ai+1>ai&&ai+1ai+2)mid_value=ai+1; cout5.编写程序，泵n至少为多大时，n个“1 组成的整数能被2013整除。精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载 3 =精选公文范文，管理

6、类，工作总结类，工作计划类文档，欢迎阅读下载=#include using namespace std; int main() double value=0;for(int n=1;n return 0; 6.计算兀值的问题能精确求解吗？编写程序， 求解满足给定精度要求的冗值 #include using namespacestd;intmain () double a,b;doublearctan(double x);/声明 a = *arctan(1/); b = *arctan(1/239); coutreturn0 ; double arctan(double x) int i=0;

7、double r=0,e,f,sqr; 定义四个变量初sqr = x*x; e = x;while (e/i>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 和它本身，所有小于它本身的因数称为 这个数的真因数，如果一个自然数的真精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载 4 精选公文范文，管理类，工作总结类，工作

8、计划类文档，欢迎阅读下载因数之和等于它本身，这个自然数称为 完美数。例如，6=1+2+3,因此6是完美 数。神6天创造世界，暗示着该创造是 完美的。设计算法，判断给定的自然数 是否是完美数#include usingnamespace std;int main() int value, k=1; cin>>value;for (int i =2;i!=value;+i) while (value % i = 0 )k+=i;/k为该自然数所有因子之和 value = value/ i; /for 4个人打算过桥，这个桥每次最多只能有 两个人同时通过。他们都在桥的某一端, 并且是在晚

9、上，过桥需要一只手电筒, 而他们只有一只手电筒。这就意味着两 个人过桥后必须有一个人将手电筒带回if(k=value)cout cout来。每个人走路的速度是不同的：甲过 桥要用1分钟，乙过桥要用2分钟，丙 过桥要用5分钟，丁过桥要用10分钟， 显然，两个人走路的速度等于其中较慢 那个人的速度，问题是他们全部过桥最 精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载 5 =精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载=精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载=少要用多长时间？ if (Tj=0' ) return (- strlen(

10、T) +1);/返回本趟匹配的开始位置else return 0; int main() coutreturn 0;2.分式化简。设计算法，将一个给定的真分数化简为最简分数形式。例如，将6/8化简为3/4#include using namespace std; int main() int n;分子int m;/分母 int factor;/最大公因子intfactor1; cout>n>>m; int r = m % n;/因为是真分数 所以分母一定大 于分子 factor1=m; factor=n; while (r != 0)factor1 =factor;facto

11、r = r; r = factor1% factor; cout 3,设计算法，判断一个大整数 能否被11整除。可以通过以下方法：将该数的十进制表示从右端开始，每两位一组构成一个整数，然后将这些数相加，判断其和能否被11整除。例如， 将 562843748分割成 5,62,84,37,48,然后判断(5+62+84+37+48)能否被11整除/将一个大整数看成一个数组/数组 的奇数位对应数的10倍加上数组偶数对 应数的本身验证结果能否被11整除main() #include using namespace std; intint a9=5,6,2,8,4,3,7,4,8;int result=

12、0; /result为题目要求的各位之和for(int i=0;i!=9;+i)if(i%2=0) result+=ai; /i为偶数位时，结果加上其对应数组数的 本身 else result+=ai*10; /i 为奇数位时，结果加上对应数组数的10倍 if(result=0) coutcout 4.数字游戏。把数字1,2,?,9这 9个数字填入以下含有加、减、乘、除的 四则运算式中，使得该等式成立。要求9 个数字均出现一次且仅出现一次，且数 字1不能出现在乘和除的一位数中。？刈 + ?-? ? = 05.设计算法求解an mod m,其中a、n 精选公文范文，管理类，工作总结类，工作计划类

13、文档，感谢阅读下载 和 m均为大于1的整数。#include using namespacestd; 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() inta, n, m;cout>a>>n>>m; cout i

14、nt result = resultmod(a, n);cout 6.设计算法，在数组rn中删除所有元素值为x的元素，要求时间复杂性为O(n),空间复杂性为O(1)。7.设计算法，在数组rn中删除重复的元素， 要求移动元素的次数较少并使剩余元素 间的相对次序保持不变。 #include using namespace std;voiddeletere(int a,int N) int b100=0; int i,k; k=0; static int j=0; for(i=0;i int main() int a=1,2,1,3,2,4; 精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅

15、读下载 8 =精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载=deletere(a,6); return 0; /在数组查找相同的元素把其中一个相同的数值的元素位置设成一个特#include int main()殊数值” 输出所求函数int i,j;using namespace std;for( i=0;ifor(j=0；jint a=1,2,1,5,3,2,9,4,5,535;ai=64787250;/设一个数组不存在的数值 /forfor(i=0;i 10 表 A=a1, a2, ?, an)将 A 拆成 B 和 C 两个表，使A中值大于等于0的元素存 入表B,值小于0的

16、元素存入表C,要 求表B和C不另外设置存储空间而利用表A的空间。排将大于的元素给C namespacestd; low,int high) l0=llow; (low=prvotkey) llow=lhigh;/先对A进行快 的元素给B,小于0#include using int partions(int l,int int prvotkey=llow;while (lowwhile (lowwhile-high;lhigh=llow; llow=l0; return low; voidqsort(int l,int low,int high) int prvotloc;if(lowprvot

17、loc=partions(l,low,high); 将第一 次排序的结果作为枢轴 qsort(l,low,prvotloc-1); 递归调 用排序low至 Uprvotloc-1qsort(l,prvotloc+1,high); 递归调用排序prvotloc+1 至ll high void quicksort(int l,int n) qsort(l,1,n); /第一个作为枢轴，从第一个排到第n个 int main() inta11=-2,2,32,43,-23,45,36,-57,14,27,-39;quicksort(a,11); for(inti=1;i cout cout retur

18、n0;9.荷兰国旗问题。要求重新排列一个字符 R, W, B构 成的数组，使得所有的R都排在最前面，W排在其次，B排在最后。为荷兰国旗 问题设计一个算法，其时间性能是O(n)。/0代表红；1代表白；2代表蓝 #include 精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载 =精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载=using namespace std; const int N = 20;void swap_ab (int *p , int *q ) int tmp = *p; *p = *q; *q = tmp; void process ( int

19、a,int n ) int *p, *q; p = q = a; while ( p != a+n-1 ) /p向前遍历，直到便 利完毕 if ( *(p+1) q = p+1; while ( *q swap_ab ( q, q-1 ); -q; q 指针后移 if +p; /while int main() int aN= 0, 2, 1,2,0, 1, 0, 2, 2, 1, 0, 1,2, 1, 1, 0, 0, 1, 1, 2; 待处理的数组 cout for (int i=0; i cout 10. 设最近对问题以k维空间的形式出现，k 维空间的两个点p1=(x1, x2, ?,

20、xk)和p2=(y1, y2, ?, yk)的欧几里德距离定义 为：d(p1,p2)?(y-x)iii?1k2。对 k 维空间 的最近对问题设计蛮力算法，并分析其时间性能。11.设计蛮力算法求解小规模的线性规划问题。假设约 束条件为：x+yw« x+3y06 x0且yAQ 使目标函数3x+5y取得极大值。 精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载 11 #include using namespace std; int main() int x,y,x0,y0; int summax=0,temp=0;for(x0=0;x0for(y0=0;(x0+yOtemp

21、=3*x0+5*y0;if(temp=summax) summax=temp; x=x0;/ 符 合 sum最大值的x y=y0;/符合sum最大 值得 y /for coutreturn 0; 12.设计算法，判定一个以邻接矩阵表示的连通图是否具有欧 拉回路。算法描述：输入：邻接矩阵(n*n)输出：如有证明有欧拉回路，则输出该回路，否则，输出无 解信息1对矩阵的对角线是否有0的 元素进行判断循环变量i从1 n重复进行下述操作：计算矩阵i次方，如果矩阵对角线上有0的元素，则 跳转到 否则+i;如果矩阵对角线有0的元素，则输出该回路 2输 出无解信息；13.找词游戏。要求游戏者从一张填满字符的正

22、方形表 中，找出包含在一个给定集合中的所有精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载 12 精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载单词。这些词在正方形表中可以横着读、 竖着读、或者斜着读。为这个游戏设计 一个蛮力算法14.变位词。给定两个单词，判断这两个单词是否是变位 词。如果两个单词的字母完全相同，只 是位置有所不同，则这两个单词称为变 位词。例如， eat和tea是变位词。/判断qwer和rewq是否是变位词 #include #include using namespace std; int main() char s5= char t5= f

23、or(int i=0;i!=4;+i)if(si!=t3-i)coutcoutreturn 0; 15.在美国有一个连锁店叫7-11店，因为这个商店以前是早晨 7点开门，晚上11点关门。有一天，一 个顾客在这个店挑选了四样东西，然后 到付款处去交钱。营业员拿起计算器， 按了一些键，然后说：总共是$。”这个顾客开了个玩笑说：哦？难道因为你们的店名叫7-11,所以我就要付$吗？ "营 业员没有听出这是个玩笑，回答说： 当 然不是，我已经把这四样东西的价格相乘才得出这个结果的！ ”顾客一听非常吃 惊，你怎么把他们相乘呢？你应该把他 们相加才对！ ”营业员答道：噢，对不起，我今天非常头疼，所

24、以把键按错了。 然后，营业员将结果重算了一遍，将这 四样东西的价格加在一起，然而，令他 俩更为吃惊的是总和也是$。设计蛮力算 法找出这四样东西的价格各是多少？该算法为：int $(float afloat b,floatc,float d,int n) for(int i=0;i!=n;+i) for(int j=0；j!=n；+j)for(intk=0;k!=n;+k)for(intm=0;m!=n;+m)if(ai+bj+ck+dm)=&& ai*bj*ck*dm=)cout习题41.分治法的时间性能与直接计算最小问题的时间、合并子问 题解的时间以及子问题的个数有关，试 说

25、明这几个参数与分治法时间复杂性之 间的关系。 2.证明：如果分治法 的合并可以在线性时间内完成，则当子 问题的规模之和小于原问题的规模时，精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载14=精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载=算法的时间复杂性可达到O(n)。O(N)=2*O(N/2)+xO(N)+x=2*O(N/2)+2*x a*O(N)+x=a*(2*O(N/2)+x)+x=2*a *O(N/2)+(a+1)*x 此可知，时间复杂度可 达到O(n);3.分治策略一定导致递归吗？如果是，请解释原因。如果不是， 给出一个不包含递归的分治例子，并阐 述这

26、种分治和包含递归的分治的主要不 同。不一定导致递归。如非递归的二叉树中序遍历。这种分治方法与递归的二叉树中序遍历主要区 别是：应用了栈这个数据结构。 4.对于待排序序列(5, 3, 1, 9),分别画出归 并排序和快速排序的递归运行轨迹。归并排序：第一趟：；第二趟：；第三趟：；快速排序：第一趟：5; /5为哨兵，比较9和5第二趟：5; 比较1和5,将1挪到相应位置； 第三趟：5;/比较3和5;第四趟：；5.设计分治算法求一个数组中的最大元 素，并分析时间性能。简单的分治问题 /将数组均衡的分为前”， 后”两部分 分别求出这两部分最大值，然后再比较这两个最大值 #include using na

27、mespace std; extern const int n=6;/声明 int main() int an=0,6,1,2,3,5; 初始化 int mid=n/2;intnum_max1=0,num_max2=0; for(int i=0;inum_max1)num_max1=ai; for(intj=n/2+1;jnum_max2) num_max2=aj;if(num_max1>=num_max2)coutcout 时间复杂度：O 6.设计 分治算法，实现将数组An中所有元素 循环左移k个位置，要求时间复杂性为 O(n),空间复杂性为O(1)。例如，对abcdefgh循环左移3

28、位得到defghabCo /采用分治法/将数组分为0-k-1和k-n-1两块将这两块分别左移然后精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载16精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载再合并左移#include usingnamespace std;voidLeftReverse(char *a, int begin, int end) for(int i=0;iinttemp=abegin+i; abegin+i=aend-i;aend-i=temp; voidConverse(char *a,int n,int k) LeftReverse(a,0,

29、k-1);LeftReverse(a,k,n-1);LeftReverse(a, 0, n-1); for(int i=0;i int main() chara7='a' , ' b' , ' c' , ' d' , ' e'Converse(a,7,3);return 0;7.设计递归算法生成n个元素的所有排 歹U 对象。#include usingnamespace std;int data100;在m个数中输出n个排列数 voidDPpl(int num,int m,int n,int depth) if(d

30、epth=n) for(inti=0;i for(int j=0;j if(num&(1 DPpl(num+(1int main()DPpl(0,5,1,0);精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载 17 DPpl(0,5,2,0);DPpl(0,5,3,0);DPpl(0,5,4,0); return 0; DPpl(0,5,5,0);.设计分治算法求解一维空间上n个点的最近对问题。 参见最近对问题的算法分析及算法实现9.在有序序列(r1, r2, ?, rn)中，存在序号 i,使得ri=i。请设计一个分治算法找到 这个元素，要求算法在最坏情况下的时 间性能为

31、O(log2n)。/在有序数组中采用二分法查找符合条件的元素#include using namespacestd; void Findnum(int *a,int n) int low=0; int high二n-1;while(low int mid=(low+high)/2; if(amid=mid) coutmid) 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.在一个序列中出现次数最多的元素称为众数。请 设计算法寻找众数并分析算

32、法的时间复 杂性。先对序列进行快速排精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载 18 序再进行一次遍历 次数namespace std;low,int high) b0=blow; while (low=prvotkey) blow=bhigh;bhigh=blow; return low; low,int high)输出众数的重复#include using int partions(int b,int int prvotkey=blow;(lowwhile-high;while (low blow=b0;void qsort(int l,int int prvotloc

33、; if(lowprvotloc=partions(l,low,high);将第一次排序的结果作为枢轴 qsort(l,low,prvotloc-1); 递归调 用排序 low至 Uprvotloc-1qsort(l,prvotloc+1,high); 递归调用排序 prvotloc+1 到I high void quicksort(int l,int n) qsort(l,1,n); / 第一个作为枢轴，从第一个排到第n个 int main() int精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载 19 =精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载=a10

34、=1,235,333,2,5,1; int i=0; int count=0; int max=0;/max 表示出 现的次数qsort(a,0,10);while(imax) max=count;count=0; /while cout return 0; 时间复杂度nlog(n) 11.设M是一个nxn 的整数矩阵，其中每一行和每一列的元 素都按升序排列。设计分治算法确定一 个给定的整数x是否在M中，并分析算 法的时间复杂性。12.设S是n个不等的正整数的集合，要求将集 合S划分为子集S1和S2,使得| S1|=| S2|=n/2,且两个子集元素之和的差达到 最大。先用快速排序进行一趟排序/如果s1的的个数大于n/2将个最小的数排到后面/如果s1的的 个数小于n/2 将s2n/2-low-1排到前面将排好的数组的前n/2个数赋值给s1 / 将排好的数组的后 n/2个数赋值给s2n=#include using namespace std; const intvoid partions(int a,int low,int精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载 20 精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载high) 进行一趟快排 intprvotkey=alow; a0=alow; w