算法设计与分析习题

本文档如对你有帮助，请帮忙下载支持！《算法设计与分析》习题第一章算法引论1、 算法的定义？答：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。通俗讲，算法：就是解决问题的方法或过程。2、 算法的特征？答： 1) 算法有零个或多个输入；２) 算法有一个或多个输出； 3) 确定性； ４) 有穷性3、 算法的描述方法有几种？答：自然语言、图形、伪代码、计算机程序设计语言4、 衡量算法的优劣从哪几个方面？答： (1) 算法实现所耗费的时间（时间复杂度）； (2) 算法实现所所耗费的存储空间（空间复杂度）； (3) 算法应易于理解，易于编码，易于调试等等。5、 时间复杂度、空间复杂度定义？答：指的是算法在运行过程中所需要的资源（时间、空间）多少。6、时间复杂度计算： {i=1； while（i<=n ） i=i*2； } 答：语句①执行次数1 次，语句②③执行次数f(n), 2^f(n)<=n,则 f(n) <=log2n; 算法执行时间： T(n)= 2log2n +1 时间复杂度：记为O(log2n) ；7. 递归算法的特点？答：①每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算；（递归终止条件）②递归中用较小自变量函数值来表达较大自变量函数值；（递归方程式）8、算法设计中常用的算法设计策略？答：①蛮力法；②倒推法；③循环与递归；④分治法；⑤动态规划法；⑥贪心法；⑦回溯法；⑧分治限界法9、设计算法 ：递归法：汉诺塔问题？兔子序列（上楼梯问题）？整数划分问题？蛮力法：百鸡百钱问题？倒推法：穿越沙漠问题？答：算法如下：（1）递归法汉诺塔问题void hanoi(int n, int a, int b, int c) {if (n > 0) { hanoi(n-1, a, c, b); move(a,b); 本文档如对你有帮助，请帮忙下载支持！ hanoi(n-1, c, b, a); } }兔子序列（ fibonaci数列 ）递归实现：Int F(int n) { if(n<=2) return 1; else return F(n-1)+ F(n-2); } 上楼梯问题Int F(int n) { if(n=1) return 1 if(n=2) return 2; else return F(n-1)+ F(n-2); } 整数划分问题问题描述：将正整数n 表示成一系列正整数之和，n=n1+n1+n3+⋯将最大加数不大于m 的划分个数，记作q(n,m) 。正整数n 的划分数p(n)=q(n,n)。 可以建立 q(n,m) 的如下递归关系：递归算法：Int q( int n, int m){ if(n<1||m<1) return 0; If((n=1)||(m=1)) return 1; If (n