haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 小学教育 > 学科竞赛学科竞赛

第七讲_递推法

发布时间:2014-01-12 11:58:03  

第11章 递推与递归
主讲:马新娟 时间:2012.3
开 始

前言
递推是计算机数值算法中的重要算法。递 推的思路是通过数学推导,将复杂的运算 化解为若干重复的简单运算,以充分发挥 计算机擅长重复处理的特点。 ? 递归算法在可计算性理论中占有重要的地 位,它写出的程序比较简单,在程序设计 中有着独特的作用。
?

主要内容
? ?

递推 递归

11.1 递推
?递推关系是一种简洁高效的常见数学模型,比如
Fibonacci数列问题。 ?特点:在递推问题中,每个数据项都和它前面的若 干个数据项(或后面的若干个数据项)有一定的关联, 这种关联一般通过“递推关系式”表示。

?问题求解一般从初始的一个或若干个数据项出发,
通过递推关系逐步推进,从而得到最终结果,这种求 解问题的方法叫“递推法”。其中,初始的若干数据 项称为“边界”。

解决递推问题有三个重点:
如何建立正确的递推关系 ? 递推关系有何性质 ? 递推关系式如何求解
?

按照推导问题的方向,递推分为: ? 逆推法 ? 顺推法

一、逆推法
例1、猴子第1天摘下若干个桃子,当即吃了一半又 一个。第2天又把剩下的桃吃了一半又一个,以后每 天都吃前一天剩下的桃子的一半又一个,到第10天 猴子想吃时,只剩下一个桃子。 问猴子第1天一共摘 了多少桃子? 问题分析: 已知条件第 10 天剩下 1 个桃子,隐含条件每一 次前一天的桃子个数等于后一天桃子的个数加 1 的 2 倍。 采取逆向思维的方法,从后往前推,可用逆推法求 解。

一、逆推法
#include <stdio.h> main( ) { int a=1,i; for (i=9; i>=1; i--) a=(a+1)*2; printf("%d",a); }

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

一、逆推法
算法分析: 先要找第N只猴子和其面前桃子数的关系。如果从第1 只开始往第5只找,不好找,但如果思路一变,从第N 到第1去,可得出下面的推导式: 第N只猴 第N只猴前桃子数目 5 s5=x 4 s4=s5*5/4+1 3 s3=s4*5/4+1 2 s2=s3*5/4+1 1 s1=s2*5/4+1 通过递推,求出s1即可

//程序1:递推法 #include <stdio.h> void main() { int x,s,k,i; x=6; //第五只猴子面前最少的桃子数 k=0; //整除标志 while ( k!=4) { s=x; k=0; for ( i=4; i>=1; i--) { if ( s%4 ==0) k++; else break; s=s*5/4+1; } x=x+5; } printf("s=%d\n",s); }

二、顺推法

?例3 母牛的故事 有一头母牛,它每年年初生一头小母牛。每头小母牛 从第四个年头开始,每年年初也生一头小母牛。请编 程实现在第n年的时候,共有多少头母牛? ?关系很复杂?需要找规律!

二、顺推法
?首先,用数组f(i)来存储第i年的母牛总数,则第

n年的母牛总数为f(n)。
?f(n)只与两个值有关: ?一是在本年之前就已经出生的母牛数目; ?二是在本年新出生的小母牛数目。 即:三年前的母 牛总数:f(n-3)

即:前一年的母 牛总数:f(n-1)

二、顺推法
?由此可以得到递推公式: f(n)=f(n-1)+f(n-3) (n>=4) ?递推的边界条件:
第一、二、三年的母牛总数是直接可知的,即:

f(1)=1; f(2)=2; f(3)=3;

?类似与Fibonacci数列问题

二、顺推法
#include <stdio.h> int main() { int f[50],i,n; scanf("%d",&n); f[1]=1;f[2]=2;f[3]=3; for(i=4; i<=n; i++) { f[i]=f[i-3]+f[i-1]; } printf("%d\n",f[n]); return 0; }

二、顺推法
例4 骨牌问题 在2×n的长方形方格中,用n个1×2的骨牌铺满 方格,输入n ,输出铺放方案的总数。 例如 n=3时,为2×3方格,骨牌的铺放方案有三 种方法,如下图所示:

二、顺推法
?长度为n时的骨牌铺放方案不容易直接得到,可以从最简单的 情况开始寻找问题解决的规律——递归解决问题的基本途径。 ?以f(i)表示长度为i时的铺放方案数目 ?当n=1时,只能是一种铺法,即f(1)= 1,如下左图所示: ?当n=2时,只能是两种铺法,即f(2)= 2,如下右图所示。

