（贵州省普通高中信息学奥赛CSP-JS NOIP—提高组C++知识点讲解）第7讲 递推

学科竞赛编程 C++ NOIP NOI IOI 1 1 PART ONE 递推算法： 是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。 递推的概念 1 2 3 特点： 1、问题可以划分成多个状态； 2、除初始状态外，其它各个状态都可以用固定的递推关系式来表示。 首要问题： 得到相邻的数据项间的关系（即递推关系）。 一般来说，可以将递推算法看成是一种特殊的迭代算法。 1 PART ONE 给定一个数的序列H0，H1，…，Hn，…若存在整数n0，使当n>n0时，可以用符号（或大于号、小于号）将Hn与其前面的某些项Hi（0<i<n）联系起来，这样的式子就叫做递推关系式 递推关系式： Hn=Hn-1+Hn-2 递推的概念——递推关系式 1 PART ONE Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”引出的 递推的概念——斐波那契（Fibonacci）数列 一对兔子，从出生满2月起，每个月都生一对兔子。小兔子长到第3个月后每个月又生一对兔子。假如兔子都不死，请问第1个月出生的一对兔子，第n个月有几只兔子？ 问题分析：前提——不考虑兔子死亡 用小写字母表示新兔子，用大写字母表示具备生育能力的兔子 第1个月：放入一对新兔子r1。 第2个月：还是一对兔子，但已具备生育能力r1变成R1。 第3个月：R1生新兔子r2，兔子变为R1+r2。 第4个月：R1生新兔子r3，r2变R2。兔子为R1，R2，r3。 第5个月：R1和R2生新兔子r4和r5，r3变为R3。兔子为R1，R2，R3，r4，r5 … 兔子数量 1 1 2 3 5 … 1 PART ONE  代码如下： #include <iostream> using namespace std; int main(){ int a[1000],n; cin>>n; a[0]=a[1]=1; for(int i=2; i<=n; i++){a[i]=a[i-1]+a[i-2];} cout<<a[n]; return 0;} 递推的概念——斐波那契（Fibonacci）数列 Fibonacci数列递推方程： 递推算法以初始（起点）值为基础，用相同的运算规律，逐次重复运算，直至运算结束。这种从“起点”重复相同的方法直至到达一定“边界”，犹如单向运动，用循环可以实现。递推的本质是按规律逐次推出（计算）先一步的结果 1 PART ONE 什么是顺推和逆推 顺推法：从已知条件出发，逐步推出要解决的问题的结果。 逆推法：从问题结果出发，逐步推到已知条件。 1 PART ONE 什么是顺推和逆推 顺推 逆推 由题意（或递推关系）定初始值F1（边界条件）求出顺推关系式Fi=G(Fi-1) 由题意（或递推关系）确定最终结果Fn；求出倒推关系式Fi-1=G(Fi) i=1（由边界条件F1出发进行顺推） i=n（从最终结果Fn出发进行倒推） while当前结果Fi非最终结果Fn，由Fi=G(Fi-1)顺推后项； while当前结果Fi非初始值F1，由Fi-1=G(Fi)倒推前项； 输出顺推结果Fn和顺推过程 输出倒推结果F1和倒推过程 解决递推问题的一般步骤： 1、建立递推关系式；2、确定边界条件（即初始值）；3、递推求解 1 PART ONE 顺推（骨牌问题） 算法分析 n=1 有2*n的长方形方格，用n个1*2的骨牌铺满方格。编一程序，试对给出的任意一个n（n>0），输出铺法总数。 顺推和逆推的应用——顺推 n=2 n=3 n=4 请你看看n=4时有几种排法吧！ 1 PART ONE 推出一般规律： 对于一般的n，假设其铺法总数为xn 若第一个骨牌是竖排列放置时，剩下n-1个需要排列，其排列方法数刚好为xn-1 若第一个骨牌是横排放置时，则整个方格至少有2个骨牌横排，则剩下n-2个需要排列，排列方法为xn-2 顺推和逆推的应用——顺推 …. ….. …. ….. n n-1 n n-2 1 PART ONE 顺推和逆推的应用——顺推 初始化边界条件 初始条件：或是问题本身已经给定，或是通过对问题的分析和化简后确定 代码如下： #include <iostream> using namespace std; int main(){ int a[1000],n; cin>>n; a[1]=1; //初始化边界条件 a[2]=2; //开始递推 for(int i=2; i<=n; i++){a[i]=a[i-1]+a[i-2];} cout<<a[n]<<endl; return 0;} 1 PART ONE 顺推和