【摘要】一.递推
“递推”是计算机解题的一种常用方法。利用“递推法”解题首先要分析归纳出“递推关系”。如经典的斐波那契数列问题，用 f (i)表示第 i 项的值，则 f (1) =0，f(2) =1，在 n>2 时，存在递推关系：f (n) = f(n-1) + f(n-2)。在递推问题模型中，每个数据项都与它前面的若干个数据项（或后面的若干个数据项）存在一定的关联，这种关…

一.递推

“递推”是计算机解题的一种常用方法。利用“递推法”解题首先要分析归纳出“递推关系”。如经典的斐波那契数列问题，用 f (i)表示第 i 项的值，则 f (1) =0，f(2) =1，在 n>2 时，存在递推关系：f (n) = f(n-1) + f(n-2)。
在递推问题模型中，每个数据项都与它前面的若干个数据项（或后面的若干个数据项）存在一定的关联，这种关联一般是通过一个“递推关系式”来描述的。求解问题时，需要从初始的一个或若干数据项出发，通过递推关系式逐步推进，从而推导计算出最终结果。这种求解问题的方法叫“递推法”。其中，初始的若干数据项称为“递推边界”。

解决递推问题有三个重点：
1、建立正确的递推关系式；
2、分析递推关系式的性质；
3、根据递推关系式编程求解。
递推法分为“顺推”和“倒推”两类模型：
1、顺推，就是从问题的边界条件(初始状态)出发，通过递推关系式依次从前往后递推出问题的解；
2、倒推，就是在不知道问题的边界条件(初始状态)下，从问题的最终解(目标状态或某个中间状态)出发，反过来推导问题的初始状态。

二.例题

1.取数问题

题目描述
我们来玩一个游戏：自然数1到N，按顺序列成一排，你可以从中取走任意个数，但是相邻的两个不可以同时被取走。

如果你能算出一共有多少种取法，那么你会被天神Lijiganjun奖励。

输入格式
一个数n（1< n < = 50）。

输出格式
仅包含一个数——你的答案。

样例数据
input
5
output
13

代码：

#include<bits/stdc++.h>
using namespace std;
long long a[100]={0,2,3,0};
int main()
{
	int n;
	cin>>n;
	for(int i=3;i<=n;i++)
		a[i]=a[i-1]+a[i-2];//这是代码核心，也就是递推式，很重要
	cout<<a[n];
	return 0;
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12

2.骨牌铺法

题目描述

有 1×n 的一个长方形，用一个 1×1、1×2 和 1×3 的骨牌铺满方格。例如当 n=3 时为 1×3 的方格。此时用 1×1、1×2 和 1×3 的骨牌铺满方格，共有四种铺法。如下图：
在这里插入图片描述

输入格式
一个整数 n n<=40
输出格式
一个整数表示方法总数
样例数据
input
3
output
4
分析：
从上一个例子中可以看出：递推的关键在于找到递推式。找递推式的过程可以抽象地看作是数学上的找规律。如果你找到了递推式，那么这道题就迎刃而解了。
【算法分析】
（1）面对上述问题，如果思考方法不恰当，要想获得问题的解答是相当困难的。可以用递推方法归纳出问题解的一般规律。
（2）当n=1时，只能是一种铺法，铺法总数有示为x1=1。
（3）当n=2时：骨牌可以两个并列竖排，也可以并列横排，再无其他方法，如下左图所示，因此，铺法总数表示为x2=2；
在这里插入图片描述
（4）当n=3时：骨牌可以全部竖排，也可以认为在方格中已经有一个竖排骨牌，则需要在方格中排列两个横排骨牌（无重复方法），若已经在方格中排列两个横排骨牌，则必须在方格中排列一个竖排骨牌。如上右图，再无其他排列方法，因此铺法总数表示为x3=3。
由此可以看出，当n=3时的排列骨牌的方法数是n=1和n=2排列方法数的和。
（5）推出一般规律：对一般的n，要求xn可以这样来考虑，若第一个骨牌是竖排列放置，剩下有n-1个骨牌需要排列，这时排列方法数为xn-1；若第一个骨牌是横排列，整个方格至少有2个骨牌是横排列（1*2骨牌），因此剩下n-2个骨牌需要排列，这是骨牌排列方法数为xn-2。从第一骨牌排列方法考虑，只有这两种可能，所以有：
xn=x（n-1）+x（n-2）（n>2）
x1=1
x2=2
xn=xn-1+xn-2就是问题求解的递推公式。任给n都可以从中获得解答。例如n=5，
x3=x2+x1=3
x4=x3+x2=5
x5=x4+x3=8
代码：

#include<bits/stdc++.h>
using namespace std;
int a[50]={0,1,2,4};
int main()
{ int n; cin>>n; for(int i=4;i<=n;i++) a[i]=a[i-1]+a[i-2]+a[i-3];//递推式 cout<<a[n]; return 0;
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12

3.平面分割

题目描述
同一平面内有 n（n≤500）条直线，已知其中 p（p≥2）条直线相交于同一点，则这 n 条直线最多能将平面分割成多少个不同的区域？

输入格式
两个整数 n（n≤500）和 p（2≤p≤n）。

输出格式
一个正整数，代表最多分割成的区域数目。
样例数据
input
12 5
output
73
分析：
直线每过一条直线，就能多分割出一块空间，共可分割出n块。
所以得到递推式：f ( p ) = 2 * p ;
代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,p,sum;
	cin>>n>>p;
	sum=p*2;
	for(int i=p;i<n;i++)
		sum+=i+1;
	cout<<sum<<endl;
	return 0;
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12