(連結已經修復)

遞迴(Recurrence)在程式語言中,是一個很有趣的東西!!
而「河內塔」(Hanoi Tower),是一個遞迴的經典題目
凡舉大學資訊相關類科系,都應該有碰過...

 

 

 

所謂的遞迴,簡單的說,就是自己呼叫自己。
但是呼叫自己必須有一個「結束點」,否則就會無止盡直到記憶體用盡當機....

ex. void example (int num) { if(num>1){ example(num-1); }


河內塔的規則
(1) 一次只能搬移一個盤
(2) 小盤可以移到大盤上面,大盤不可以移到小盤上面。
(3) 全部的盤都搬到另外一個塔上,就算完成

  四個盤的部份移動情形   


  以下是 一個盤 ~ 四個盤 的最速解法   
[ 左邊數字代表 被移動的盤子的編號 ] 
[ 右邊英文代表,從哪一柱一到哪一柱 ]




  有趣的來了,如果仔細看的話,會發現移動盤子的順序是有規律的 !!!  


很有趣吧,可以自己排排看是不是這麼一回事~~

簡而言之,最速解法是

1) 先指定「起始柱」和「目標柱」,剩下的那個柱就是「暫存柱」,而你的盤數為 n

2) 先把 n-1 個盤全部移到 「暫存柱」

3) 再把 第 n 個盤 移動到 「目標柱」

4) 最後,把放在「暫存柱」的所有盤全部移到「目標柱」

5) 完成~!!


有沒發現,它們之間存在著遞迴關係!!

如果你想要讓電腦解出某個盤數的解法,可以寫一個這樣的遞迴程式 (C語言)

#include<stdio.h>

void hanoi (int num, char start, char temp, char end ){

   if( num > 0 ){

 

 

   hanoi ( num-1 , start , end , temp );

   printf("%d  %c -> %c  \n" , num, start , end ); /* 顯示移動狀況 */

   hanoi ( num-1 , temp , start , end);

  }

}


int main(){

    hanoi ( 4 , 'A' , 'B' ,'C' );
    /*四個盤子,以A為起始柱,以C為目標柱,以B為暫存柱*/
  
    return 0;

}


創作者介紹

Frank's 資訊科技潮流站

finalfrank 發表在 痞客邦 PIXNET 留言(5) 人氣()


留言列表 (5)

發表留言
  • 寂情
  • hanoi ( num-1 , start , end, temp );

    printf("%d %c -> %c \n" , num, start , end ); /* 顯示移動狀況 */

    hanoi ( num-1 , temp , start ,end );

    CODE要改醬才對哦
  • 謝謝!!已經修正!!之前發文沒注意到~ 當時沒看清楚Function傳入的值..感恩~
    還好有你提醒 不然這篇文可能會遺臭萬年~ 真的感謝你啦~

    finalfrank 於 2008/12/17 15:27 回覆

  • sherry
  • 有沒有不用不是recursion的寫法?用for loop的
  • 閣下可以試試看暴力法...

    finalfrank 於 2010/09/20 19:19 回覆

  • Dora
  • 河內塔的別名?

    最近孩子在玩Tower of Hanoi,但台灣好像不是很流行???
    我一直在找Hanoi的"台式譯名"或比較口語的說法,
    不知Frank知道嗎?
    附上孩子們玩河內塔的影片,有空可以瞧瞧 :)
    http://www.youtube.com/schoko2004
  • 好厲害!居然可以徒手玩耶!這種遊戲我老了,只能寫程式交給電腦慢慢玩了.........
    另外,河內塔有人翻 漢諾伊塔,但比較少見就是了

    而在台灣不是不流行,因為它在資訊界幾乎是必修課....

    finalfrank 於 2010/09/20 19:22 回覆

  • Zelda
  • ....不能下載呢
    能不能做出自動的呢?
    一開始先選定哪裡移到哪裡
    選定完之後,他自動排列過去
  • 魚兒
  • 真是太謝謝了!
    本來都一直看不懂河內塔的規則~
    你寫得好詳細啊:DD
找更多相關文章與討論