CHAWTeam: C語言河內塔

2019年11月25日星期一

C語言河內塔

河內塔就是有三根桿子，每個桿子穿著若干個圓盤，將小的圓盤疊在大的上面。今欲將圓盤從第一根桿子全部移動到第二根，須遵守規則如下：

一次只能移動一個圓盤
圓盤一定要疊在比較大的圓盤上

依照這個規則我們可以推論得出，有n個圓盤堆疊而成的河內塔，至少需要2^n -1次的步驟才能移動好所有的圓盤。
利用簡單的遞迴方法，可以顯示出每一個層數的河內塔問題移動所需的步數。

#include <stdio.h>
unsigned long long cnt = 0;
void tower(int n, int i, int j)
{
    int m;
    if (i == 0) {
        m = j == 1 ? 2 : 1;
    } else if (i == 1) {
        m = j == 0 ? 2 : 0;
    } else if (i == 2) {
        m = j == 0 ? 1 : 0;
    }

    if (n == 1) {
        printf("Move disk %d from %c to %c\n", 1, i + 'A', j + 'A');
        ++cnt;
    } else {
        tower(n-1, i, m);
        printf("Move disk %d from %c to %c\n", n, i + 'A', j + 'A');
        tower(n-1, m, j);
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    tower(n, 0, 2);