b190: 97七區資訊學科5(改編)

內容

一個必有偶數層的河內塔，有 a b c 三根柱子，假設所有的環原本在 a 柱上，請將奇數號的環移到 b 柱上，偶數號的環移到 c 柱上，大的環不能疊在小的環上，請輸出移動過程和最少步數。

河內塔的規則為：
有三根柱子 a、b、c。a 桿上有 N 個(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。
要求按下列規則進行移動：

1. 每次只能移動一個圓盤，
2. 大盤不能疊在小盤上面。

輸入

每一組只有一個整數，代表有 n 個環。

4

輸出

輸出移動步驟時，需按照『ring x : y -> z’的格式，其中 x 為整數，y、z 為 a、b、c 其中一個。
最後在輸出最少步數。

ring 1 : a -> b
ring 2 : a -> c
ring 1 : b -> c
ring 3 : a -> b
ring 1 : c -> a
ring 2 : c -> b
ring 1 : a -> b
ring 4 : a -> c
ring 1 : b -> a
ring 2 : b -> c
ring 1 : a -> b
共移動了 11 步

解題思路

先觀察一個高度為 3 的河內塔正確移動的順序

要將第 3 盤從 a 柱移動到 b 柱但第 2 盤擋住了

要將第 2 盤從 a 柱移動到 c 柱但第 1 盤擋住了

將第 1 盤從 a 柱移動到 b 柱避面擋到第 2 盤移動

第 1 盤移開了，將第 2 盤從 a 柱移動到 c 柱

第 2 盤移開了，但又被移動到 b 柱的第 1 盤擋住了

將第 1 盤從 b 柱移動到 c 柱避面擋到第 3 盤移動

第 1 盤移開了，將第 3 盤從 a 柱移動到 b 柱 (第 3 盤移動完成)
第 2 盤經過剛才的移動剛好也在 c 柱上，不用動 (第 2 盤移動完成)
第 1 盤還在 c 柱，將他移到 b 柱 (第 1 盤移動完成)

可以發現如果要將某盤從 a 柱移到 b 柱，就必須將該盤上面的所有盤子移動到不是 a 或 b 的 c 柱，也就是說從最底層那盤為奇數盤，就以將他移動到 b 柱為目標，將它上面的盤子移動到 c 柱，等他移動到 b 柱後再移動上面那盤至 c 柱，如此循環直到全部的盤子都分配至正確的位置即可。

所以實際上就是用遞迴完成以下循環，直到要沒有要移動的盤子後結束

把要移動的盤子上面的盤子都移動到不相干的柱子上 → 移動要移動的盤子 → 把要移動的盤子變成他上面那個 → 回到開始

一些其他的細節請參考 b592

完整程式碼

AC (7ms, 92KB)

#include <stdio.h>

int n, count;
char list[100];

void dfs(int lv, char to)
{
    for (int i = lv; i; i--)
    {
        if (lv == n)
            to = i & 1 ? 'b' : 'c';
        if (list[i] != to)
        {
            dfs(i - 1, 294 - list[i] - to);
            printf("ring %d : %c -> %c\n", i, list[i], to);
            list[i] = to;
            count++;
        }
    }
}

int main()
{
    while (scanf(" %d", &n) == 1)
    {
        count = 0;
        for (int i = 1; i <= n; i++)
            list[i] = 'a';
        dfs(n, '?');
        printf("共移動了 %d 步\n", count);
    }
    return 0;
}