HDU 2569

題目描述
        HDU 2569
分析
        使用遞推的方法可以解決。
        設當懸崖的長度為n時，到達彼岸的方法有F[n]種。
        顯然，F[1] = 3, F[2] = 9, F[3] = 21     假設已知F[n-1]與F[n-2]，尋求F[n]與F[n-1]、F[n-2]之間的關系。
        分為兩種情況：
        (1)第n-2段與n-1段顏色相同，則第n段可以為三種顏色的任意一種：
             F[n-2] * 3
        (2)第n-2段與n-1段顏色不同，第n段只能為其中的兩種顏色：
             (F[n-1] - F[n-2]) * 2

        故，總的方法數為：F[n-2] * 3 +　(F[n-1] - F[n-2]) * 2　＝　F[n-1] * 2  + F[n-2]
源碼
       

#include <stdio.h>

int main()
{
    int result[40];
    int i;

    result[1] = 3;
    result[2] = 9;
    result[3] = 21;
    for (i = 4; i < 40; i ++)
    {
        result[i] = result[i-1]*2 + result[i-2];
    }

    int C, n;
    scanf("%d", &C);
    while (C --)
    {
        scanf("%d", &n);
        printf("%d\n", result[n]);
    }

    return 0;
}