算法设计与分析基础习题参考答案课案
5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立.
Hint:
根据除法的定义不难证明:
●如果d整除u和v, 那么d一定能整除u±v;
●如果d整除u,那么d也能够整除u的任何整数倍ku.
对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。
数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。
故gcd(m,n)=gcd(n,r)
6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?
Hint:
对于任何形如0<=m 并且这种交换处理只发生一次. 7.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?(1次) b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?(5次) gcd(5,8) 习题1.2 1.(农夫过河) P—农夫W—狼G—山羊C—白菜 2.(过桥问题) 1,2,5,10---分别代表4个人, f—手电筒 4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数) 算法Quadratic(a,b,c) //求方程ax^2+bx+c=0的实根的算法 //输入:实系数a,b,c //输出:实根或者无解信息 D←b*b-4*a*c If D>0 temp←2*a x1←(-b+sqrt(D))/temp x2←(-b-sqrt(D))/temp return x1,x2 else if D=0 return –b/(2*a) else return “no real roots” else //a=0 if b≠0 return –c/b else //a=b=0 if c=0 return “no real numbers” else return “no real roots” 5.描述将十进制整数表达为二进制整数的标准算法 a.用文字描述 b.用伪代码描述 解答： a.将十进制整数转换为二进制整数的算法 输入：一个正整数n 输出：正整数n相应的二进制数 第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n 第二步：如果n=0，则到第三步，否则重复第一步 第三步：将Ki按照i从高到低的顺序输出 b.伪代码 算法DectoBin(n) //将十进制整数n转换为二进制整数的算法 //输入：正整数n //输出：该正整数相应的二进制数，该数存放于数组Bin[1...n]中 i=1 while n!=0 do { Bin[i]=n%2; n=(int)n/2; i++; } while i!=0 do{ print Bin[i]; i--; } 9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略) 对这个算法做尽可能多的改进. 算法MinDistance(A[0..n-1]) //输入:数组A[0..n-1] //输出:the smallest distance d between two of its elements 习题1.3 1.考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的 元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去. a.应用该算法对列表”60,35,81,98,14,47”排序 b.该算法稳定吗? c.该算法在位吗? 解: a. 该算法对列表”60,35,81,98,14,47”排序的过程如下所示: b.该算法不稳定.比如对列表”2,2*”排序 c.该算法不在位.额外空间for S and Count[] 4.(古老的七桥问题) 习题1.4 1.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度. a.删除数组的第i 个元素(1<=i<=n) b.删除有序数组的第i 个元素(依然有序) hints: a. Replace the i th element with the last element and decrease the array size of 1 b. Replace the ith element with a special symbol that cannot be a value of the array ’s element(e.g., 0 for an array of positive numbers ) to mark the i th position is empty. (“lazy deletion ”) 第2章 习题2.1 7.对下列断言进行证明:(如果是错误的,请举例) a. 如果t(n )∈O(g(n),则g(n)∈Ω(t(n)) b.α>0时,Θ(αg(n))= Θ(g(n)) 解: a. 这个断言是正确的。它指出如果t(n)的增长率小于或等于g(n)的增长率，那么 g(n)的增长率大于或等于t(n)的增长率 由 t(n )≤c ·g(n) for all n ≥n0, where c>0 则：)()()1 (n g n t c ≤ for all n ≥n0 b. 这个断言是正确的。只需证明))(())(()),(())((n g n g n g n g ααΘ?ΘΘ?Θ。 设f(n)∈Θ(αg(n)),则有： )()(n g c n f α≤ for all n>=n0, c>0 )()(1n g c n f ≤ for all n>=n0, c1=c α>0 即：f(n)∈Θ(g(n)) 又设f(n)∈Θ(g(n)),则有：)()(n cg n f ≤ for all n>=n0,c>0 )()()(1n g c n g c n f ααα =≤ for all n>=n0,c1=c/α>0 即：f(n)∈Θ(αg(n)) 8．证明本节定理对于下列符号也成立： a.Ω符号 b.Θ符号 证明： a 。we need to proof that if t 1(n)∈Ω(g 1(n)) and t 2(n)∈Ω(g 2(n)), then t 1(n)+ t 2(n)∈Ω(max{g 1(n), g 2(n)})。 由 t 1(n)∈Ω(g 1(n))， t 1(n)≥c 1g 1(n) for all n>=n1, where c1>0 由 t 2(n)∈Ω(g 2(n))， T 2(n)≥c 2g 2(n) for all n>=n2, where c2>0 那么，取c>=min{c1,c2},当n>=max{n1,n2}时： t 1(n)+ t 2(n)≥c 1g 1(n)+ c 2g 2(n) ≥c g 1(n)+c g 2(n)≥c[g 1(n)+ g 2(n)] ≥cmax{ g 1(n), g 2(n)} 所以以命题成立。 b. t 1(n)+t 2(n) ∈Θ()))(2),(1max(n g n g 证明：由大?的定义知，必须确定常数c1、c2和n0，使得对于所有n>=n0，有： ))(2),(1max()(2)(1))(2),(1max((1n g n g n t n t n g n g c ≤+≤ 由t 1(n)∈Θ(g1(n))知，存在非负整数a1,a2和n1使： a1*g1(n)<=t 1(n)<=a2*g1(n)-----(1) 由t 2(n)∈Θ(g2(n))知，存在非负整数b1,b2和n2使： b1*g2(n)<=t 2(n)<=b2*g2(n)-----(2) (1)+(2): a1*g1(n)+ b1*g2(n)<=t1(n)+t2(n) <= a2*g1(n)+ b2*g2(n) 令c1=min(a1,b1),c2=max(a2,b2)，则 C1*(g1+g2)<= t 1(n)+t 2(n) <=c2(g1+g2)-----(3) 不失一般性假设max(g1(n),g2(n))=g1(n). 显然，g1(n)+g2(n)<2g1(n)，即g1+g2<2max(g1,g2) 又g2(n)>0，g1(n)+g2(n)>g1(n),即g1+g2>max(g1,g2)。 则（3）式转换为： C1*max(g1,g2) <= t 1(n)+t 2(n) <=c2*2max(g1,g2) 所以当c1＝min(a1,b1),c2＝2c2=2max(c1,c2)，n0＝max(n1,n2)时，当n>=n0时上述不等式成立。 证毕。 习题2.4 1. 解下列递推关系 （做a,b ） a. 解： ?? ?=+-=0)1(5)1()(x n x n x 当n>1时 b. 解： 2. 对于计算n!的递归算法F(n)，建立其递归调用次数的递推关系并求解。 解： 3. 考虑下列递归算法，该算法用来计算前n 个立方的和：S(n)=13+23+…+n3。 算法S(n) //输入：正整数n //输出：前n 个立方的和 if n=1 return 1 else return S(n-1)+n*n*n a. 建立该算法的基本操作次数的递推关系并求解 b. 如果将这个算法和直截了当的非递归算法比，你做何评价？ 解： ?? ?=-=4 )1()1(3)(x n x n x 当n>1时 a. 7. a. 请基于公式2n=2n-1+2n-1，设计一个递归算法。当n是任意非负整数的时候，该算法能够计算2n的值。 b. 建立该算法所做的加法运算次数的递推关系并求解 c. 为该算法构造一棵递归调用树，然后计算它所做的递归调用次数。 d. 对于该问题的求解来说，这是一个好的算法吗？ 解: a.算法power(n) //基于公式2n=2n-1+2n-1,计算2n //输入:非负整数n //输出: 2n的值 If n=0 return 1 Else return power(n-1)+ power(n-1) c. ∑=+-==n i n i n C 01122)( 8.考虑下面的算法 算法 Min1(A[0..n-1]) //输入:包含n 个实数的数组A[0..n-1] If n=1 return A[0] Else temp ←Min1(A[0..n-2]) If temp ≤A[n-1] return temp Else return A[n-1] a.该算法计算的是什么? b.建立该算法所做的基本操作次数的递推关系并求解 解: a.计算的给定数组的最小值 b.? ??+-=01 )1()(n C n C 9.考虑用于解决第8题问题的另一个算法,该算法递归地将数组分成两半.我们将它称为Min2(A[0..n-1]) 算法 Min(A[r..l]) If l=r return A[l] Else temp1←Min2(A[l..(l+r)/2]) Temp2←Min2(A[l..(l+r)/2]+1..r) If temp1≤temp2 return temp1 Else return temp2 a.建立该算法所做的的操作次数的递推关系并求解 b.算法Min1和Min2哪个更快?有其他更好的算法吗? 解: a. for all n>1 n=1 习题2.6 1.考虑下面的排序算法,其中插入了一个计数器来对关键比较次数进行计数. 算法SortAnalysis(A[0..n-1]) //input:包含n个可排序元素的一个数组A[0..n-1] //output:所做的关键比较的总次数 count←0 for i←1 to n-1 do v←A[i] j←i-1 while j>0 and A[j]>v do count←count+1 A[j+1]←A[j] j←j+1 A[j+1]←v return count 比较计数器是否插在了正确的位置?如果不对,请改正. 解:应改为: 算法SortAnalysis(A[0..n-1]) //input:包含n个可排序元素的一个数组A[0..n-1] //output:所做的关键比较的总次数 count←0 for i←1 to n-1 do v←A[i] j←i-1 while j>0 and A[j]>v do count←count+1 A[j+1]←A[j] j←j+1 if j>=0 count=count+1 A[j+1]←v return count 习题3.1 4. a.设计一个蛮力算法,对于给定的x 0,计算下面多项式的值: P(x)=a n x n +a n-1x n-1+…+a 1x+a 0 并确定该算法的最差效率类型. b.如果你设计的算法属于Θ(n 2),请你为该算法设计一个线性的算法. C.对于该问题来说,能不能设计一个比线性效率还要好的算法呢? 解: a. Algorithms BruteForcePolynomialEvaluation(P[0..n],x) //由高幂到低幂用蛮力法计算多项式p 在给定点x 的值 //输入:P[0..n]是多项式按低幂到高幂的常系数,以及定值x //输出: 多项式p 在给定点x 的值 p=0.0 for i=n to 0 do power=1 for j=1 to i do power=power*x p=p+P[i]*power return p 算法效率分析: 基本操作:两个数相乘,且M(n)仅依赖于多项式的阶n ∑∑∑===Θ∈+= ==n i n i i j n n n i n M 020 1 )(2 ) 1(1)( b. tha above algorithms is very inefficient, because we recompute powers of x again and again as if there were no relationship among them.In fact ,we can move from the lowest term to the highest and compute x i by using x i-1. Algorithms BetterBruteForcePolynomialEvaluation(P[0..n],x) //由高幂到低幂用蛮力法计算多项式p 在给定点x 的值 //输入:P[0..n]是多项式按低幂到高幂的常系数,以及定值x //输出: 多项式p 在给定点x 的值 P=P[0] power=1 for i←1 to n do power←power*x p←p+P[i]*power return p 基本操作乘法运算总次数M(n): )(22)(1n n n M n i Θ∈==∑= c.不行.因为计算任意一个多项式在任意点x 的值,都必须处理它的n+1 个系数.例如: (x=1,p(x)=a n +a n-1+..+a 1+a 0,至少要做n 次加法运算) 5.应用选择排序对序列example 按照字母顺序排序. 6.选择排序是稳定的吗?(不稳定) 7.用链表实现选择排序的话,能不能获得和数组版相同的Θ(n2)效率? Yes.Both operation—finding the smallest element and swapping it –can be done as efficiently with the linked list as with an array. 9.a.请证明,如果对列表比较一遍之后没有交换元素的位置,那么这个表已经排好序了,算法可以停止了. b.结合所做的改进,为冒泡排序写一段伪代码. c.请证明改进的算法最差效率也是平方级的. Hints: a.第i趟冒泡可以表示为: 如果没有发生交换位置,那么: b.Algorithms BetterBubblesort(A[0..n-1]) //用改进的冒泡算法对数组A[0..n-1]排序 //输入:数组A[0..n-1] //输出:升序排列的数组A[0..n-1] count←n-1 //进行比较的相邻元素对的数目 flag←true //交换标志 while flag do flag←false for i=0 to count-1 do if A[i+1] swap(A[i],A[i+1]) flag←true count←count-1 c最差情况是数组是严格递减的,那么此时改进的冒泡排序会蜕化为原来的冒泡排序. 10.冒泡排序是稳定的吗?(稳定) 习题3.2 1.对限位器版的顺序查找算法的比较次数: a.在最差情况下 b.在平均情况下.假设成功查找的概率是p(0<=p<=1) Hints: a.C worst(n)=n+1 b.在成功查找下,对于任意的I,第一次匹配发生在第i个位置的可能性是p/n,比较 次数是i.在查找不成功时,比较次数是n+1,可能性是1-p. 6.给出一个长度为n的文本和长度为m的模式构成的实例,它是蛮力字符串匹配算法的一个最差输入.并指出,对于这样的输入需要做多少次字符比较运算. Hints: 文本:由n个0组成的文本 模式:前m-1个是0,最后一个字符是1 比较次数: m(n-m+1) 7.为蛮力字符匹配算法写一个伪代码,对于给定的模式,它能够返回给定的文本中所有匹配子串的数量. Algorithms BFStringmatch(T[0..n-1],P[0..m-1]) //蛮力字符匹配 //输入:数组T[0..n-1]—长度为n的文本,数组P[0..m-1]—长度为m的模式 //输出:在文本中匹配成功的子串数量 count←0 for i←0 to n-m do j←0 while j j←j+1 if j=m count←count+1 return count 8.如果所要搜索的模式包含一些英语中较少见的字符,我们应该如何修改该蛮力算法来利用这个信息. Hint:每次都从这些少见字符开始比较,如果匹配, 则向左边和右边进行其它字符的比较. 习题4.1 1.a.为一个分治算法编写伪代码,该算法求一个n个元素数组中最大元素的位置. b.如果数组中的若干个元素都具有最大值,该算法的输出是怎样的呢? c.建立该算法的键值比较次数的递推关系式并求解. d.请拿该算法与解同样问题的蛮力算法做一个比较 解:a. Algorithms MaxIndex(A[l..r]){ Input:A portion of array A[0..n-1] between indices l and r(l≤r) Output: The index of the largest element in A[l..r] if l=r return l else temp1←MaxIndex(A[l..(l+r)/2]) tem p2←MaxIndex(A[(l+r)/2..r]) if A[temp1]≥A[temp2] return temp1 else return temp2 } b.返回数组中位于最左边的最大元素的序号. c.键值比较次数的递推关系式: C(n)=C( n/2 )+C( n/2 )+1 for n>1 C(1)=0 设n=2k，C(2k)=2C(2k-1)+1 =2[2 C(2k-2)+1]+1=22C(2k-2)+2+1 =2[22C(2k-3)+1]+2+1=23C(2k-3)+ 22+2+1 =... =2i C(2k-i)+ 2i-1+2 i-2 +...+2+1 =... =2k C(2k-k)+ 2k-1+2 k-2 +...+2+1=2k－1=n-1 可以证明C(n)=n-1对所有n>1的情况都成立（n是偶数或奇数） d.比较的次数相同，但蛮力算法不用递归调用。 2、a.为一个分治算法编写伪代码，该算法同时求出一个n元数组的最大元素和最小元素的值。 b.请拿该算法与解同样问题的蛮力算法做一个比较。 c.请拿该算法与解同样问题的蛮力算法做一个比较。 解答： a.同时求出最大值和最小值，只需要将原数组一分为二，再使用相同的方法找出这两个部分中的最大值和最小值，然后经过比较就可以得到整个问题的最大值和最小值。 算法MaxMin(A[l..r],Max,Min) //该算法利用分治技术得到数组A中的最大值和最小值 //输入：数值数组A[l..r] //输出：最大值Max和最小值Min if(r=l) Max←A[l]；Min←A[l]; //只有一个元素时 else if r－l=1 //有两个元素时 if A[l]≤A[r] Max←A[r]; Min←A[l] else Max←A[l]; Min←A[r] else //r－l>1 MaxMin(A[l,(l+r)/2],Max1,Min1); //递归解决前一部分 MaxMin(A[(l+r/)2..r],Max2,Min2); //递归解决后一部分 if Max1＜Max2 Max= Max2 //从两部分的两个最大值中选择大值 if Min2 } b.假设n=2k,比较次数的递推关系式: C(n)=2C(n/2)+2 for n>2 C(1)=0, C(2)=1 C(n)=C(2k)=2C(2k-1)+2 =2[2C(2k-2)+2]+2 =22C(2k-2)+22+2 =22[2C(2k-3)+2]+22+2 =23C(2k-3)+23+22+2 ... =2k-1C(2)+2k-1+2k-2+...+2 //C(2)=1 =2k-1+2k-1+2k-2+...+2 //后面部分为等比数列求和 =2k-1+2k-2 //2(k-1)=n/2,2k=n =n/2+n-2 =3n/2－2 b.蛮力法的算法如下： 算法simpleMaxMin(A[l..r]) //用蛮力法得到数组A的最大值和最小值 //输入：数值数组A[l..r] //输出：最大值Max和最小值Min Max=Min=A[l]; for i=l+1 to r do if A[i]>Max Max←A[i]; else if A[i] return Max,Min } 时间复杂度t(n)=2(n-1) 算法MaxMin的时间复杂度为3n/2-2，simpleMaxMin的时间复杂度为2n-2，都属于Θ(n)，但比较一下发现，MaxMin的速度要比simpleMaxMin的快一些。 6.应用合并排序对序列E,X,A,M,P,L,E按字母顺序排序. 1 2 3 8.a.对合并排序的最差键值比较次数的递推关系式求解.(for n=2k) b.建立合并排序的最优键值比较次数的递推关系式求解.(for n=2k) c.对于4.1节给出的合并排序算法,建立它的键值移动次数的递推关系式.考虑了该算法的键值移动次数之后,是否会影响它的效率类型呢? 解: a.递推关系式见4.1节. b.最好情况(列表升序或降序)下: C best(n)=2C best(n/2)+n/2 for n>1 (n=2k) C best(1)=0 c.键值比较次数M(n) M(n)=2M(n)+2n for n>1 M(1)=0 习题4.2 1.应用快速排序对序列E,X,A,M,P,L,E按字母顺序排序 4.请举一个n个元素数组的例子,使得我们有必须对它使用本节提到的”限位器”.限位 器的值应是多少年来?为什么一个限位器就能满足所有的输入呢? Hints: With the pivot being the leftmost element, the left-to-right scan will get out of bounds if and only if the pivot is larger than the other elements. Appending a sentinel(限位器) of value equal A[0](or larger than A[0]) after the array’s last element , the quicksort algorithms will stop the index of the left-to-right scan of A[0..n-1] from going beyond position n. 8.设计一个算法对n个实数组成的数组进行重新排列,使得其中所有的负元素都位于正元素之前.这个算法需要兼顾空间和时间效率. Algorithms netbeforepos(A[0..n-1]) //使所有负元素位于正元素之前 //输入:实数组A[0..n-1] //输出:所有负元素位于于正元素之前的实数组A[0..n-1] A[-1]←-1; A[n]←1 //限位器 i←0; j←n-1 While i While A[i]≤0 do i←i+1 while A[j]≥0 do j←j-1 swap A[i]and A[j] swap A[i]and A[j] //undo the last swap 当全是非负数或全是非正数时需要限位器. 习题4.3 1.(题略) 解: a.由公式4.4得:4次 b.二分查找判定树: 所以,14,31,42,74,85,98需要比较4次 c. 2.313 4164131431312213111131≈=??+??+??+??=yes avg C d. 9.314 5412414123141≈=??+??=no avg C 2. 当n=2k 时,用反向替换法求下面的递推方程: 当n>1时, C w (n)=C w (n/2)+1, C w (1)=1 (略) 4.如果对于一个100000个元素的数组成功查找的话,使用折半查找比顺序查找要快多少倍? 6． 如何将折半查找应用于范围查找?范围查找就是对于一个有序数组,找出位于给定值L 、U 之间（包含L 、U ）的所有元素，L<=U 。该算法的最差效率是多少？ Hints: Step1: 检查A[0]≤L ，A[n-1]≥U 是否成立，若不成立，则无解。否则进入step 2 Step2:在数组A 中用二分查找法查找值L ，如果查找成功，则返回数组下标m ，否则l 二分查找结束时的值. Step3: 在数组A 中用二分查找法查找值U ，如果查找成功，则返回数组下标m ，否则r 为二分查找结束时的值. 最后，结果就是在数组序号范围在low 和high （包含low,high ）之间的范围。（low 和high 是step2和step3的值。） 7． 为折半查找写递归的伪代码。 Algorithms BSR(A[o..n-1],K) //折半查找递归算法 //有序子数组A[l ..r]和查找键值K //查找成功则输出其下标，否则输出-1 if l>r return -1 else m← (l+r)/2 if K=A[m] return m else if K< A[m] return BSR(A[l..m-1],K) else if K> A[m] return BSR(A[m+1,r],K) 8.设计一个只使用两路比较的折半查找算法，即只用≤和=, 或者只用≥和=. Algorithms TwoWaysBinarySearch(A[o..n-1],K) //二路比较的折半查找 //有序子数组A[l..r]和查找键值K //查找成功则输出其下标，否则输出-1 l←0, r←n-1 while l m← (l+r)/2 if K≤A[m] r←m else l←m+1 if K=A[l] return l else return -1 习题4.4 1.设计一个分治算法来计算二叉树的层数.(空树返回0,单顶点树返回1),并分析效率类型. Algorithms Level(Tree T) //递归计算二叉树的层数 //输入:二叉树T //输出:二叉树T的层数 If T=NULL return 0 Else return max{Level(T L),Level(T R)}+1 算法效率类型是Θ(n)(同4.4节算法height(T)) 2.选择一个二叉树的经典遍历算法(前\中\后序),写出它的递归伪代码,并求它的递归调用次数. Algorithms preorder(T) //先序遍历二叉树T //输入: 二叉树T //输出:先序遍历的结点序列表 If T≠NULL Visit T’s root Preorder(T L) Preorder(T R) 递归调用次数C(n)=扩展树中内部结点+外部结点=n+(n+1) =2n+1 7.设计一个算法计算有根有序树的高度. Algorithms height(T) //递归计算有根有序树的高度 //输入:一棵有根有序树的高度T //输出:T的高度 i=NumChildren(T) //根的孩子个数 if i=0 return 0 else return max{height(T1),height(T2),…,height(T i)}+1 8.下面的算法试图计算一棵二叉树中叶子的数量 Algorithms LeafCount(T) //递归计算二叉树中叶子的数量 //输入:一棵二叉树 //输出:T中叶子的数量 if T=NULL return 0 else return LeafCount(T L)+LeafCount(T R) 应为: if T=NULL return 0 //empty tree else if T L =NULL AND T R=NULL return 1 //single-node tree else return LeafCount(T L)+LeafCount(T R) //general case 习题4.6 1.a.为最近对问题的一维版本设计一个直接基于分治技术的算法,并确定它的效率类型 b.对于这个问题,它是一个好算法吗? 解: a.Algorithms ClosestNumber(A[l..r]) //分治计算最近对问题的一维版本 //输入:升序排列的实数子数组A[l..r] //输出:最近数对的距离 If r=l return ∞ Else if r－l=1 return A[r]－A[l] Else return min{ClosestNumber(A[l… (l+r)/2 ]), ClosestNumber(A[ (l+r)/2 ...r]) A[ (l+r)/2 +1]－A[ (l+r)/2 ]