又荒废了几天，哎，今天继续更。

引言

已知数列a的前6项是：1、1、2、3、5、8，请求出第7项！

这道小学数学题目应该难不倒大家吧，没错，这道题的求解过程就是递推！

算法思想

递推算法是一种用若干步可重复的简运算（规律）来描述复杂问题的方法。它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定象的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。

基础模型

这类题求解的过程，一般是通过前面的简单运算，分析其中通项的求解过程，然后由前向后依次类推下一项，直到得到需要的值。

例题1

题目描述（hdu2046）

在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数.
例如n=3时,为2× 3方格，骨牌的铺放方案有三种,如下图：

输入数据由多行组成，每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0

测试样例

输入 1  3  2

输出 1  3  2

解题思路

由于长方形规格是2*n，因此，他有两条边长度为2固定不变，另外两条边长度为n，有上图可知：2*4的长方形，将由2*3的长方形在每一种情况后加上一个2*1的骨牌得到，或者可以由2*2的长方形的每一张情况后加上2张2*1的骨牌横向放置得到。

因此将2*n的长方形的所有放置的情况记为f(n)，则f（4）= f（3）+ f（2），故此可得到通项公式：f（n）= f（n-1）+f（n-2），由于容易求出f（1）=1，f（2）=2，因此可利用循环，从前到后以此递推到n，求出f（n）的值。

完整代码

#include
using namespace std;
int main(){
    long long a[51]={0, 1, 2}, n;//此处注意最后结果是否会溢出int型
    for(int i = 3; i <= 50; i++) 
		a[i] = a[i - 1] + a[i - 2];
    while(cin>>n){
        cout<

例题2

题目描述（hdu2050）

我们看到过很多直线分割平面的题目，今天的这个题目稍微有些变化，我们要求的是n条折线分割平面的最大数目。比如，一条折线可以将平面分成两部分，两条折线最多可以将平面分成7部分，具体如下所示。

输入数据的第一行是一个整数C,表示测试实例的个数，然后是C 行数据，每行包含一个整数n(0

对于每个测试实例，请输出平面的最大分割数，每个实例的输出占一行。

测试样例

输入 2  1  2

输出 2  7

解题思路

根据直线分平面可知，由交点决定了射线和线段的条数，进而决定了新增的区域数。当n-1条折线时，区域数为f（n-1）。为了使增加的区域最多，则折线的两边的线段要和n-1条折线的边（2*（n-1）条线段）相交。那么新增的线段数为4*（n-1），射线数为2。但要注意的是，折线本身相邻的两线段只能增加一个区域。因此可得：f(n)=f(n-1)+4(n-1)+2-1，化简得：f(n) =2n^2-n+1

完整代码

#include 
using namespace std;
int main(){
    int n,t;
    cin>>t;
    while(t--){
        cin>>n;
        cout<<2*n*n-n+1<

总结回顾

一般的递推题目，f（n）是由f（n-1）、f（n-2）或者f（n/2）这些项推出，运算形式多为加、减、乘、除运算，当然也有可能是乘方、开方运算，题目多变，具体情况还需具体对待，并无固定形式，但是解题思想相通。解题者在解题过程中，可通过对前几项的计算，认真找出通项公式求解即可。

例题推荐

hdu：2044、2045、2047、2048、2049

written by 金磊