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

算法分析与设计 作业 计算机学院刘在德 习题1 1 6 P6 6 证明等式gcd m n gcd n mmodn 对每一对正整数都成立证明 m可以表示成m kn r 则r mmodn假设d是m n的一个公约数 则有d m d n 而r m kn 因此d r因此d是 n mmodn 的公约数假设d是 n mmodn 的公约数 则d n d r 但是m kn r因此d也是 m n 的公约数因此 m n 和 n mmodn 的公约数是一样的 其最大公约数也必然相等 得证 习题1 1 9 P6 9 用减法实现Euclidean算法解 算法Euclid m n 求两个不全为0的非负整数的GCDifm 0returnnifn 0returnmwhilem ndoifm nm m nifm nn n mreturnm 习题1 2 5 P13 5 写出十进制正整数转换为二进制整数的算法解 算法Binary n 输入 十进制正整数n 输出 bkbk 1 b1b0k 0whilen 0bk nmod2n n 2 k k 1 习题2 1 7 P39 7 Gaussian消去法用于求解n个n元线性方程联立的方程组 乘法是其基本操作 且大约需要n3 3乘法运算 问a 解一个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 5 4 P64 4 爬梯子 假设每一步可以爬一格或者两格梯子 爬一部n格梯子一共有几种爬法 解 令C n 表示总的爬法 则C n 1 表示第一步爬一格梯子的爬法 C n 2 表示第一步爬二格梯子的爬法 所以有C n C n 1 C n 2 n 2C 1 1 C 2 2解之得C n F n 1 这里F n 表示Fibonacci数列 习题2 5 6 P65 6 改进迭代算法Fib 使它仅需要 1 的额外空间算法Fib n a 0 b 0fori 2tondob b aa b aifn 0return0elsereturnb 习题3 1 9 b P79 9 b 改进冒泡排序 使之在对列表比较一遍后没有交换元素的情况下停止解 算法BubbleSort A 0 n 1 count n 1flag truewhileflagflag falseforj 0tocount 1ifA j 1 A j swap A j A j 1 flag truecount count 1 习题3 2 5 P82 5 用蛮力字符串匹配算法在1000个0组成的文本中查找下列模式需做多少次比较 a 00001b 10000c 01010解 文本T长度n 1000 模式P长度m 5 对于三种情况匹配都失败 所以外层循环执行次数为n m 1 996 从而有a 每次循环 比较5次 总次数 5 996 4980b 每次循环 比较1次 总次数 1 996 996c 每次循环 比较2次 总次数 2 996 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 当m n时 有C n nm 习题7 2 3 P201 3 文本T为1000个0 模式P分别为a 00001b 10000c 01010用Horspool算法进行匹配 求总比较次数解 由题意知 三种情况匹配都不成功 因此有a ShiftTable 0 4 3 1 1 5 每次循环比较1次 0的滑动距离 1 所以总次数 1000 5 1 996b ShiftTable 1 4 0 4 0 1 每次循环比较5次 0的滑动距离 1 总次数 1000 5 1 5 4980c ShiftTable 0 4 2 2 1 1 每次循环比较2次 0的滑动距离 2 所以总次数 1000 5 1 2 2 996 4 应用Horspool算法在一个长度为n的文本中查找长度为m的模式 给出最差和最优输入的例子解 最差输入 令T为长度为n个0的字符串 P的第1个字符为1 后m 1个字符为0 则ShiftTable 0 1 1 m 1 此时总的比较次数最多 结果为C n m n m 1 当m n时 有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 1term awhi