《算法设计与分析习题与实验题(12.18)》由会员分享，可在线阅读，更多相关《算法设计与分析习题与实验题(12.18)（28页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析习题第一章 引 论 习题1-1 写一个通用方法用于判定给定数组是否已排好序。解答： Algorithm compare(a,n) Begin J=1; While (jn and aj=aj+1) do j=j+1; If j=n then return true Else While (j=aj+1) do j=j+1; If j=n then return true else return false end if End if end 习题1-2 写一个算法交换两个变量的值不使用第三个变量。 解答： x=x+y; y=x-y; x=x-y;习题1-3 已知m,n为自然数，其
2、上限为k（由键盘输入，1=k=109）,找出满足条件 (n2-mn-m2)2=1 且使n2+m2达到最大的m、 n。解答： m:=k; flag:=0;repeat n:=m; repeat l:=n*n-m*n-m*n; if (l*l=1) then flag:=1 else n:=n-1; until (flag=1) or (n=0) if n=0 then m:=m-1until (flag=1) or (m=0); 第二章 基础知识习题2-1 求下列函数的渐进表达式：3n2+10n; n2/10+2n; 21+1/n; logn3; 10 log3n 。解答： 3n2+10n=O（
3、n2）， n2/10+2n=O（2n）， 21+1/n=O（1）， logn3=O（log n），10 log3n=O（n）。习题2-2 说明O(1)和 O(2)的区别。 习题2-3 照渐进阶从低到高的顺序排列以下表达式：，。 解答：照渐进阶从低到高的顺序为：、 3n、 、20n、logn、2习题2-4 （1） 假设某算法在输入规模为n时的计算时间为。在某台计算机上实现并完成该算法的时间为t秒。现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？（2） 若上述算法的计算时间改进为，其余条件不变，则在新机器上用t秒时间能解输入规模多
4、大的问题？（3） 若上述算法的计算时间进一步改进为,其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？解答：（1） 设新机器用同一算法在t秒内能解输入规模为的问题。因此有，解得。（2） 。（3） 由于常数，因此算法可解任意规模的问题。习题2-5 XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。对于计算复杂性分别为，和的各算法，若用ABC公司的计算机能在1小时内能解输入规模为的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？ 解答：。习题2-6对于下列各组函数和，确定或或，并简述理由。（1）。（2）。（3）。（4）。（5）。
5、（6）。（7）。（8）。解答：（1）。（2）。（3）。（4）。（5）。（6）。（7）。（8）。习题2-7 证明：如果一个算法在平均情况下的计算时间复杂性为，则该算法在最坏情况下所需的计算时间为。证明：因此，。习题2-7 求解下列递归方程: s0=0 sn=2sn-1+2n -1 解答：步骤: 1应用零化子化为齐次方程，2解此齐次方程的特征方程，3由特征根构造一般解，4再由初始条件确定待定系数，得到解为：习题2-8 求解下列递归方程: 解 hn=2n+1(n+1) 第三章 递归与分治策略习题3-1 下面的7个算法都是解决二分搜索问题的算法。请判断这7个算法的正确性。如果算法不正确，请说明产生错误
6、的原因。如果算法正确，请给出算法的正确性证明。public static int binarySearch1(int a,int x,int n)int left=0; int right =n-1;while (left amiddle) left = middle;else right = middle;return -1;public static int binarySearch2(int a, int x, int n)int left = 0; int right = n-1;while ( left right-1 ) int middle = ( left + right )/
7、2;if ( x = amiddle) left = middle;else right = middle;if ( x = aleft) return left ;else return -1;public static int binarySearch4(int a, int x, int n)if (n0 & x= a0) int left = 0; int right = n-1;while (left right ) int middle = (left + right )/2;if ( x 0 & x = a0 ) int left = 0; int right = n-1;whi
8、le (left right ) int middle = ( left + right +1)/2;if ( x 0 & x= a0) int left = 0; int right = n-1;while ( left right) int middle = (left + right +1)/2;if (x 0 & x=a0) int left = 0; int right = n-1;while ( left right) int middle = ( left + right + 1)/2;if ( x amiddle) right = middle;else left = midd
9、le;if ( x = aleft) return left;return -1;分析与解答：算法binarySearch1数组段左右游标left和right的调整不正确，导致陷入死循环。算法binarySearch2数组段左右游标left和right的调整不正确，导致当x=an-1时返回错误。算法binarySearch3数组段左右游标left和right的调整不正确，导致当x=an-1时返回错误。算法binarySearch4数组段左右游标left和right的调整不正确，导致陷入死循环。算法binarySearch5正确，且当数组中有重复元素时，返回满足条件的最右元素。算法binaryS
10、earch6数组段左右游标left和right的调整不正确，导致当x=an-1时返回错误。算法binarySearch7数组段左右游标left和right的调整不正确，导致当x=an-1时陷入死循环。习题3-2 设是已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。分析与解答：改写二分搜索算法如下：public static boolean binarySearch(int a, int x, int left, int right, int ind)int middle;while ( left amiddle) left = middle + 1;else right = middle -1;ind0 = right; ind1=left;return false;返回的ind1是小于x的最大元素位置，ind0是大于x的最小元素的位置。习题3-3 设是
