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

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载============== 算法设计与分析习题答案1

习题 1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉提出并解决了该问题。七桥问题是这样描述的：北区一个人是否能在一次步行中穿越哥尼斯堡城中全部岛区的七座桥后回到起点，且每座桥只经过一次，南区图是这条河以及河上的两个岛和七座桥的图七桥问题草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。七桥问题属于一笔画问题。输入：一个起点输出：相同的点1，一次步行2，经过七座桥，且每次只经历过一次3，回到起点该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。2．在欧几里德提出的欧几里德算法中用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算

--------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载---------------------

~ 1 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载==============

法=m-n 2.循环直到r=0 m=n n=r r=m-n 3 输出m 3．设计算法求数组中相差最小的两个元素的差。要求分别给出伪代码和C++描述。//采用分治法//对数组先进行快速排序//在依次比较相邻的差#include using namespace std; int partions(int b,int low,int high) { int prvotkey=b[low]; b[0]=b[low]; while (low while (low=prvotkey)--high; b[low]=b[high]; while (low b[high]=b[low]; } b[low]=b[0]; 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 到prvotloc-1 qsort(l,prvotloc+1,high); //递归调用排序prvotloc+1到high } } void quicksort(int l,int n) { qsort(l,1,n); // --------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载--------------------- ~ 2 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载==============

第一个作为枢轴，从第一个排到第n个} int main() { int a[11]={0,2,32,43,23,45,36,57,14,27,39};

int value=0;//将最小差的值赋值给value for (int b=1;b quicksort(a,11); for(int i=0;i!=9;++i) { if( (a[i+1]-a[i]) value=a[i+2]-a[i+1]; } cout return 0; } 4．设数组a[n]中的元素均不相等，设计算法找出a[n]中一个既不是最大也不是最小的元素，并说明最坏情况下的比较次数。要求分别给出伪代码和C++描述。#include 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(a[i+1]>a[i]&&a[i+1]a[i+2]) {mid_value=a[i+1]; cout 5. 编写程序，求n至少为多大时，n个“1”组成的整数能被2013整除。--------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载---------------------

~ 3 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载============== #include using namespace std; int main() { double value=0; for(int n=1;n return 0; } 6. 计算π值的问题能精确求解吗？编写程序，求解满足给定精度要求的π值#include using namespace std; int main () { double a,b; double arctan(double x);//声明 a = *arctan(1/);

b = *arctan(1/239); cout return 0；} double arctan(double x) { int i=0; 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}//while return r; } 7. 圣经上说：神6天创造天地万有，第7日安歇。为什么是6天呢？任何一个自然数的因数中都有1和它本身，所有小于它本身的因数称为这个数的真因数，如果一个自然数的真--------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载---------------------

~ 4 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载==============

因数之和等于它本身，这个自然数称为完美数。例如，6=1+2+3，因此6是完美数。神6天创造世界，暗示着该创造是完美的。设计算法，判断给定的自然数是否是完美数#include using namespace 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 if(k==value) cout cout8. 有4个人打算过桥，这个桥每次最多只能有两个人同时通过。他们都在桥的某一端，并且是在晚上，过桥需要一只手电筒，而他们只有一只手电筒。这就意味着两个人过桥后必须有一个人将手电筒带回来。每个人走路的速度是不同的：甲过桥要用1分钟，乙过桥要用2分钟，丙过桥要用5分钟，丁过桥要用10分钟，显然，两个人走路的速度等于其中较慢那个人的速度，问题是他们全部过桥最--------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载---------------------

~ 5 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载============== 少要用多长时间？

} } if (T[j] == ‘\\0’) return (i - strlen(T) +1);//返回本趟匹配的开始位置else return 0; } int main() { char s1=\ char s2=\cout return 0;} 2.分式化简。设计算法，将一个给定的真分数化简为最简分数形式。例如，将6/8化简为3/4。#include using namespace std; int main() { int n;//分子int m;//分母int factor;//最大公因子int factor1; cout>n>>m; int r = m % n;//因为是真分数所以分母一定大于分子factor1=m; factor=n; while (r != 0) { factor1 =factor; factor = r; r = factor1% factor; } cout 3. 设计算法，判断一个大整数能否被11整除。可以通过以下方法：将该数的十进制表示从右端开始，每两位一组构成一个整数，然后将这些数--------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载--------------------- ~ 6 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载==============

