漢諾塔III

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 33200 Accepted Submission(s): 16027

Problem Description

約19世紀(jì)末，在歐州的商店中出售一種智力玩具，在一塊銅板上有三根桿，最左邊的桿上自上而下、由小到大順序串著由64個圓盤構(gòu)成的塔。目的是將最左邊桿上的盤全部移到右邊的桿上，條件是一次只能移動一個盤，且不允許大盤放在小盤的上面。
現(xiàn)在我們改變游戲的玩法，不允許直接從最左(右)邊移到最右(左)邊(每次移動一定是移到中間桿或從中間移出)，也不允許大盤放到下盤的上面。
Daisy已經(jīng)做過原來的漢諾塔問題和漢諾塔II，但碰到這個問題時，她想了很久都不能解決，現(xiàn)在請你幫助她?，F(xiàn)在有N個圓盤，她至少多少次移動才能把這些圓盤從最左邊移到最右邊？

Input

包含多組數(shù)據(jù)，每次輸入一個N值(1<=N=35)。

Output

對于每組數(shù)據(jù)，輸出移動最小的次數(shù)。

Sample Input

1
3
12

Sample Output

2
26
531440

解題思路：

假設(shè)將n層塔從A經(jīng)B挪到C需要f[n]步。那么具體的移動過程可以這樣看：將上面n-1層從A經(jīng)B挪到C需要f[n-1]步，再將第n層從A挪到B，需要一步，再將上n-1層從C經(jīng)B挪到A，需要f[n-1]步，再將第n層從B挪到C，需要一步，再將上n-1層從A經(jīng)B挪到C，需要f[n-1]步，總計3*f[n-1] + 2步，其中 f[1] = 2;

代碼：

#include <stdio.h>
long long dp[36] = {0, 2};
int main()
{
    int n;
    for(n = 2; n < 36; n++)
        dp[n] = dp[n-1] * 3 + 2;
    while(scanf("%d", &n) == 1) 
        printf("%lld\n", dp[n]);
    return 0;
}

點贊

評論

舉報