Tower of Hanoi

三、河內塔遊戲（Tower of Hanoi）
河內塔遊戲中有三根支架A、B、C，每根支架最多可放n個大小不同、中心挖孔的圓盤，大圓盤不得放在小圓盤上面。起先n個圓盤均置於支架A上（如圖一所示，以n=3為例）。今欲將這n個圓盤從支架A搬到支架C，每次只能搬一個盤子，支架B當作暫存處，請問共須搬動多少次的盤子才能完成？

請寫一個非遞迴（non-recursive）程式來處理這個問題。為簡單起見，這n個圓盤以數字1到n來表示，大數字代表大盤子，圓盤置於支架之情形用橫式表示，請參考Sample
Output。程式開始時需讀入圓盤之個數n（3≦n≦8），然後顯示支架A、B、C上圓盤放置情形（參考Sample
Output，以n=3為例），當搬動之次數為5之倍數（5,
10、15、…）時，需顯示A、B、C支架上圓盤放置之情形，並印出已經搬動盤子的次數。螢幕印滿後暫停，按任何鍵再繼續執行，直到完成後，顯示此n個盤子已搬至支架C上，並印出搬動之總次數。

Sample Output：
請輸入圓盤數目： 3
*************************
起始狀態：
支架A： 3 2 1
支架B：
支架C：
*************************
搬了5次之後
支架A： 1
支架B： 2
支架C： 3
*************************
：
：
：
*************************
共搬了7次才完成
支架A：
支架B：
支架C： 3 2 1
　

困難度：**
時間複雜度：O(n)
程式語言：C++
預估時間：1 小時

解題原理：
1. 根據 Glenn C. Rhoads 提出對河內塔非遞迴解方式，以二進位方式進行操作，得到驚人的結果。其原理是假設有3個支架分別為0~2，一開始第一個支架為0，如果目前要移動的盤子是偶數，則要移動到第1個支架，否則移動到第2個支架
2. 計算螢幕中印出的行數，進行處理
3. 使用向量儲存目前支架的集合，每五次印出
4. 完成

程式下載

原碼下載

參考來源：中山大學八十九學年度電腦程式設計競賽 試題 三