二、顺推法
n=3时骨牌的铺放方案有三种方法,如下图所示:

这三种铺放方法可以采用如下的步骤分析得到: n=3时,第一块骨牌的铺法只有两种可能,横铺或者竖铺,即: (1)横铺方式:在第一格横放一个骨牌,此时剩余两格,在两 格内铺放骨牌有f(2)种铺法; (2)竖铺方式:在第一、二格竖放两个骨牌,此时剩余一格, 在一格内铺放骨牌有f(1)种铺法; f(3)=f(2)+f(1)=2+1=3。

二、顺推法
对于一般的n值,其第一块骨牌的铺法也只有两种可能,横铺或者竖铺:

(1)横铺方式:若第一格横放一个骨牌,此时剩余n-1

格,在n-1格放n-1个骨牌有f(n-1)种铺法; (2)竖铺方式:若第一、二格竖放两格骨牌,此时剩 余n-2格,在n-2格放n-2个骨牌有f(n-2)种铺法;

……

……

二、顺推法
因此,n块骨牌的铺法为首块骨牌横铺方 式的铺法与竖铺方式的铺法之和,即: f(n)=f(n-1)+f(n-2) ? 特别地,f(1)=1,f(2)=2。 ? 即为本问题的递推公式。
?

二、顺推法
? ? ? ? ?

?
? ? ? ? ? ?

#include<stdio.h> int main() { int i,n; __int64 f[50]; f[0]=1; f[1]=2; scanf("%d",&n); for(i=2;i<n;i++) f[i]=f[i-1]+f[i-2]; printf("%I64d\n",f[n-1]);

}

思考:上楼问题
设有一个共有n级的楼梯,某人每步可走1级, 也可走2级,也可走3级,求从底层开始走完全 部楼梯的有多少种走法。(例如:当n=3时,共 有4种走法,即1+1+1,1+2,2+1,3 )

算法分析:
n的值 1 2 3
4

走法 1 2 4
7

从递推的思想出发,可以设想,从 第4项开始,每1项等于前面3项的和。

f(n)=f(n-1)+f(n-2)+f(n-3) 特别地,f(1)=1,f(2)=2,f(3)=4。 即为本问题的递推公式。 #include <stdio.h>
void main( ) { int x,n,i,a,b,c; scanf("%d",&n); a=1; b=2; c=4; if (n==1) x=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); }

二、顺推法
例5 错排公式 某人写了n封信和n个信封,如果所有的信都装错了信封。 求所有的信都装错信封,共有多少种不同情况? 对n封信以及n个信封各自按照从1到n进行编号, f(n)表示当n个编号的信放在n个编号位置的信封,信 的编号与信封位置编号各不对应的方法数; 类似,f(n-1)表示n-1个编号的信放在n-1个编号位置 的信封,各不对应的方法数。 其它类推。

