Highslide for Wordpress Plugin

說明文摘自:http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/HanoiTower.htm

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

事實上,若有n個盤子,則移動完畢所需之次數為2n – 1,所以當盤數為64時,則所需次數為: 264– 1 = 18446744073709551615 為5.05390248594782e+16年,也就是約5000世紀,如果對這數字沒什麼概念,就假設每秒鐘搬一個盤子好了,也要約5850億年左右。

其搬移的演算法如下:

假使n=1,則搬移第一個盤子從A到C

否則

  1. 搬移n-1個盤子從A到B
  2. 搬移第n個盤子從A到C
  3. 搬移n-1個盤子從B到C

   1: #include<stdio.h>

   2: #include<stdlib.h>

   3: #include<math.h>

   4: void hanoi(int n, char A, char B, char C);

   5: int main()

   6: {

   7:     int n;

   8:     double i;

   9:     printf("請輸入盤數:");

  10:     scanf("%d",&n);

  11:     hanoi(n,'A','B','C');

  12:     i=pow(2,n)-1;

  13:     printf("\n共花了%.0lf次處理\n",i);

  14:     system("pause");

  15:     return 0;

  16: }

  17: void hanoi(int n, char A, char B, char C)

  18: {

  19:     if(n==1)printf("將盤子1從%c拿到%c\n",A,C);

  20:     else

  21:     {

  22:         hanoi(n-1,A,C,B);

  23:         printf("將盤子%d從%c拿到%c\n",n,A,C);

  24:         hanoi(n-1,B,A,C);

  25:     }

  26: }

以上程式碼效果是利用Windows Live Writer+Code Snippet所達成。

Related Posts with Thumbnails
留下迴響