a227: 三龍杯 -> 河內之塔

內容

河內之塔(Towers of Hanoi)是法國人 M.Claus(Lucas)於 1883 年從泰國帶至法國的，河內為越戰時北越的首都，即現在的胡志明市；1883 年法國數學家 Edouard Lucas 曾提及這個故事，據說創世紀時 Benares 有一座波羅教塔，是由三支鑽石棒（Pag）所支撐，開始時神在第一根棒上放置 64 個由上至下依由小至大排列的金盤（Disc），並命令僧侶將所有的金盤從第一根石棒移至第三根石棒，且搬運過程中遵守大盤子在小盤子之下的原則，若每日僅搬一個盤子，則當盤子全數搬運完畢之時，此塔將毀損，而也就是世界末日來臨之時。

A            B          C

輸入

每行有一個正整數 N N <= 15

1
2
3

輸出

請輸出把 A 上 N 個環移動到 C 的方法

( 剛開始 A 層最下方的 Ring 編號為 N 最上方的編號為 1 )

Move ring 1 from A to C

Move ring 1 from A to B
Move ring 2 from A to C
Move ring 1 from B to C

Move ring 1 from A to C
Move ring 2 from A to B
Move ring 1 from C to B
Move ring 3 from A to C
Move ring 1 from B to A
Move ring 2 from B to C
Move ring 1 from A to C

解題思路

參考 b190，這題更簡單，不用把奇偶分配在不同的柱子上，直接全部丟到 C 柱即可。

完整程式碼

AC (20ms, 108KB)

#include <stdio.h>

int n;
char list[100];

void dfs(int lv, char to)
{
    for (int i = lv; i; i--)
    {
        if (list[i] != to)
        {
            dfs(i - 1, 198 - list[i] - to);
            printf("Move ring %d from %c to %c\n", i, list[i], to);
            list[i] = to;
        }
    }
}

int main()
{
    while (scanf(" %d", &n) == 1)
    {
        for (int i = 1; i <= n; i++)
            list[i] = 'A';
        dfs(n, 'C');
        putchar('\n');
    }
    return 0;
}