《算法分析与设计：作业.ppt》由会员分享，可在线阅读，更多相关《算法分析与设计：作业.ppt（15页珍藏版）》请在三一办公上搜索。
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算法解：算法 Euclid(m,n)/求两个不全为0的
2、非负整数的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.解一个1000个方程联立的方程组比解一个500个方程联立的方程组要多运行
3、多少时间？解：设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)表示第一步爬一格梯子的爬法，C(n-2)表示第一步爬二格梯子的爬法，所以有C(n)=C(n-1)
4、+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)count n-1 flag true while flag flag false for j 0 to count-1
5、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=996c.每次循环，比较2次，总次数=2996=1992,习题3.2-6，P82,6.设文本T长度为n，模式P长度为m，给出一个蛮力字符串匹配最差的
6、实例，并指出精确的比较次数解：令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，每次循环比较1次，0的滑动距离=1，所以总次数=1000-5+1=996b.ShiftTable=14-0=4;01，每次循环比较5次，0的滑动距离=1，总次数=(1000-
7、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，但不明确使用n的二进制表现形式解：product 1 term a while n0 do b n mod 2 n n/2 if b=1 product product*term term term*term return product,
