第七讲递推法

1、第11章 递推与递归 主讲：马新娟 时间：2012.3开开 始始前言l递推是计算机数值算法中的重要算法。递推的思路是通过数学推导，将复杂的运算化解为若干重复的简单运算，以充分发挥计算机擅长重复处理的特点。l递归算法在可计算性理论中占有重要的地位，它写出的程序比较简单，在程序设计中有着独特的作用。主要内容l递推l递归11.1 递推：例例1、猴子第、猴子第1天摘下若干个桃子天摘下若干个桃子,当即吃了一半又当即吃了一半又一个。第一个。第2天又把剩下的桃吃了一半又一个天又把剩下的桃吃了一半又一个,以后每以后每天都吃前一天剩下的桃子的一半又一个天都吃前一天剩下的桃子的一半又一个,到第到第10天天猴子想吃

2、时猴子想吃时,只剩下一个桃子。只剩下一个桃子。 问猴子第问猴子第1天一共摘天一共摘了多少桃子了多少桃子? 问题分析：问题分析： 已知条件第已知条件第 10 天剩下天剩下 1 个桃子，隐含条件个桃子，隐含条件每一每一次前一天的桃子个数等于后一天桃子的个数加次前一天的桃子个数等于后一天桃子的个数加 1 的的 2 倍。倍。 采取采取逆向思维逆向思维的方法的方法,从后往前推，可用从后往前推，可用逆推法逆推法求求解。解。一、逆推法#include main( )int a=1,i;for (i=9; i=1; i-)a=(a+1)*2;printf(%d,a); 一、逆推法例例2 2：猴子分食桃子：猴子

3、分食桃子 五只猴子采得一堆桃子，猴子彼此约定隔五只猴子采得一堆桃子，猴子彼此约定隔天早起后再分食。不过，就在半夜里，一只猴天早起后再分食。不过，就在半夜里，一只猴子偷偷起来，把桃子均分成五堆后，发现还多子偷偷起来，把桃子均分成五堆后，发现还多一个，它吃掉这桃子，并拿走了其中一堆。第一个，它吃掉这桃子，并拿走了其中一堆。第二只猴子醒来，又把桃子均分成五堆后，还是二只猴子醒来，又把桃子均分成五堆后，还是多了一个，它也吃掉这个桃子，并拿走了其中多了一个，它也吃掉这个桃子，并拿走了其中一堆。第三只，第四只，第五只猴子都依次如一堆。第三只，第四只，第五只猴子都依次如此分食桃子。那么桃子数最少应该有几个呢

4、？此分食桃子。那么桃子数最少应该有几个呢？一、逆推法算法分析：算法分析：先要找第N只猴子和其面前桃子数的关系。如果从第1只开始往第5只找，不好找，但如果思路一变，从第N到第1去，可得出下面的推导式： 第N只猴 第N只猴前桃子数目5 s5=x4 s4=s5*5/4+13 s3=s4*5/4+12 s2=s3*5/4+11 s1=s2*5/4+1通过递推，求出s1即可一、逆推法/程序程序1：递推法：递推法#include void main() int x,s,k,i;x=6; /第五只猴子面前最少的桃子数第五只猴子面前最少的桃子数k=0; /整除标志整除标志while ( k!=4)s=x;k=

5、0;for ( i=4; i=1; i-)if ( s%4 =0) k+; else break;s=s*5/4+1; x=x+5;printf(s=%dn,s);二、顺推法二、顺推法 二、顺推法二、顺推法二、顺推法二、顺推法二、顺推法 二、顺推法l因此，n块骨牌的铺法为首块骨牌横铺方式的铺法与竖铺方式的铺法之和，即： f(n)=f(n-1)+f(n-2)l特别地，f(1)=1，f(2)=2。l即为本问题的递推公式。二、顺推法二、顺推法l#includelint main()ll int i,n;l _int64 f50;l f0=1;lf1=2;lscanf(%d,&n);l for

6、(i=2;in;i+)l fi=fi-1+fi-2;l printf(%I64dn,fn-1); l 设有一个共有n级的楼梯，某人每步可走1级，也可走2级，也可走3级，求从底层开始走完全部楼梯的有多少种走法。（例如：当n=3时，共有4种走法，即1+1+1，1+2，2+1，3 ）思考：上楼问题思考：上楼问题算法分析：算法分析：n的值 走法 1 1 2 2 3 4 4 7 从递推的思想出发，可以设想，从第4项开始，每1项等于前面3项的和。#include void main( ) int x,n,i,a,b,c;scanf(%d,&n); a=1; b=2; c=4; if (n=1) x

7、=1;else if (n=2) x=2; else if (n=3) x=4; for (i=4; i=n; i+) x=a+b+c; a=b; b=c; c=x; printf(%d,x); f(n)=f(n-1)+f(n-2)+f(n-3) 特别地，f(1)=1，f(2)=2,f(3)=4。 即为本问题的递推公式。例5 错排公式 某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封，共有多少种不同情况？ 对n封信以及n个信封各自按照从1到n进行编号， f（n）表示当n个编号的信放在n个编号位置的信封，信的编号与信封位置编号各不对应的方法数； 类似，f（n-1）表示n-

