受限漢諾塔問題

受限漢諾塔問題 古代有一個梵塔,塔内有3個基座A、B、C,開始時A基座上有64個盤子,盤子大小不等,大的在下,小的在上。有一個老和尚想把這64個盤子從A座移到C座,但（1）每次隻允許移動一個盤子；（2）在移動過程中在3個基座上的盤子都始終保持大盤在下,小盤在上；（3）任何移動要麼把一個盤子搬到B上，要麼從B上搬走一個盤子。請程式設計列印出移動過程 。

分析：把n個盤子從A移動到C可分五步完成

1）把1到n-1号盤子從A移動到C；

2）把n号盤子從A移動到B；

3）把1到n-1号盤子從C移動到A；

4）把n号盤子從B移動到C；

5）把1到n-1号盤子從A移動到C。

記void hanoi(int n, char a, char b, char c)為把n個盤子從A移動到C的函數，則可得

#include"stdio.h"

#include"stdlib.h"

#include"string.h"

int count=0;

void sxhanoi(int n, char a, char b, char c)

{

    if(n>0)

      { sxhanoi(n-1, a, b, c);

        printf("move %d: %c-> %c\n", n, a, b);

        count++;

        sxhanoi(n-1, c, b, a);

        printf("move %d: %c-> %c\n", n, b, c);

        count++;

        sxhanoi(n-1, a, b, c);

      }

}

int main()

{

  int n=3;

  char a='A';

  char b='B';

  char c='C';

  sxhanoi(n, a, b, c);

  printf("\ncount=%d\n", count);

  //system("pause");

 //return 0;

}

運作結果：

move 1: A-> B

move 1: B-> C

move 2: A-> B

move 1: C-> B

move 1: B-> A

move 2: B-> C

move 1: A-> B

move 1: B-> C

move 3: A-> B

move 1: C-> B

move 1: B-> A

move 2: C-> B

move 1: A-> B

move 1: B-> C

move 2: B-> A

move 1: C-> B

move 1: B-> A

move 3: B-> C

move 1: A-> B

move 1: B-> C

move 2: A-> B

move 1: C-> B

move 1: B-> A

move 2: B-> C

move 1: A-> B

move 1: B-> C

count=26

--------------------------------

Process exited after 0.9864 seconds with return value 0

請按任意鍵繼續. . .