網頁

2019年11月25日 星期一

C語言 河內塔

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

  1. 一次只能移動一個圓盤
  2. 圓盤一定要疊在比較大的圓盤上
依照這個規則我們可以推論得出,有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);
    printf("%llu\n", cnt);
}




👉【幫我們一個忙!】👈

👋如果您喜歡這篇文章,請在下方按5個Like!
 ❤您的支持是我們最大的動力!

您只要登入帳號(Facebook、Google),在下方按5個Like,我們就會收到來自LikeCoin基金會的贊助。
您只需要支持我們,完全不會花到錢!