算法设计与分析习题

《算法设计与分析习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法设计与分析》习题第一章算法引论1、算法的定义？答：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。通俗讲，算法：就是解决问题的方法或过程。2、算法的特征？答：1)算法有零个或多个输入；２)算法有一个或多个输出；3)确定性；４)有穷性3、算法的描述方法有几种？答：自然语言、图形、伪代码、计算机程序设计语言4、衡量算法的优劣从哪几个方面？答：(1)算法实现所耗费的时间（时间复杂度）；(2)算法实现所所耗费的存储空间（空间复杂度）；(3)算法应易于理解，易于编码，易于调试等等。5、时间复杂度、空间复杂度定义？答：指的是算法在运行过程中所需要的

2、资源（时间、空间）多少。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、设计算法：

3、　　递归法：汉诺塔问题？兔子序列（上楼梯问题）？　　整数划分问题？　　蛮力法：百鸡百钱问题？倒推法：穿越沙漠问题？答：算法如下：（1）递归法l汉诺塔问题voidhanoi(intn,inta,intb,intc){if(n>0){hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);}}l兔子序列（fibonaci数列）递归实现：IntF(intn){if(n<=2)return1;elsereturnF(n-1)+F(n-2);}l上楼梯问题IntF(intn){if(n=1)return1if(n=2)return2;else

4、returnF(n-1)+F(n-2);}l整数划分问题问题描述：将正整数n表示成一系列正整数之和，n=n1+n1+n3+…将最大加数不大于m的划分个数，记作q(n,m)。正整数n的划分数p(n)=q(n,n)。可以建立q(n,m)的如下递归关系：递归算法：Intq(intn,intm){if(n<1

5、

6、m<1)return0;If((n=1)

7、

8、(m=1))return1;If(n

9、，z分别为公鸡、母鸡、小鸡的数量。约束条件：x+y+z=100且5*x+3*y+z/3=100main(){intx,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+zand100=5*x+3*y+z/3)   {　print(thecocknumberis",x)；print(thehennumberis",y)；　　　　print(thechicknumberis"z);}}算法分析：以上算法需要枚举尝试20*34*100=68000次

10、。算法的效率显然太低算法设计2：在公鸡（x）、母鸡（y）的数量确定后，小鸡 的数量 z就固定为100-x-y，无需再进行枚举了。 此时约束条件只有一个：5*x+3*y+z/3=100main(){ intx,y,z;    for(x=1;x<=20;x=x+1)                      for(y=1;y<=33;y=y+1)                  { z=100-x-y;                     if(zmod3=0and5*x+3*y+z/3=100)                               

11、                {print(thecocknumberis",x)；print(thehennumberis",y)；　　　　print(thechicknumberis"z);}        }}算法分析：以上算法只需要枚举尝试20*33=660次。实现时约束条件又限定Z能被3整除时，才会判断“5*x+3*y+z/3=100”。这样省去了z不整除3时的算术计算和条件判断，进一步提高了算法的效率。(3)倒推法：穿越沙漠问题desert（）{intdis，k，oil,k;//dis表示距终点的距离，k表示贮油点从后到前的序号dis=500;k=1

12、;oil=