算法分析与设计：作业.ppt

1、算法分析与设计：作业,计算机学院 刘在德,习题1.16，P6,6. 证明等式gcd(m, n)=gcd(n, m mod n)对每一对正整数都成立 证明：m可以表示成m = kn+r，则r = m mod n假设d是m, n的一个公约数，则有d|m, d|n，而r = m-kn，因此d|r因此d是(n, m mod n)的公约数假设d是(n, m mod n)的公约数，则d|n，d|r，但是m = kn+r因此d也是(m, n)的公约数因此(m, n)和(n, m mod n)的公约数是一样的，其最大公约数也必然相等，得证,习题1.1-9，P6,9. 用减法实现Euclidean算法 解：算法

2、 Euclid(m, n) /求两个不全为0的非负整数的GCD if m=0 return n if n=0 return m while mn do if mn m - m-n if mn n = n-m return m,习题1.25，P13,5. 写出十进制正整数转换为二进制整数的算法 解：算法 Binary(n) /输入：十进制正整数n /输出：bkbk-1b1b0 k 0 while n 0 bk n mod 2 n n/2 k k+1,习题2.17，P39,7. Gaussian消去法用于求解n个n元线性方程联立的方程组. 乘法是其基本操作，且大约需要n3/3乘法运算. 问a. 解

3、一个1000个方程联立的方程组比解一个500个方程联立的方程组要多运行多少时间？ 解：设cM是一次乘法运行的时间，则T(n) cMn3/3，T(2n) cM(2n)3/3，所以T(2n)/T(n) 8,b. 新机器比旧机器运算速度快1000倍，假设两台机器的运行时间相同，问新旧机器的运算规模有什么变化 解：Told cMn3/3，Tnew 10-3cMN3/3因为Told = Tnew，所以有cMn3/3 10-3cMN3/3从而有N/n 10,习题2.54，P64,4. 爬梯子. 假设每一步可以爬一格或者两格梯子，爬一部n格梯子一共有几种爬法？ 解：令C(n)表示总的爬法，则C(n-1)表示

4、第一步爬一格梯子的爬法，C(n-2)表示第一步爬二格梯子的爬法，所以有C(n) = C(n-1)+C(n-2), n2C(1) = 1, C(2) = 2解之得C(n) = F(n+1)，这里F(n)表示Fibonacci数列,习题2.56，P65,6. 改进迭代算法Fib，使它仅需要(1)的额外空间 算法 Fib(n) a 0, b 0 for i 2 to n do b b+a a b-a if n=0 return 0 else return b,习题3.19.b，P79,9.b. 改进冒泡排序，使之在对列表比较一遍后没有交换元素的情况下停止 解：算法 BubbleSort(A0.n-1

5、) count n-1 flag true while flag flag false for j 0 to count-1 if Aj+1Aj swap(Aj, Aj+1) flag true count count-1,习题3.2-5，P82,5. 用蛮力字符串匹配算法在1000个0组成的文本中查找下列模式需做多少次比较？a. 00001 b. 10000 c. 01010 解：文本T长度n=1000，模式P长度m=5，对于三种情况匹配都失败，所以外层循环执行次数为n-m+1=996，从而有a. 每次循环，比较5次，总次数=5996=4980b. 每次循环，比较1次，总次数=1996=99

6、6c. 每次循环，比较2次，总次数=2996=1992,习题3.2-6，P82,6. 设文本T长度为n，模式P长度为m，给出一个蛮力字符串匹配最差的实例，并指出精确的比较次数 解：令T为长度为n个0的字符串，P的前m-1个字符为0，第m个字符为1，此时总的比较次数最多，结果为C(n)=m(n-m+1)，当mn时，有C(n)(nm),习题7.2-3，P201,3. 文本T为1000个0，模式P分别为a. 00001 b. 10000 c. 01010用Horspool算法进行匹配，求总比较次数 解：由题意知，三种情况匹配都不成功，因此有a. ShiftTable=04-3=1; 15，每次循环比

7、较1次，0的滑动距离=1，所以总次数=1000-5+1=996b. ShiftTable=14-0=4; 01，每次循环比较5次， 0的滑动距离=1，总次数=(1000-5+1)5=4980c. ShiftTable=04-2=2; 11，每次循环比较2次， 0的滑动距离=2 ，所以总次数=(1000-5+1)/22=996,4.应用Horspool算法在一个长度为n的文本中查找长度为m的模式。给出最差和最优输入的例子 解：最差输入：令T为长度为n个0的字符串，P的第1个字符为1，后m-1个字符为0， 则ShiftTable=01; 1m-1，此时总的比较次数最多，结果为C(n)=m(n-m+1)，当mn时，有C(n)(n2) 最优输入： T为长度为n个0的字符串，P为长度为m的0串，比较次数为m,5. 相同的文本和模式，Horspool算法的比较次数是否有可能多于蛮力算法？举例说明 解：有可能。例如令T为长度为n个0的字符串，P的第1个字符为1，后m-1个字符为0， Horspool算法比较m(n-m+1)次 蛮力法比较n-m+1次,习题6.5-8，P180,8. 改进从右到左二进制幂算法计算an，