相加，判断其和能否被11整除。例如，将562843748分割成5,62,84,37,48，然后判断(5+62+84+37+48)能否被11整除//将一个大整数看成一个数组//数组的奇数位对应数的10倍加上数组偶数对应数的本身//验证结果能否被11整除#include using namespace std; int main() { int a[9]={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+=a[i]; //i 为偶数位时，结果加上其对应数组数的本身else result+=a[i]*10; //i 为奇数位时，结果加上对应数组数的10倍}if(result ==0) cout cout 4. 数字游戏。把数字1,2,?,9这9个数字填入以下含有加、减、乘、除的四则运算式中，使得该等式成立。要求9个数字均出现一次且仅出现一次，且数字1不能出现在乘和除的一位数中。??×?＋???÷?－?? = 0 5. 设计算法求解an mod m，其中a、n --------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载--------------------- ~ 7 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载==============

和m均为大于1的整数。#include 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; cout>a>>n>>m; cout int result = resultmod(a, n); cout 6. 设计算法，在数组r[n]中删除所有元素值为x 的元素，要求时间复杂性为O(n)，空间复杂性为O(1)。7. 设计算法，在数组r[n]中删除重复的元素，要求移动元素的次数较少并使剩余元素间的相对次序保持不变。#include using namespace std; void deletere(int a,int N) { int b[100]={0}; int i,k; k=0; static int j=0; for(i=0;i int main() { int a={1,2,1,3,2,4}; --------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载---------------------

~ 8 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载============== deletere(a,6); return 0; } //在数组查找相同的元素//把其中一个相同的数值的元素位置设成一个“特殊数值” //输出所求函数#include 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 for(j=0;j a[i]=64787250;//设一个数组不存在的数值} }//for for(i=0;i8. 设表A={a1, a2, ?, an}，将A拆成B和C 两个表，使A中值大于等于0的元素存入表B，值小于0的元素存入表C，要求表B和C不另外设置存储空间而利用表A的空间。//先对A进行快排//将大于0的元素给B，小于0的元素给 C #include using namespace std; int partions(int l,int low,int high) { int prvotkey=l[low]; l[0]=l[low]; while (low while (low=prvotkey)--high; l[low]=l[high]; while (low

--------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载--------------------- ~ 9 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载==============

l[high]=l[low]; } l[low]=l[0]; 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 到prvotloc-1 qsort(l,prvotloc+1,high); //递归调用排序prvotloc+1到high } } void quicksort(int l,int n) { qsort(l,1,n); //第一个作为枢轴，从第一个排到第n个} int main() { int a[11]={-2,2,32,43,-23,45,36,-57,14,27,-39 }; quicksort(a,11); for(int i=1;i cout cout return 0; } 9. 荷兰国旗问题。要求重新排列一个字符R, W, B构成的数组，使得所有的R都排在最前面，W排在其次，B排在最后。为荷兰国旗问题设计一个算法，其时间性能是O(n)。//0代表红；1代表白；2代表蓝#include --------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载---------------------

