Problem 10359 Tiling，大數模型組合次數

這題需要用到 Problem 10254 的大數處理概念，再利用費氏級數概念，這題就不難解決了。

只需利用 F(0) = 1、F(1) = 1、F(2) = 3，當 n > 2，F(n) = F(n-1) + 2 * F(n-2)。我們可以宣告一個結構(struct)，以及將它宣告陣列用以擺入答案，接著套用 Problem 10254 的大數處理概念，再寫成 C 語言程式碼如下：

#define MAXLEN 251
#define LEN 76
struct til
{
    int num[100];       
};
struct til t[MAXLEN];
struct til s;

void mult2s()
{
     int i, j;
     for (i = 0; i < LEN; i ++)
         s.num[i] *= 2;
     for (i = 0; i < LEN; i ++)
         if (s.num[i] >= 10)
            s.num[i + 1] ++, s.num[i] %= 10;
}

void add(int n)
{
    int i;
    for (i = 0; i < LEN; i ++)
    {
        t[n].num[i] += s.num[i];
        if (t[n].num[i] >= 10)
           t[n].num[i + 1] ++, t[n].num[i] %= 10;
    }
    
    for (i = 0; i < LEN; i ++)
    {
        t[n].num[i] += t[n - 1].num[i];
        if (t[n].num[i] >= 10)
           t[n].num[i + 1] ++, t[n].num[i] %= 10;
    }
}

void creat()
{
    int i, j; 
    t[0].num[0] = 1, t[1].num[0] = 1, t[2].num[0] = 3;
    for (i = 3; i < MAXLEN; i ++)
    {
        for (j = 0; j < LEN; j ++)
            s.num[j] = t[i - 2].num[j];
        mult2s();
        add(i);
    } 
}

這時只須將輸入的 n 值對應陣列索引，將它印出即可。C 語言程式碼如下：

creat();
while (scanf("%d", &n) == 1)
{
    for (i = LEN - 1; i >= 0; i --)
        if (t[n].num[i] > 0) break;
    for (j = i; j >= 0; j --)
        printf("%d", t[n].num[j]);
    printf("\n");         
}

By David.K

p10359題目連結
回ACM題庫目錄
回首頁