[noip教案]三、递推

《[noip教案]三、递推》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Fibonacci(斐波那契)数列Fibonacci数列,即斐波那契数列。它的特点是前面两个数的和等于后面的一个数。斐波那契数列只有一个。例如1，1，2，3，5，8，13，21，34，55，89，144，233，377，610，987，1597，2584，4181，6765……F(n)=F(n-1)+F(n-2)(n>2)递推算法找出前后过程之间的数量关系，即递推式！一、Fibonacci(斐波那契)数列兔子繁殖问题有雌雄一对兔子，假定过两个月之后便可每月繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？设第n月共有F(n)对兔子，其中包括第n-1月的F

2、(n-1)对兔子，还包括新生的兔子对数（由于第n-2月的兔子在第n月都具有了繁殖能力，所以新生兔子对数为F(n-2).F(0)=0;F(1)=1;F(n)=F(n-1)+F(n-2);P169例3.2骨牌铺满方格有2*n个长方形方格，用n个1*2的骨牌铺满方格，求输入任意一个n，输出铺法总数。(e1.cpp)F(1)=1;F(2)=2;F(n)=F(n-1)+F(n-2);如：n=3时#includeusingnamespacestd;intmain(){inti,n,f[200];scanf("%d",&n);f[1]=1;f[2]=2;fo

3、r(i=3;i<=n;++i)f[i]=f[i-1]+f[i-2];printf("%d",f[n]);return0;}练习2、S:=N!3、P180页4题骨牌铺法用递推的方法完成下列问题：1、有5个人坐在一起，问第5个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第3个人，又说比第2个人大2岁。问第2个人，说比第1个人大2岁。最后问第1个人，他说是10岁。请问第5个人多大。4、P180页1题走楼梯例：贮油点一辆重型卡车欲穿过1000公里的沙漠，卡车耗汽油为1升/公里，卡车总载油能力为500公升。显然卡车装一次油是过不了沙漠的。因此

4、司机必须设法在沿途建立若干个贮油点，使卡车能顺利穿过沙漠。试问司机如怎样建立这些贮油点？每一贮油点应存储多少汽油，才能使卡车以消耗最少汽油的代价通过沙漠？(e2.cpp)#includeusingnamespacestd;intmain(){floatoil[1000],way[1000];inti,j;oil[0]=0;way[0]=0;i=0;while(way[i]<1000){++i;oil[i]=oil[i-1]+500;way[i]=way[i-1]+500/(2*i-1);}for(j=i-1;j>0;--j)printf("%d

5、:%.2f%.2f",j,1000-way[j],oil[j]);return0;}例：(e9.cpp)把整数n分成k份，且每份不能为空，任意两种分法不能相同（不考虑顺序）。例如：n=7,k=3时，分法有4种。#include#includeusingnamespacestd;intmain(){intf[200][200],i,j,n,k,p;scanf("%d%d",&n,&k);for(i=0;i<=n;++i)for(j=0;j<=k;++j)f[i][j]=0;f[1][1]=1;for(i=2;i<=n;++i

6、){f[i][1]=1;for(j=2;j<=i-1;++j){f[i][j]=0;for(p=1;p<=j;++p)f[i][j]+=f[i-j][p];}f[i][i]=1;}printf("%d",f[n][k]);return0;}递推法：把n分成不同的k份方案总数等于将正整数n-k分解成不大于k的正整数之和的不同解决方案总数。练习NOIP2001数的计数我们要求找出具有以下性质数的个数（包含输入的自然数n）。先输入一个自然数n（n<=1000），然后对此自然数按照以下方法进行处理：不作任何处理；在它的左边加上一个自然数，但该自然数不能超过原数的一半；

7、加上数后，继续按此规则进行处理，直到不能再加自然数为止。【输入格式】自然数n(n<=1000)【输出格式】满足条件的数【输入样列】6【输出样列】6【样列说明】满足条件的数为6、16、26、126、36、136二、最值问题例:数学三角形(e3.cpp)以下所示为一个数学三角形。请编一个程序计算从顶到底的一条路径，使该路径所经过的数字总和最大，输出数字总和的最大值，输入格式如下图右781074445265a[i,j]存放从i,j出发到达n层的最大值。a[i,j]=max{a[i,j]+a[i+1,j]，a[I,j]+a[i+1,j+1]}781074445265对

8、于任意点i,j只有两条路选择#incl