~ 10 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载============== 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) q = p+1; while ( *q swap_ab ( q, q-1 ); --q; //q指针后移} } //if ++p; } //while } int main() { int a[N] = { 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, ?, xk)和p2=(y1, y2, ?, yk)的欧几里德距离定义为：d(p1,p2)??(y-x)iii?1k2。对k维空间的最近对问题设计蛮力算法，并分析其时间性能。11．设计蛮力算法求解小规模的线性规划问题。假设约束条件为：x+y≤4；x+3y≤6；x≥0且y≥0；使目标函数3x+5y取得极大值。--------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载---------------------

~ 11 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载============== #include using namespace std; int main() { int x,y,x0,y0; int summax=0,temp=0; for(x0=0;x0 for(y0=0;(x0+y0temp=3*x0+5*y0; if(temp>=summax)

{summax=temp;x=x0;//符合sum最大值的x y=y0;//符合sum最大值得y} }//for cout return 0; } 12．设计算法，判定一个以邻接矩阵表示的连通图是否具有欧拉回路。算法描述：输入：邻接矩阵(n*n) 输出：如有证明有欧拉回路，则输出该回路，否则，输出无解信息 1 对矩阵的对角线是否有>0的元素进行判断循环变量i从1—n重复进行下述操作：计算矩阵i次方，如果矩阵对角线上有>0的元素，则跳转到否则++i; 如果矩阵对角线有>0的元素，则输出该回路 2 输出无解信息；13．找词游戏。要求游戏者从一张填满字符的正方形表中，找出包含在一个给定集合中的所有--------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载--------------------- ~ 12 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载==============

单词。这些词在正方形表中可以横着读、竖着读、或者斜着读。为这个游戏设计一个蛮力算法14. 变位词。给定两个单词，判断这两个单词是否是变位词。如果两个单词的字母完全相同，只是位置有所不同，则这两个单词称为变位词。例如，eat和tea是变位词。//判断qwer和rewq是否是变位词#include #include using namespace std; int main() { char s[5]=\ char t[5]=\ for(int i=0;i!=4;++i) { if(s[i]!=t[3-i]) {cout cout return 0; } 15．在美国有一个连锁店叫7-11店，因为这个商店以前是早晨7点开门，晚上11点关门。有一天，一个顾客在这个店挑选了四样东西，然后到付款处去交钱。营业员拿起计算器，按了一些键，然后说：“总共是$。”这个顾客开了个玩笑说：“哦？难道因为你们的店名叫7-11，所以我就要付$吗？”营业员没有听出这是个玩笑，回答说：“当然不是，我已经把这四样东西的价格相--------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载---------------------

~ 13 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载==============

乘才得出这个结果的！”顾客一听非常吃惊，“你怎么把他们相乘呢？你应该把他们相加才对！”营业员答道：“噢，对不起，我今天非常头疼，所以把键按错了。”然后，营业员将结果重算了一遍，将这四样东西的价格加在一起，然而，令他俩更为吃惊的是总和也是$。设计蛮力算法找出这四样东西的价格各是多少？该算法为：int $(float a,float b,float c,float d,int n) { for(int i=0;i!=n;++i) for(int j=0;j!=n;++j)for(int k=0;k!=n;++k) for(int m=0;m!=n;++m)

{ if((a[i]+b[j]+c[k]+d[m])== && a [i]*b[j]*c[k]*d[m]==)cout 习题 4 1. 分治法的时间性能与直接计算最小问题的时间、合并子问题解的时间以及子问题的个数有关，试说明这几个参数与分治法时间复杂性之间的关系。 2. 证明：如果分治法的合并可以在线性时间内完成，则当子问题的规模之和小于原问题的规模时，--------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载--------------------- ~ 14 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载==============

算法的时间复杂性可达到O(n)。O(N)=2*O(N/2)+x

O(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.分治策略一定导致递归吗？如果是，请解释原因。如果不是，给出一个不包含递归的分治例子，并阐述这种分治和包含递归的分治的主要不同。不一定导致递归。如非递归的二叉树中序遍历。这种分治方法与递归的二叉树中序遍历主要区别是：应用了栈这个数据结构。 4. 对于待排序序列(5, 3, 1, 9)，分别画出归并排序和快速排序的递归运行轨迹。归并排序：第一趟：；第二趟：；第三趟：；快速排序：第一趟：5；//5为哨兵，比较9和5第二趟：5；//比较1和5，将1挪到相应位置；第三趟：5;//比较3和5；第四趟：; --------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载---------------------

~ 15 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载============== 5. 设计分治算法求一个数组中的最大元素，并分析时间性能。//简单的分治问题//将数组均衡的分为“前”，“后”两部分//分别求出这两部分最大值，然后再比较这两个最大值#include using namespace std; extern const int n=6;//声明int main() { int a[n]={0,6,1,2,3,5};//初始化int mid=n/2; int num_max1=0,num_max2=0; for(int i=0;inum_max1)

num_max1=a[i]; } for(int j=n/2+1;jnum_max2)

num_max2=a[j]; } if(num_max1>=num_max2) cout cout时间复杂度：O 6. 设计分治算法，实现将数组A[n]中所有元素循环左移k个位置, 要求时间复杂性为O(n)，空间复杂性为O(1)。例如，对abcdefgh循环左移3位得到defghabc。//采用分治法//将数组分为0-k-1和k-n-1两块//将这两块分别左移//然后--------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载--------------------- ~ 16 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载==============

再合并左移#include using namespace std; void LeftReverse(char *a, int begin, int end) { for(int i=0;i int temp=a[begin+i]; a[begin+i]=a[end-i]; a[end-i]=temp; } } void Converse(char *a,int n,int k) { LeftReverse(a, 0, k-1); LeftReverse(a, k, n-1); LeftReverse(a, 0, n-1); for(int i=0;i int main() { char a[7]={‘a’,’b’,’c’,’d’,’e’,’f’,’g’}; Converse(a,7,3); return 0; } 7. 设计递归算法生成n个元素的所有排列对象。#include using namespace std; int data[100]; //在m个数中输出n个排列数void DPpl(int num,int m,int n,int depth) { if(depth==n) { for(int i=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); DPpl(0,5,5,0); return 0; } 8. 设计分治算法求解一维空间上n个点的最近对问题。参见最近对问题的算法分析及算法实现9. 在有序序列(r1, r2, ?, rn)中，存在序号i，使得ri=i。请设计一个分治算法找到这个元素，要求算法在最坏情况下的时间性能为O(log2n)。//在有序数组中//采用二分法查找符合条件的元素#include using namespace std; void Findnum(int *a,int n) { int low=0; int high=n-1; while(low int mid=(low+high)/2; if(a[mid]==mid) { coutmid) high=mid-1; else low=mid+1;} } int main() { int a[7]={1,0,2,5,6,7,9}; Findnum(a,7); return 0; } 时间复杂度为O(log2n)。10. 在一个序列中出现次数最多的元素称为众数。请设计算法寻找众数并分析算法的时间复杂性。//先对序列进行快速排--------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载--------------------- ~ 18 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载==============

序//再进行一次遍历//输出众数的重复次数#include using namespace std; int partions(int b,int low,int high) { int prvotkey=b[low]; b[0]=b[low]; while (low while (low=prvotkey)--high; b[low]=b[high]; while (low b[high]=b[low]; } b[low]=b[0]; 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 到prvotloc-1 qsort(l,prvotloc+1,high); //递归调用排序prvotloc+1到high } } void quicksort(int l,int n) { qsort(l,1,n); //第一个作为枢轴，从第一个排到第n 个} int main() {int --------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载--------------------- ~ 19 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载============== a[10]={1,2,3,5,3,3,3,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是一个n×n 的整数矩阵，其中每一行和每一列的元素都按升序排列。设计分治算法确定一个给定的整数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个数赋值给s2 #include using namespace std; const int n=8; void partions(int a,int low,int --------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载--------------------- ~ 20 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载============== high) { //进行一趟快排int prvotkey=a[low]; a[0]=a[low]; while (low while (low a[low]=a[high]; while (low=prvotkey)++low; a[high]=a[low]; } a[low]=prvotkey; //如果s1的的个数大于n/2 if(low>=n/2) { for(int i=0;i for(int j=0;j {if(a[j]//如果s1的的个数小于n/2 else for(int i=0;i for(int k=n-1;ka[k-1]) {int temp1=a[k]; a[k]=a[k-1];

a[k-1]=temp1; }}//for} } int main() { int a[n]={1,3,5,9,6,0,-11,-8}; partions(a,0,n-1); for(int i=0;i if(i cout cout} } return 0; } 13. 设a1, a2,?, an是集合{1, 2, ?, n}的一个排列，如果iaj，则序偶(ai, aj)称为该排列的一个逆序。例如，2, 3, 1有两个逆序：(3, 1)和(2, 1)。设计算法统计给定排列中含有逆序的个数。//用归并进行排序//当一个子集的一个数大于第二个子集的--------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载--------------------- ~ 21 ~

本文来源：https://www.bwwdw.com/article/awol.html