算法设计与分析习题答案1-6章
更新时间:2024-06-19 18:27:01 阅读量: 综合文库 文档下载
- 算法设计与分析第二版推荐度:
- 相关推荐
习题1
1.
图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉(Leonhard Euler,1707—1783)提出并解决了该问题。七桥问题是这样描述的:北区 一个人是否能在一次步行中穿越哥尼斯堡(现
东区 在叫加里宁格勒,在波罗的海南岸)城中全部岛区 的七座桥后回到起点,且每座桥只经过一次,
南区 图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
int partions(int b[],int low,int high) {
int prvotkey=b[low]; b[0]=b[low]; while (low while (low 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 a[11]={0,2,32,43,23,45,36,57,14,27,39}; int value=0;//将最小差的值赋值给value for (int b=1;b<11;b++) cout< quicksort(a,11); for(int i=0;i!=9;++i) { if( (a[i+1]-a[i])<=(a[i+2]-a[i+1]) ) value=a[i+1]-a[i]; else value=a[i+2]-a[i+1]; } cout< return 0; } 4. 设数组a[n]中的元素均不相等,设计算法找出a[n]中一个既不是最大也不是最小的元素,并说明最坏情况下的比较次数。要求分别给出伪代码和C++描述。 #include 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整除。 #include int main() { double value=0; for(int n=1;n<=10000 ;++n) { value=value*10+1; if(value 13==0) { cout<<\至少为:\ break; } }//for return 0; } 6. 计算π值的问题能精确求解吗?编写程序,求解满足给定精度要求的π值 #include int main () { double a,b; double arctan(double x);//声明 a = 16.0*arctan(1/5.0); b = 4.0*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和它本身,所有小于它本身的因数称为这个数的真因数,如果一个自然数的真因数之和等于它本身,这个自然数称为完美数。例如,6=1+2+3,因此6是完美数。神6天创造世界,暗示着该创造是完美的。设计算法,判断给定的自然数是否是完美数 #include 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<<\该自然数是完美数\ else cout<<\该自然数不是完美数\ return 0; } 8. 有4个人打算过桥,这个桥每次最多只能有两个人同时通过。他们都在桥的某一端,并且是在晚上,过桥需要一只手电筒,而他们只有一只手电筒。这就意味着两个人过桥后必须有一个人将手电筒带回来。每个人走路的速度是不同的:甲过桥要用1分钟,乙过桥要用2分钟,丙过桥要用5分钟,丁过桥要用10分钟,显然,两个人走路的速度等于其中较慢那个人的速度,问题是他们全部过桥最少要用多长时间? } } 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 int main() { int n;//分子 int m;//分母 int factor;//最大公因子 int factor1; cout<<\输入一个真分数的分子与分母: \ cin>>n>>m; int r = m % n;//因为是真分数 所以分母一定大于分子 factor1=m; factor=n; while (r != 0) { factor1 =factor; factor = r; r = factor1% factor; } cout<<\输出该真分数的最简分数: \return 0; } 3. 设计算法,判断一个大整数能否被11整除。可以通过以下方法:将该数的十进制表示 从右端开始,每两位一组构成一个整数,然后将这些数相加,判断其和能否被11整除。例如,将562843748分割成5,62,84,37,48,然后判断(5+62+84+37+48)能否被11整除 //将一个大整数看成一个数组 //数组的奇数位对应数的10倍加上数组偶数对应数的本身 //验证结果能否被11整除 #include 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<<\该整数能被11整除\ else cout<<\该整数不能被11整除\ return 0; } 4. 数字游戏。把数字 1,2,?,9这9个数字填入以下含有加、减、乘、除的四则运算式中,使得该等式成立。要求9个数字均出现一次且仅出现一次,且数字1不能出现在乘和除的一位数中(即排除运算式中一位数为1的平凡情形)。 ??×?+???÷?-?? = 0 5. 设计算法求解an mod m,其中a、n和m均为大于1的整数。(提示:为了避免an 超出int型的表示范围,应该每做一次乘法之后对n取模) #include 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: \ cin>>a>>n>>m; cout< int result = resultmod(a, n); cout<<\的结果为:\ return 0; } 6. 设计算法,在数组r[n]中删除所有元素值为x的元素,要求时间复杂性为O(n),空间复杂性为O(1)。 7. 设计算法,在数组r[n]中删除重复的元素,要求移动元素的次数较少并使剩余元素间的相对次序保持不变。 #include void deletere(int a[],int N) { int b[100]={0}; int i,k; k=0; static int j=0; for(i=0;i //在数组查找相同的元素 //把其中一个相同的数值的元素位置设成一个“特殊数值” //输出所求函数 #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<12;i++) { for(j=0;j a[i]=64787250;//设一个数组不存在的数值 } }//for for(i=0;i<12;i++) { if(a[i]!=64787250) cout< 8. 设表A={a1, a2, ?, an},将A拆成B和C两个表,使A中值大于等于0的元素存入表B,值小于0的元素存入表C,要求表B和C不另外设置存储空间而利用表A的空间。 //先对A进行快排 //将大于0的元素给B,小于0的元素给C #include int partions(int l[],int low,int high) { int prvotkey=l[low]; l[0]=l[low]; while (low while (low l[low]=l[high]; while (low 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<11;i++) { if(a[i]<0) cout<<\ else cout<<\ } cout< return 0; } 9. 荷兰国旗问题。要求重新排列一个由字符R, W, B(R代表红色,W代表白色,B代表兰色,这都是荷兰国旗的颜色)构成的数组,使得所有的R都排在最前面,W排在其次,B排在最后。为荷兰国旗问题设计一个算法,其时间性能是O(n)。 //0代表红;1代表白;2代表蓝 #include 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) < *p ) { q = p+1; while ( *q < *(q-1) ) { 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 << \处理后的数组序列: \ process ( a, N ); for (int i=0; i< N; ++i ) cout << a[i] <<\ cout << endl; return 0; } 10. 设最近对问题以k维空间的形式出现,k维空间的两个点p1=(x1, x2, ?, xk)和p2=(y1, y2, ?, yk)的欧几里德距离定义为:d(p1,p2)??(y-x)iii?1k2。对k维空间的最近对问题设计 蛮力算法,并分析其时间性能。 11.设计蛮力算法求解小规模的线性规划问题。假设约束条件为:(1)x+y≤4;(2)x+3y≤6;(3)x≥0且y≥0;使目标函数3x+5y取得极大值。 #include int main() { int x,y,x0,y0; int summax=0,temp=0; for(x0=0;x0<=4;++x0) { for(y0=0;(x0+y0<=4)&&(x0+3*y0<=6);++y0) temp=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的元素进行判断 1.1 循环变量i从1—n重复进行下述操作: 1.1.1计算矩阵i次方,如果矩阵对角线上有>0的元素,则跳转到1.2 1.1.2否则++i; 1.2 如果矩阵对角线有>0的元素,则输出该回路 2 输出无解信息; 13.找词游戏。要求游戏者从一张填满字符的正方形表中,找出包含在一个给定集合中的所有单词。这些词在正方形表中可以横着读、竖着读、或者斜着读。为这个游戏设计一个蛮力算法 14. 变位词。给定两个单词,判断这两个单词是否是变位词。如果两个单词的字母完全相同,只是位置有所不同,则这两个单词称为变位词。例如,eat和tea是变位词。 //判断qwer和rewq是否是变位词 #include int main() { char s[5]=\ char t[5]=\ for(int i=0;i!=4;++i) { if(s[i]!=t[3-i]) { cout<<\和rewq不是变位词\ return 0; break; } } cout<<\和rewq是变位词\ return 0; } 15.在美国有一个连锁店叫7-11店,因为这个商店以前是早晨7点开门,晚上11点关门。有一天,一个顾客在这个店挑选了四样东西,然后到付款处去交钱。营业员拿起计算器,按了一些键,然后说:“总共是$7.11。”这个顾客开了个玩笑说:“哦?难道因为你们的店名叫7-11,所以我就要付$7.11吗?”营业员没有听出这是个玩笑,回答说:“当然不是,我已经把这四样东西的价格相乘才得出这个结果的!”顾客一听非常吃惊,“你怎么把他们相乘呢?你应该把他们相加才对!”营业员答道:“噢,对不起,我今天非常头疼,所以把键按错了。”然后,营业员将结果重算了一遍,将这四样东西的价格加在一起,然而,令他俩更为吃惊的是总和也是$7.11。设计蛮力算法找出这四样东西的价格各是多少? 该算法为: int $7.11(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])==7.11 && a [i]*b[j]*c[k]*d[m]==7.11) cout< 习题4 1. 分治法的时间性能与直接计算最小问题的时间、合并子问题解的时间以及子问题的个数有关,试说明这几个参数与分治法时间复杂性之间的关系。 2. 证明:如果分治法的合并可以在线性时间内完成,则当子问题的规模之和小于原问题的规模时,算法的时间复杂性可达到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,3)(1,9); 第二趟:(3,5,1,9); 第三趟:(1,3,5,9); 快速排序: 第一趟:5( ,3,1,9);//5为哨兵,比较9和5 第二趟:5(1,3, ,9);//比较1和5,将1挪到相应位置; 第三趟:5(1,3, ,9);//比较3和5; 第四趟:(1,3,5,9); 5. 设计分治算法求一个数组中的最大元素,并分析时间性能。 //简单的分治问题 //将数组均衡的分为“前”,“后”两部分 //分别求出这两部分最大值,然后再比较这两个最大值 #include 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;i<=n/2;++i)//前半部分 { if(a[i]>num_max1) num_max1=a[i]; } for(int j=n/2+1;j cout<<\数组中的最大元素: \ return 0; } 时间复杂度:O(n) 6. 设计分治算法,实现将数组A[n]中所有元素循环左移k个位置, 要求时间复杂性为O(n),空间复杂性为O(1)。例如,对abcdefgh循环左移3位得到defghabc。 //采用分治法 //将数组分为0-k-1和k-n-1两块 //将这两块分别左移 //然后再合并左移 #include void LeftReverse(char *a, int begin, int end) { for(int i=0;i<(end-begin+1)/2;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 char a[7]={'a','b','c','d','e','f','g'}; Converse(a,7,3); return 0; } 7. 设计递归算法生成n个元素的所有排列对象。 #include int data[100]; //在m个数中输出n个排列数(n<=m) 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+(1< int main() { DPpl(0,5,1,0); DPpl(0,5,2,0); DPpl(0,5,3,0); DPpl(0,5,4,0); DPpl(0,5,5,0); return 0; } 8. 设计分治算法求解一维空间上n个点的最近对问题。 参见4.4.1最近对问题的算法分析及算法实现 9. 在有序序列(r1, r2, ?, rn)中,存在序号i(1≤i≤n),使得ri=i。请设计一个分治算法找到这个元素,要求算法在最坏情况下的时间性能为O(log2n)。 //在有序数组中 //采用二分法查找符合条件的元素 #include void Findnum(int *a,int n) { int low=0; int high=n-1; while(low<=high) { int mid=(low+high)/2; if(a[mid]==mid) { cout<<\这个数是: \ break; } else if(a[mid]>mid) 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. 在一个序列中出现次数最多的元素称为众数。请设计算法寻找众数并分析算法的时间复杂性。 //先对序列进行快速排序 //再进行一次遍历 //输出众数的重复次数 #include int partions(int b[],int low,int high) { int prvotkey=b[low]; b[0]=b[low]; while (low while (low 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 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(i<10) { int j; j=i+1; if(a[i]=a[j]&&i<10) { count++; i++; } if(count>max) { max=count; count=0; } }//while cout<<\重复次数:\ return 0; } 时间复杂度nlog(n) 11. 设M是一个n×n的整数矩阵,其中每一行(从左到右)和每一列(从上到下)的元素都按升序排列。设计分治算法确定一个给定的整数x是否在M中,并分析算法的时间复杂性。 12. 设S是n(n为偶数)个不等的正整数的集合,要求将集合S划分为子集S1和S2,使得| S1|=| S2|=n/2,且两个子集元素之和的差达到最大。 //先用快速排序进行一趟排序 //如果s1(大的数集)的的个数大于n/2 //将(i<=n/2-low-1)个最小的数排到后面 //如果s1(大的数集)的的个数小于n/2 //将s2(小的数集)n/2-low-1排到前面 //将排好的数组的前n/2个数赋值给s1 //将排好的数组的后n/2个数赋值给s2 #include void partions(int a[],int low,int high) { //进行一趟快排 int prvotkey=a[low]; a[0]=a[low]; while (low while (low a[low]=a[high]; while (low a[high]=a[low]; } a[low]=prvotkey; //如果s1(大的数集)的的个数大于n/2 if(low>=n/2) { for(int i=0;i<=n/2-low-1;++i) { for(int j=0;j { if(a[j] //如果s1(大的数集)的的个数小于n/2 else for(int i=0;i<=n/2-low-1;++i) { for(int k=n-1;k 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<4) { cout<<\属于子集s1的:\ cout< cout<<\属于子集s2的:\ cout< } } return 0; } 13. 设a1, a2,?, an是集合{1, 2, ?, n}的一个排列,如果i //用归并进行排序 //当一个子集的一个数大于第二个子集的一个数,为逆序,即a[i]>a[j] //则逆序数为end-j+1; #include int count; void Merge(int a[],int a1[],int begin,int mid,int end)//合并子序列 { int i=begin,j=mid+1,k=end; while(i<=mid&&j<=end) { if(a[i]<=a[j]) a1[k++]=a[i++];//取a[i]和a[j]中较小者放入r1[k] else { a1[k++]=a[j++]; count+=(end-j+1); } } while(i<=mid) a1[k++]=a[i++]; while(j<=end) a1[k++]=a[j++]; } void MergeSort(int a[ ], int begin, int end) { int mid,a1[1000]; if(begin==end) return ; else { mid=(begin+end)/2; MergeSort(a,begin,mid); MergeSort(a,mid+1,end); Merge(a,a1,begin,mid,end); } } int main() { int a[6]={6,5,4,3,2,1}; count=0; MergeSort(a,0,6); cout< 14. 循环赛日程安排问题。设有n=2k个选手要进行网球循环赛,要求设计一个满足以下要求的比赛日程表: (1)每个选手必须与其他n-1个选手各赛一次; (2)每个选手一天只能赛一次。 采用分治方法。 将2^k选手分为2^k-1两组,采用递归方法,继续进行分组,直到只剩下2个选手时,然后进行比赛,回溯就可以指定比赛日程表了 15. 格雷码是一个长度为2n的序列,序列中无相同元素,且每个元素都是长度为n的二进制位串,相邻元素恰好只有1位不同。例如长度为23的格雷码为(000, 001, 011, 010, 110, 111, 101, 100)。设计分治算法对任意的n值构造相应的格雷码。 //构造格雷码 #include int n; char a[100]; void gelei(int k) { if(k==n) { cout<
正在阅读:
算法设计与分析习题答案1-6章06-19
《科学通史》尔雅作业答案07-08
GDAQ1108在建项目危险源与不利环境因素识别与评价汇总表08-21
教育改造手段的创新11-11
教师考试质量分析报告表03-20
2016版最新整理苏教版四年级下册语文练习与测试答案03-11
业务注意事项新版10-13
人卫版无机化学习题答案03-11
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 习题
- 算法
- 答案
- 分析
- 设计
- 2008全国教育技术考试题
- PROE 靠证全部模拟试题(理论知识)
- 海关监管货物仓储
- projectwise协同工作平台 - 图文
- 专业技术人员沟通与协调能力的提升
- C++期末考试题及答案
- 2019年春人教版道德与法治九年级下册全套教案
- 国际分工与产业结构变动的一般均衡理论模型 - 图文
- 大学生沉迷网络的原因及对策
- 脉冲式电磁阀
- 新视野大学英语4-课后翻译答案
- 天津河西区 - 图文
- 加强党性修养和锻炼永葆党的先进性-精品文档
- 华中师范大学2014年马克思主义学院(政治传播学院)
- 福建省国土资源厅关于进一步规范土地用途分类管理的通知(闽国土
- 食品微生物题库及答案
- 关于印发《湖南省产权交易所企业国有资产产权交易规则》的通知
- 129339451987812500学生用 考试复习题
- 学前教育心理学试题
- 汇编自考题库