2013-10-26 16:04:02Morris

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

內容 :

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

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

輸入說明 :

        每個測資檔包含多筆測資。每筆測資包含三行,第一行是一個正整數N (1<=N<=10000),代表圓盤的個數。第二行及第三行分別代表圓盤的初始與目標狀態。每行有N個正整數,第i個數Si代表第i小的圓盤是套在Si上,其中Si只可能是123。當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

範例輸出 :

6
7
3
0
147483633

提示 :

出處 :

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;
}