Frank's 資訊科技潮流站

(連結已經修復)

 

 

 

所謂的遞迴，簡單的說，就是自己呼叫自己。
但是呼叫自己必須有一個「結束點」，否則就會無止盡直到記憶體用盡當機....
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;

}