8、1个编号的信放在n-1个编号位置的信封，各不对应的方法数。 其它类推。 二、顺推法l第一步，把第n封信放在一个信封，比如第k个信封（kn），一共有n-1种方法；l第二步，放编号为k的信，这时有两种情况：u把它放到第n个信封，对于剩下的n-2封信，需要放到剩余的n-2个信封且各不对应，就有f(n-2)种方法；u不把它放到位置n，这时，对于这n-1封信，放到剩余的n-1个信封且各不对应，有f(n-1)种方法； u据加法原理，完成第二步共有 f(n - 2)+f(n - 1) 种方法。 二、顺推法l根据乘法原理， n 个不同元素的错排种数 ，综上得到本问题的递推公式： f（n）=（n-1）*（f（n

9、-2）+f（n-1） 特别地，f（1）=0，f（2）=1。二、顺推法l棋盘上A点有一个过河卒，需要走到目标B点。象棋中卒行走的规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如下图中的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点（如下图中的C点和P1，P2，P8，注：马走“日”字。）。卒不能通过对方马的控制点。棋盘用坐标表示，A点(0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的，CA且CB。现在从键盘输入n，m，要你计算出卒从A点能够到达B点的路径的条数。例例6 马拦过河卒马拦过河卒二、顺推法l马踏过河卒是一道很老的题目，一

10、些程序设计比赛中也经常出现过这一问题的变形。一看到这种类型的题目容易让人想到用搜索来解决，但盲目的搜索仅当n,m=15就会超时。可以试着用递推来进行求解。l根据卒行走的规则，过河卒要到达棋盘上的一个点，只能有两种可能：从左边过来（左点）或是从上面过来（上点），所以根据加法原理，过河卒到达某一点的路径数目，就等于其到达其相邻的上点和左点的路径数目之和，因此可用逐列（或逐行）递推的方法求出从起点到终点的路径数目。障碍点（马的控制点）也完全适用，只要将到达该点的路径数目设置为0即可。 二、顺推法 假设用二维数组元素fij表示到达点（i，j）的路径数目，用gij表示点（i，j）是否是对方马的控制点，g

11、ij=0表示不是对方马的控制点，gij=1表示是对方马的控制点。则可以得到如下的递推关系式： fij = 0 gij=1 fi0 = fi-10 i0, gij=0 f0j = f0j-1 j0, gij=0 fij = fi-1j + fij-1 i0, j0, gij=0 递推的边界为：f00 = 1 二、顺推法递推的边界为：f00 = 1递推的公式为： fij = fi-1j + fij-1 fij = fi-1j + fij-1 二、顺推法#includeint main() int i,j,n,m,f2020,g2020,x,y; scanf(%d %d %d %d,&n,&

12、amp;m,&x,&y); for (i=1;i=n;i+)for (j=1;j=m;j+)fij=0; for (i=0;i=n;i+) for (j=0;j=m;j+) gij=0;/马和控制点设为马和控制点设为1gxy=1;gx-1y-2=1;gx+1y-2=1;gx-2y-1=1;gx+2y-1=1;gx-2y+1=1;gx+2y+1=1;gx-1y+2=1;gx+1y+2=1;/第一列初始化第一列初始化for (i=1;i=n;i+)if(gi0!=1) fi0=1;else for(;i=n;i+)fi0=0;/第一行初始化第一行初始化for (j=1;j=m;j+

13、)if(g0j!=1) f0j=1;else for(;j=m;j+)f0j=0;/求路径的条数求路径的条数for (i=1;i=n;i+)for (j=1;j=m;j+)if (gij=0) fij=fi-1j+fij-1; printf(%dn,fnm);return 0;为了更简洁地表示马的控制点，可以引入两个一维数组，分别用来统计从马为了更简洁地表示马的控制点，可以引入两个一维数组，分别用来统计从马的初始位置可以横向移动的位移与纵向移动的位移。程序的改进如下：的初始位置可以横向移动的位移与纵向移动的位移。程序的改进如下：#includeint main() int dx9=0,-2,-

14、1,1,2,2,1,-1,-2; int dy9=0,1,2,2,1,-1,-2,-2,-1; int n,m,x,y,i,j; int f2020=0,g2020=0; scanf(%d%d%d%d,&n,&m,&x,&y); gxy= 1;for(i=1;i=0)&(x+dxi=0)&(y+dyi=m)gx+dxiy+dyi=1;递推思考递推思考1、 平面上平面上n条直线，任两条不平行，任三条不共点，问条直线，任两条不平行，任三条不共点，问这这n条直线把这平面划分为多少个部分？条直线把这平面划分为多少个部分？分析：l1条直线把平面分成2个区域，l2条直线马平面分成2+2个区域，l3条把平面分成2+2+3个区域，4条直线把平面分成2+2+3+4个区域，l由此可知若n