计算方法实验1.doc

实 验 报 告 课程名称： 算法设计与分析 实验项目： 算法设计与分析 姓 名： 李守家 专 业： 计算机科学与技术 班 级： 计09-2 学 号： 0904010215 计算机科学与技术学院 实验教学中心 2011年 11月 3日  实验项目名称: 猴子爬山问题 实验目的 用C语言或C++语言编程实现猴子爬山问题。 实验内容 1.一个顽猴在一座有30级台阶的小山上爬山跳跃，猴子上山一步可跳1级，或跳3级，试求上山的30级台阶有多少种不同的爬法。 2.扩展：把问题引申为爬山n级，一步有m种跨法，一步跨多少级从键盘输入。 分级递推算法设计 设爬山t台阶级的不同爬法为f(t)，设从键盘输入一步跨多少级的m个整数分别为x(1)，x(2)，…，x(m)（约定x(1)x(2)…x(m)x(m)n）。 这里的整数x(1)，x(2)，…，x(m)为键盘输入，事前并不知道，因此不能在设计时简单地确定f(x(1))，f(x(2))，…。 事实上，可以把初始条件放在分级递推中求取，应用多关系分级递推算法(6)完成递推。 首先探讨f(t)的递推关系： 当tx(1)时，f(t)=0；f(x(1))=1。（初始条件） 当x(1)t=x(2)时，第1级递推：f(t)=f(t-x(1))； 当x(2)t=x(3)时，第2级递推：f(t)=f(t-x(1))+f(t-x(2))； …… 一般地，当x(k)t=x(k+1)，k=1，2，…m-1，有第k级递推： f(t)=f(t-x(1))+f(t-x(2))+…+f(t-x(k)) 当x(m)t时，第m级递推： f(t)=f(t-x(1))+f(t-x(2))+…+f(t-x(m)) 当t=x(1)，或t=x(2)，…，或t=x(m)时，按上递推求f(t)外，还要加上1。道理很简单，因为此时t本身即为一个一步到位的爬法。为此，应在以上递推基础上添加： f(t)=f(t)+1 (t=x(2)，x(3)，…，x(m)) 我们所求的目标为： f(n)=f(n-x(1))+f(n-x(2))+…+f(n-x(m)) 这一递推是我们设计的依据。 在递推设计中我们可把台阶数n记为数组元素x(m+1)，这样处理是巧妙的，可以按相同的递推规律递推计算，简化算法设计。最后一项f(x(m+1)即为所求f(n)。 最后输出f(n)即f(x(m+1)时必须把额外所添加的1减去。以上分级递推算法是新颖的，其时间复杂度O(nm)，空间复杂度为O(n)。 实验步骤 这一问题实际上是一个整数有序可重复拆分问题，试应用数组递推求解。 设爬k级台阶的不同爬法为f(k)种，首先探求f(k)的递推关系。 上山最后一步到达第30级台阶，完成上山，共有f(30)种不同的爬法：到第30级之前位于哪一级呢？无非是位于第29级（上跳1级即到），有f(29)种：或位于第27级（上跳3级即到），有f(27)种：于是 f(30)=f(29)+f(27) 依此类推，一般地有递推关系： f(k)=f(k-1)+f(k-3) (k3) 初始条件： f(1)=1；即1=1 f(2)=1；即2=1+1 f(3)=2；即3=1+1+1；3=3 根据以上递推关系与初始条件，设置一重循环应用递推模式(1)即可求出f(n)。 实验结果 1. 2. 程序代码 1. #includestdio.h void main() { int k,n;long f[1000]; printf（“请输入台阶总数n：”）； scanf(“%d”,n); f[1]=1;f[2]=1;f[3]=2; /*数组元素赋初值*/ for (k=4;k=n;k++) f[k]=f[k-1]+f[k-3]; /*按递推关系实施递推*/ printf(“s=%ld”,f[n]); } 2. #includestdio.h void main() { int i，j，k，m，n，t，x[10]； long f[200]； printf(“请输入总台阶数：”)； scanf(“%d”,n)； /*输入台阶数*/ printf(“一次有几种跳法：”)； scanf(“%d”,m)； printf(“请从小到大输入一步跳几级。\n”)； for (i=1；i=m；i++) /*输入m个一步跳级数*/ { printf(“第%d个一步可跳级数：”，i)； scanf(“%d”，x[i])； for (i=1；i=x[1]-1；i++) f[i]=0；/*确定初始条件*/ x[m+1]=n