POJ 1953 World Cup Noise（递推）

https://vjudge.net/problem/POJ-1953

题意：
输入一个n，这n位数只由0和1组成，并且不能两个1相邻。计算共有多少种排列方法。

思路：
递推题。

首先a[1]=2,a[2]=3是显而易见的，接下来计算分析到第n位时的排列方法数，如果第n-1位数为1，那么第n位只能为0，那么此时有g[n-1]种方法（g[n-1]表示第n-1位为1的数量）。如果第n-1位为0，那么此时有2*f[n-1]种方法（f[n-1]表示第n-1位为0的数量）。

所以，两者相加=g[n-1]+2*f[n-1]=a[n-1]+f[n-1]=a[n-1]+a[n-2]。（n-1位为0说明n-2既可以为0，又可以为1，所以f[n-1]=a[n-2]）。

#include<iostream> 
using namespace std;

const int maxn = 50;

int n;
int a[maxn];

void init()
{
    a[1] = 2;
    a[2] = 3;
    for (int i = 3; i <= 50; i++)
    {
        a[i] = a[i - 1] + a[i - 2];
    }
}

int main()
{
    //freopen("D:\txt.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    init();
    for (int kase = 1; kase <= T; kase++)
    {
        scanf("%d", &n);
        printf("Scenario #%d:
%d

", kase, a[n]);
    }
}