二、顺推法
第一步,把第n封信放在一个信封,比如第k 个信封(k≠n),一共有n-1种方法; ? 第二步,放编号为k的信,这时有两种情况: ? ①把它放到第n个信封,对于剩下的n-2封信, 需要放到剩余的n-2个信封且各不对应,就 有f(n-2)种方法; ? ②不把它放到位置n,这时,对于这n-1封信, 放到剩余的n-1个信封且各不对应,有f(n-1) 种方法; ? 据加法原理,完成第二步共有 f(n - 2)+f(n ?

二、顺推法
?

根据乘法原理, n 个不同元素的错排种 数 ,综上得到本问题的递推公式: f(n)=(n-1)*(f(n-2)+f(n-1)) 特别地,f(1)=0,f(2)=1。

二、顺推法
例6 马拦过河卒
?

棋盘上A点有一个过河卒,需要走到目标B点。象棋中卒行走的规 则:可以向下、或者向右。同时在棋盘上的任一点有一个对方的 马(如下图中的C点),该马所在的点和所有跳跃一步可达的点称 为对方马的控制点(如下图中的C点和P1,P2,……,P8,注: 马走“日”字。)。卒不能通过对方马的控制点。棋盘用坐标表 示,A点(0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置 坐标是需要给出的,C≠A且C≠B。现在从键盘输入n,m,要你计 算出卒从A点能够到达B点的路径的条数。

二、顺推法
?

马踏过河卒是一道很老的题目,一些程序设计比赛中也 经常出现过这一问题的变形。一看到这种类型的题目容 易让人想到用搜索来解决,但盲目的搜索仅当n,m=15 就会超时。可以试着用递推来进行求解。 根据卒行走的规则,过河卒要到达棋盘上的一个点,只 能有两种可能:从左边过来(

左点)或是从上面过来 (上点),所以根据加法原理,过河卒到达某一点的路 径数目,就等于其到达其相邻的上点和左点的路径数目 之和,因此可用逐列(或逐行)递推的方法求出从起点 到终点的路径数目。障碍点(马的控制点)也完全适用, 只要将到达该点的路径数目设置为0即可。

?

二、顺推法
假设用二维数组元素f[i][j]表示到达点(i,j)的路径数目,用 g[i][j]表示点(i,j)是否是对方马的控制点,g[i][j]=0表示不是 对方马的控制点,g[i][j]=1表示是对方马的控制点。则可以得到如 下的递推关系式: f[i][j] = 0 f[i][0] = f[i-1][0] f[0][j] = f[0][j-1] { g[i][j]=1 } {i>0, g[i][j]=0} {j>0, g[i][j]=0}

f[i][j] = f[i-1][j] + f[i][j-1]
{i>0, j>0, g[i][j]=0} 递推的边界为:f[0][0] = 1

二、顺推法

递推的边界为:f[0][0] = 1 递推的公式为: f[i][j] = f[i-1][j] + f[i][j-1]

#include<stdio.h> int main() { int i,j,n,m,f[20][20],g[20][20],x,y; //马和控制点设为1 scanf("%d %d %d g[x][y]=1; %d",&n,&m,&x,&y); g[x-1][y-2]=1; for (i=1;i<=n;i++) g[x+1][y-2]=1; for (j=1;j<=m;j++) g[x-2][y-1]=1; g[x+2][y-1]=1; f[i][j]=0; g[x-2][y+1]=1; for (i=0;i<=n;i++) g[x+2][y+1]=1; for (j=0;j<=m;j++) g[x-1][y+2]=1; g[x+1][y+2]=1; g[i][j]=0;

//第一列初始化 for (i=1;i<=n;i++) if(g[i][0]!=1) f[i][0]=1; else for(;i<=n;i++) f[i][0]=0; //第一行初始化 for (j=1;j<=m;j++) if(g[0][j]!=1) f[0][j]=1; else for(;j<=m;j++) f[0][j]=0;

//求路径的条数 for (i=1;i<=n;i++) {for (j=1;j<=m;j++) {if (g[i][j]==0) { f[i][j]=f[i-1][j]+f[i][j-1]; } } } printf("%d\n",f[n][m]); return 0; }

为了更简洁地表示马的控制点,可以引入两个一维数组,分别用来统计从马 的初始位置可以横向移动的位移与纵向移动的位移。程序的改进如下: #include<stdio.h> int main() { int dx[9]={0,-2,-1,1,2,2,1,-1,-2}; int dy[9]={0,1,2,2,1,-1,-2,-2,-1}; int n,m,x,y,i,j; int f[20][20]={0},g[20][20]={0}; scanf("%d%d%d%d",&n,&m,&x,&y); g[x][y]= 1; for(i=1;i<=8;i++) if((x+dx[i]>=0)&&(x+dx[i]<=n)&&(y+dy[i]>=0)&&(y+dy[i]<=m)) g[x+dx[i]][y+dy[i]]=1;

递推思考1、
平面上n条直线,任两条不平行,任三条不共点,问 这n条直线把这平面划分为多少个部分?

分析: ? 1条直线把平面分成2个区域, ? 2条直线马平面分成2+2个区域, ? 3条把平面分成2+2+3个区域,4条直线把 平面分成2+2+3+4个区域, ? 由此可知若n条直线把平面分成f(n)个 区域,则f(n)= f(n-1)+n.

思考2:打印杨晖三角形的前10行。杨晖三角形的 前5行如左下图所示。

问题分析:我们观察左上图不太容易找到规律, 但如果将左上图转化为右上图就不难发现杨辉三角 形其实就是一个二维表(数组)的下三角部分。

小结
递推关系是一种简洁高效的常见数学模型。 ? 特点:在递推问题中,每个数据项都和

它 前面的若干个数据项(或后面的若干个数 据项)有一定的关联,这种关联一般通过 “递推关系式”表示。 ? 问题求解一般从初始的一个或若干个数据 项出发,通过递推关系逐步推进,从而得 到最终结果,这种求解问题的方法叫“递 推法”。其中,初始的若干数据项称为 “边界”。
?


网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com