《[NOIP教案]三、递推》由会员分享，可在线阅读，更多相关《[NOIP教案]三、递推（17页珍藏版）》请在金锄头文库上搜索。
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) (n2),递推算法,找出前后过程之间的数量关系，即递推式！,一、Fibonacci(斐波那契)数列,兔子繁殖问题,有雌雄一对兔子，假定过两个月之后便可每月繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？,设第n月共有F(n)对兔子，其中包括第n-1月的F(n-1)对兔子，还包
2、括新生的兔子对数（由于第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时,#includeusing namespace std;int main()int i,n,f200;scanf(%d,&n);f1=1;f2=2;for(i=3;i=n;+i) fi=fi-1+fi-2;printf(
3、%d,fn);return 0;,练习,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),#includeusing namespace std;int main()float oil1000,way1000;int i,j;oil0=0;way0=0;i=0;while(wayi0;-j) printf(%d:%.2f %.2fn,j,1000-wayj,oilj);return 0;,例：(e9.cpp),把整数n分成k份，且每份不能为空，任意两种分法不能相同（不考虑顺序）。例如：n=7,k=3时，分法有4种。,#include#includeusing namespace std;int main()int
5、f200200,i,j,n,k,p;scanf(%d%d,&n,&k);for(i=0;i=n;+i) for(j=0;j=k;+j) fij=0; f11=1;for(i=2;i=n;+i) fi1=1; for(j=2;j=i-1;+j) fij=0; for(p=1;p=j;+p) fij+=fi-jp; fii=1; printf(%d,fnk);return 0;,递推法： 把n分成不同的k份方案总数等于将正整数n-k分解成不大于k的正整数之和的不同解决方案总数。,练习,NOIP2001数的计数,我们要求找出具有以下性质数的个数（包含输入的自然数n）。先输入一个自然数n（n=1000
6、），然后对此自然数按照以下方法进行处理： 不作任何处理； 在它的左边加上一个自然数，但该自然数不能超过原数的一半； 加上数后，继续按此规则进行处理，直到不能再加自然数为止。【输入格式】 自然数n(n=1000)【输出格式】 满足条件的数【输入样列】 6【输出样列】 6【样列说明】 满足条件的数为 6、16、26、126、36、136,二、最值问题,例:数学三角形(e3.cpp),以下所示为一个数学三角形。请编一个程序计算从顶到底的一条路径，使该路径所经过的数字总和最大，输出数字总和的最大值，输入格式如下图右,7 8 1 0 7 4 44 5 2 6 5,ai,j存放从i,j出发到达n层的最大值
7、。ai,j=maxai,j+ai+1,j，aI,j+ai+1,j+1,7 8 1 0 7 4 44 5 2 6 5,对于任意点i,j只有两条路选择,#includeusing namespace std;int main() int i,j,n,a100100; scanf(%d,&n); for(i=1;i=n;+i) for(j=1;j=1;-i) for(j=1;j(ai+1j+1) aij+=ai+1j; else aij+=ai+1j+1;printf(%d,a11);return 0;,数学三角形,例:过河卒(e4.cpp),棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：
8、可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如下图中的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点（如下图中的C点和P1，P2，P8）。卒不能通过对方马的控制点。棋盘用坐标表示，A点(0,0)、B点(n, m) (n,m为不超过15的整数),同样马的位置坐标是需要给出的，CA且CB。现在从键盘输入目标B点的位置n，m和马的位置x,y，要你计算出卒从A点能够到达B点的路径的条数。,gi,j表示点(i,j)是否是马的控制点；ai,j表示能到达点(i,j)的路径数目。,到达点(4,8)的路径条数a4,8:=a4,7+a3,8,#include#includeusing n
9、amespace std;int main() int a2121,i,j,n,m,x,y; bool g2121; memset(g,1,sizeof(g); memset(a,0,sizeof(a); scanf(%d%d%d%d,&n,&m,&x,&y); gxy=0; if(x-1)=0)&(y-2)=0) gx-1y-2=0; if(x-2)=0)&(y-1)=0) gx-2y-1=0; if(x-2)=0)&(y+1)=0)&(y+2)=m) gx-1y+2=0; if(x+1)=n)&(y+2)=m) gx+1y+2=0; if(x+2)=n)&(y+1)=m) gx+2y+1=0; if(x+2)=0) gx+2y-1=0; if(x+1)=0) gx+1y-2=0;,过河卒,if(g00) a00=1; for(i=1;i=n;+i) if(gi0) ai0=ai-10; else ai0=0; for(j=1;j=m;+j) if(g0j) a0j=a0j-1; else a0j=0; for(i=1;i=n;+i) for(j=1;j=m;+j) if(gij) aij=ai-1j+aij-1; printf(%d,anm); return 0;,边缘的aI,j初始化。,练习：,1010【联赛练习题目】马拦过河卒,
