[ZJ][遞迴] a268 河內塔問題＠Morris' Blog

2013-10-26 16:04:02| 人氣4,909| 回應0 | 上一篇 | 下一篇

[ZJ][遞迴] a268 河內塔問題

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

相信大家都知道著名的河內塔問題。簡單來說，就是有三根柱子，柱子上可以套多個圓盤，圓盤大小都不同，但是每次移動一個圓盤的時候都不能有較大的圓盤在較小的圓盤上。一般來說一開始的初始狀態是所有圓盤都在同一根柱子上，目標是在不違反規則的條件下，至少移動幾次圓盤可使所有圓盤移動到另外一根柱子上。

我們的問題比較複雜一點，給定圓盤的初始狀態以及目標狀態，問至少要移動幾次能從初始狀態到目標狀態。

輸入說明：

每個測資檔包含多筆測資。每筆測資包含三行，第一行是一個正整數N (1<=N<=10000)，代表圓盤的個數。第二行及第三行分別代表圓盤的初始與目標狀態。每行有N個正整數，第i個數S_i代表第i小的圓盤是套在S_i上，其中S_i只可能是1或2或3。當N=0時代表輸入結束。

輸出說明：

對每筆測資輸出一行，代表從初始狀態到目標狀態至少要移動幾次圓盤。由於答案可能很大，請輸出mod 1,000,000,007的結果。

範例輸入：

4
1 1 1 1
1 2 2 1
3
1 1 1
2 2 2
3
1 2 3
3 2 1
4
1 1 1 1
1 1 1 1
31
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0

範例輸出：

提示：

出處：

2011成功高中校內賽複賽第四題 (管理：david942j)

題目雖然要求一個起始狀態轉移到目標狀態的最少步數。

但是考慮一下後，先討論將一個凌亂狀態轉移到其中一個目標柱子上(與最原始問題目標相同)。

問題：凌亂狀態轉移到其中一個目標柱上的最少步數

當前有 n 個盤子，目標柱編號 c，三柱分別為 a, b, c。
考慮最大盤 n-th 盤

(1) 如果最大盤在 c 上時，則直接考慮當前有 n-1 個盤子，目標柱編號 c。
=> 明顯地知道最少步數時，這個最大盤必然不會動。

(2) 如果最大盤在 a 上，必須將剩餘 n-1 個盤子集中移動到 b，
最後將最大盤從 a 搬到 c，此時可以調用一般河內塔，將 n-1 個盤子從 b 轉移到 c。

(3) 如果最大盤在 b 上，類同於 (2) 的操作步數。

這個問題可以在 O(n) 以內完成。

問題：凌亂狀態A轉移到另一個凌亂狀態B的最少步數

一樣從最大盤 n-th 下手

(1) 對於最大盤 A[n] == B[n]，直接調用 n-1 的凌亂狀態A轉移到另一個凌亂狀態B
=> 明顯地知道最少步數時，這個最大盤必然不會動。

(2) 對於最大盤 A[n] != B[n]，令 buf 柱為非 A[n] 非 B[n] 的柱子。
先將凌亂 n-1 狀態A 般至 buf 柱 // 請使用上一個問題的定義。
再將 A-n-th 搬至 B[n] 柱，再考慮 n-1 個盤子的情況。

由於這個做法本身在 (2) 的操作時，會將 n-1 個盤子搬到同一個柱子上，不能使用 O(n) 標記，
維護一個前綴設定，來加快所有操作。

如果不這麼考慮會是 O(n^2)，加入前綴設定達到 O(n)。

#include <stdio.h>
#define mod 1000000007
int init[10005], goal[10005], n;
long long mod2[10005] = {1LL};
long long ret = 0;
int labelprefix, label;
void hanoiArbitrarily(int n, int goal) {
    if(n == 0)
        return;
    if(labelprefix >= n) {
        init[n] = label;
        if(goal != label) {
            ret += mod2[n]-1;
            ret %= mod;
        }
        return;
    }
    if(init[n] != goal) {
        int target = 1;//temp buffer.
        if(init[n] == target)    target++;
        if(goal == target)        target++;
        if(init[n] == target)    target++;
        hanoiArbitrarily(n-1, target);// move other into buffer.
        init[n] = goal;//move n-th disk to goal.
        ret++;
        ret += mod2[n-1]-1;
        ret %= mod;
    } else {
        hanoiArbitrarily(n-1, goal);
    }
}
void hanoi(int n) {
    if(n == 0)
        return;
    if(labelprefix >= n)
        init[n] = label;
    if(init[n] != goal[n]) {
        int target = 1;
        if(init[n] == target)    target++;
        if(goal[n] == target)    target++;
        if(init[n] == target)    target++;
        hanoiArbitrarily(n-1, target);
        /*for(int i = 1; i < n; i++)
            init[i] = target;*/
        labelprefix = n-1, label = target;
        ret++;
        init[n] = goal[n];//move n-th disk to goal.
    }
    hanoi(n-1);
}
int main() {
    int i;
    for(i = 1; i < 10005; i++)
        mod2[i] = (mod2[i-1]*2)%mod;
    while(scanf("%d", &n) == 1 && n) {
        labelprefix = label = 0;
        for(i = 1; i <= n; i++)
            scanf("%d", &init[i]);
        for(i = 1; i <= n; i++)
            scanf("%d", &goal[i]);
        ret = 0;
        hanoi(n);
        printf("%lld\n", ret%mod);
    }
    return 0;
}

我要檢舉

#a268#河內塔問題

台長： Morris

您可能對以下文章有興趣

[ZJ][D&C] a638. Closest-pair problem

[ZJ][字串處理] d477. 古韵之同心锁

[ZJ] a631. 11. LED Decoder

[ZJ] a812: 2013高雄市能力競賽高中組 3. 動物排隊

人氣(4,909) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: ZeroJudge |
此分類下一篇:[ZJ][D&C] d847 2D rank finding problem
此分類上一篇:[ZJ][擴充歐幾里德] d374. 6. X^2 ≡ 1 (mod M)

回應(0)