递推算法分析上课讲义.ppt

《递推算法分析上课讲义.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、递推算法分析2.递推关系递推算法的首要问题是得到相邻的数据项之间的关系，即递推关系。递推关系是一种高效的数学模型，是递推应用的核心。递推关系不仅在各数学分支中发挥着重要的作用，由它所体现出来的递推思想在各学科领域中更是显示出其独特的魅力。求解方法找规律：a[1]=1a[2]=1a[3]=2=1+1=a[1]+a[2]a[4]=3=1+2=a[2]+a[3]a[5]=5=2+3=a[3]+a[4]a[6]=8=3+5=a[4]+a[5]则有：a[n]=a[n-2]+a[n-1]，a[1]=1,a[2]=1有了这个递推方程，程序就很简单了。例：求斐波那契数列：1、1、2

2、、3、5、8、……的第n项。3.递推的实施步骤（1）确定递推变量递推变量可以是简单变量，也可以是一维或多维数组。（2）建立递推关系递推关系是递推的依据，是解决递推问题的关键。（3）确定初始（边界）条件根据问题最简单情形的数据确定递推变量的初始（边界）值，这是递推的基础。（4）对递推过程进行控制递推过程控制：递推在什么时候结束，满足什么条件结束。4.递推算法框架描述（1）简单顺推算法顺推即从前往后推，从已求得的规模为1,2,…,i-1的一系列解，推出问题规模为i的解，直至得到规模为n的解：f(1—i-1)=<初始值>；//确定初始值for(k=i;k<=n;k++)f

3、(k)=<递推关系式>；//根据递推关系实施顺推print(f(n))；//输出n规模的解f(n)（2）简单逆推算法逆推即从后往前推，从已求得的规模为n,n−1,…,i+1的一系列解，推出问题规模为i的解，直至得到规模为1的解：f(n—i+1)=<初始值>；//确定初始值for(k=i;k>=1;k--)f(k)=<递推关系式>；//实施逆推print(f(1))；（3）较复杂的递推问题需设置多重循环递推。例1：求斐波那契数列：1、1、2、3、5、8、……的第n项。问题分析：斐波那契数列具有下列递推关系a[n]=a[n-2]+a[n-1]，a[1]=1,a[2]=1

4、，q且其中n>=3算法描述：intfib(intn){inti,f1=1,f2=1,f;for(i=3;i<=n;i++){f=f1+f2;f1=f2;f2=f;}if(n==1

5、

6、n==2)return1;elsereturnf;}}二、递推算法实例1、输出斐波那契数列：1、1、2、3、5、8、……的前n项。（每行输出10个数）2、求斐波那契数列：1、1、2、3、5、8、……的前n项的和。思考：二、递推算法实现实例例2：求n！。算法描述：intfact(intn){inti,s=1;for(i=1;i<=n;i++)s=s*i;returns;}二、递推算法实现例

7、3：求n！。算法描述：intfact(intn){inti,s=1;for(i=1;i<=n;i++)s=s*i;returns;}三、案例分析3.1猴子爬山案例提出：一个顽猴在一座有30级台阶的小山上爬山跳跃，猴子上山一步可跳1级，或跳3级，试求上山的30级台阶有多少种不同的爬法。设爬k级台阶的不同爬法为f(k)种。（1）探求f(k)的递推关系。上山最后一步到达第30级台阶，共有f(30)种不同的爬法；到第30级之前位于哪一级呢？无非是位于第29级（上跳1级即到），有f(29)种；或位于第27级（上跳3级即到），有f(27)种；于是有f(30)=f(29)+f(2

8、7)一般地有递推关系：f(k)=f(k-1)+f(k-3)（k>3）（2）确定初始条件f(1)=1；即1=1;f(2)=1；即2=1+1;f(3)=2；即3=1+1+1；3=31.算法分析2.算法描述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("%d",f[n]);3.2水手分椰子案例提出五个水手来到一个岛上，采了一堆椰子。一段时间后，第一个水手醒来，悄悄地将椰子等分成五份，多出一个椰子，便给

9、了旁边的猴子，然后自己藏起一份，再将剩下的椰子重新合在一起。不久，第二名水手醒来，同样将椰子等分成五份，恰好也多出一个，也给了猴子。然后自己也藏起一份，再将剩下的椰子重新合在一起。以后每个水手都如此分了一次并都藏起一份，也恰好都把多出的一个给了猴子。第二天，五个水手醒来，把剩下的椰子分成五份，恰好又多出一个，给了猴子。问原来这堆椰子至少有多少个?设置y数组，第i个水手藏椰子数为y(i)(i=1,2,…,5)个，第二天5个水手醒来后各分得椰子为y(6)个，依题意原来这堆椰子数为x=5*y(1)+1为了求取y(1)，实施递推。相邻两人所藏椰子数y(i)与y(i+1)