发布时间 : 星期二 文章算法设计与分析习题 - 图文更新完毕开始阅读4a2af42ba300a6c30c229f7f
《算法设计与分析》习题
第一章算法引论
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)的如下递归关系： 1n?1,m?1??
q(n,n)n?m?q( n,m)??1?q(n,n?1)n?m?
?n?m?1?q(n,m?1)?q(n?m,m)
递归算法：
Int q( int n, int m){
if(n<1||m<1) return 0; If((n=1)||(m=1)) return 1; If (n return q(n,m-1)+q(n-m,m); } （2） 蛮力法：百鸡百钱问题 算法设计1： 设x，y，z分别为公鸡、母鸡、小鸡的数量。 约束条件： x+y+z=100 且 5*x+3*y+z/3=100 main( ) { int x,y,z; for(x=1;x<=20;x=x+1) for(y=1;y<=34;y=y+1) for(z=1;z<=100;z=z+1) if(100=x+y+z and 100=5*x+3*y+z/3) { print(the cock number is\； print(the hen number is\； print(the chick number is \} 算法分析：以上算法需要枚举尝试20*34*100=68000次。算法的效率显然太低 算法设计2： 在公鸡（x）、母鸡（y）的数量确定后，小鸡 的数量 z就固定为100-x-y，无需再进行枚举了 。 此时约束条件只有一个： 5*x+3*y+z/3=100 main( ) { int x,y,z; for(x=1;x<=20;x=x+1) for(y=1;y<=33;y=y+1) { z=100-x-y; if(z mod 3=0 and 5*x+3*y+z/3=100) {print(the cock number is\； print(the hen number is\； print(the chick number is \ } } 算法分析：以上算法只需要枚举尝试20*33=660次。实现时约束条件又限定Z能被3整除时，才会判断“5*x+3*y+z/3=100”。这样省去了z不整除3时的算术计算和条件判断，进一步提高了算法的效率。 (3) 倒推法：穿越沙漠问题 desert（ ） { int dis，k，oil,k; // dis表示距终点的距离，k表示贮油点从后到前的序号 dis=500;k=1;oil=500; //初始化 while ( dis<1000) { print(“storepoint”,k,”distance”, 1000-dis,”oilquantity”,oil) //1000- dis则表示距起点的距离， k=k+1; //k表示储油点从后到前的序号 dis=dis+500/(2*k-1); oil= 500*k; } print(“storepoint”,k,”distance”,dis,”oilquantity”,oil)； } 第二章 分治算法 1、分治算法基本思想是什么？ 适合用分治算法解决的问题，一般具有几个特征？ 分治算法基本步骤是什么？ 答：1) 基本思想:将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 2) 特征： ? 该问题的规模缩小到一定的程度就可以容易解决; ? 该问题可以分解为若干个规模较小的相同子问题，即该问题具有最优子结构性质； ? 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 ? 4)利用该问题分解出子问题解可以合并为该问题解; 3）基本步骤： 分解、求小问题解、合并 2、改写二分查找算法：设a[1?n]是一个已经排好序的数组，改写二分查找算法: ? 当搜索元素x不在数组中时，返回小于x的最大元素位置i，和大于x的最小元素位置j； (即返回x的左、右2个元素) ? 当搜索元素x在数组中时，i和j相同，均为x在数组中的位置。 并计算其时间复杂度？ 答： ３、设计一个合并排序的算法？（分治法解） 并计算其时间复杂度？(要求写出递推