Problem 10254 The Priest Mathematician，四根柱子的河內塔

一開始，我以為四根柱子的河內塔在 64 片盤子移動的次數為 18433 次，當然 10000 片盤子的移動次數也應該或許不會超過 long long int 的範圍，但是我錯了，此移動次數的成長是以 2ⁿ 的次方成長。最後我算出 10000 片盤子的移動次數為 374931278650296101567069263458900577819295745 ，高達 44 位數，所以這一題應該是大數處理的題目。

我其實不太會算河內塔的次數，所以 google 了一下，發現這篇 文章 研究河內塔移動次數之深，其實不難懂，有興趣的人可以參考一下。而在這篇文章中說明了四根柱子移動次數的變化，如下表：

n	1	2	3	4	5	6	7	8	9	10	11
F4(n)	1	3	5	9	13	17	25	33	41	49	65
F4(n)的差分	1	2	2	4	4	4	8	8	8	8	16

以上表說明了在四根柱子的情況下，F₄(n)的差分中，2⁰出現 1 次、2¹出現 2 次、2²出現 3 次、2³出現 4 次、....、2ⁿ出現 n + 1 次，所以，我們只需利用此表分差的概念，將 10000 以內盤子移動的次數累加並儲存起來，就可以輕鬆解決。

首先建立一個結構，C語言程式碼如下：

struct towerofHanoi
{
    int num[MAXLEN];  
};

struct towerofHanoi toH[10001];
struct towerofHanoi s;

s 為分差，所以需要一個累乘的 2 的函式，C語言程式碼如下：

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

接著就要寫一個函式來建構這 10000 個陣列的值，依前面敘述的觀念，寫成C語言程式碼如下：

void creat()
{
    s.num[0]= 1;
    int i, count = 1, j, r = 0, v, k;
    for (j = 0; j < MAXLEN; j ++)
        toH[0].num[j] = 0;
    for (i = 1; i <= 10000; )
    {
        for (j = 0; j < count; j ++, i ++)
           if(i <= 10000)
           { 
               copy(i, i - 1);
               add(i);
           }
           else break;     
        mult2s(), count ++;     
    }
}

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

最後，再把所輸入的值，對應結構陣列印出即可：

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

By David.K

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