bnu條形碼設計（遞推）

題目鏈接：bnu4064

/*
    首先不考慮對稱，遞推公式：f[n] = f[n-1] + 2*f[n-2];
即n-1的情況加上一個豎條，n-2的情況加上一個2*2的或兩個橫條
    接著考慮有多種是對稱的，n為奇數時：s[n] = f[n/2];  n為偶數時：s[n] = f[n/2] + f[n/2-1]*2;
即（中間是一塊2*2的，或兩個橫條，或沒有）；
    f[n] = 2*不對稱的種數+s[n];
*/
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int f[30] = {0,1,3};
int s[30] = {0,1,3};
int main()
{
    int n,i,j;
    for(i = 3; i <= 28; i ++)
    {
        f[i] = f[i-1] + 2*f[i-2];
        if(i&1)
            s[i] = f[i/2];
        else
            s[i] = f[i/2] + f[i/2-1]*2;
    }
    int p = 1;
    while(scanf("%d",&n),n)
    {
        printf("Case %d:%d\n",p++,(f[n]+s[n])/2);
    }
    return 0;
}