回分類題庫
b023: 河內塔
關鍵字: 遞迴

測資點 : 5 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 1729 Times / 1507 Users | Submit : 2755 Times / 1564 Users | Accepted rate : 96%
題目加入時間 : 2011-10-14 00:53

Content: 简体中文

河內塔(Tower of Hanoi)這個遊戲源自古印度的一個傳說,它的規則如下:

  1. 有 1、2、3 等3根柱子。
  2. 一開始在 1 號柱子上由上到下有 1、2、3、…、N 等 N個環。
  3. 每次只能移動一個環到另一根柱子,而且號碼大的環不可以放在比它小的環上。
  4. 反覆移動這些環,直到所有的環都移到 3 號柱子上。

要完成這個動作,你可以先把 1~N-1 號環移到 2 號柱子上,然後把 N 號環移到 3 號柱子上,再把 1~N-1 號環移到 3 號柱子上。而如何將 1~N-1 號環移到另一根柱子上,其實可以再分解成把 1~N-2 號先移走,再移動 N-1 號的方式,然後再把 1~N-2 號移回來,注意到了嗎,這就是遞迴。

現在請你寫一個程式,印出將這 N 個環移到另一根柱子的過程。

Input:

輸入一個正整數 N (3<=N<=15)。

Output:

請依照下面輸出範例的格式,印出這些環移動的過程。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3

Sample Output :

Ring 1 from 1 to 3
Ring 2 from 1 to 2
Ring 1 from 3 to 2
Ring 3 from 1 to 3
Ring 1 from 2 to 1
Ring 2 from 2 to 3
Ring 1 from 1 to 3

Hint :

Author :

遞迴 (管理員:sagit)

  Solve it!   Status Forum