回分類題庫
d030: 97年雲嘉區第五題
關鍵字: 97年雲嘉區複賽

測資點 : 5 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 85 Times / 77 Users | Submit : 377 Times / 91 Users | Accepted rate : 85%
題目加入時間 : 2011-09-12 23:09

Content: 简体中文

下圖為Tower of Hanoi (漢諾塔)的一種,其規則如下:

  1. 移動前的狀態如圖一所示,有A、B、C三個桿子,其中在A處有灰白相間的兩種套環,每種大小的套環都有兩個,奇數為白在上,偶數為灰在下。
  2. 假設每次只能移動一個套環,而且在每次移動的過程中,大套環不可置於小套環之上,若為相同大小的套環則灰套環不可置於白套環之上。
  3. 移動後的狀態如圖二所示,要將所有的白套環移動到B處,以及所有的灰套環移動到C處。

 

圖一:移動前的狀態

圖二: 移動後的狀態

請寫出一個程式,輸入套環總數(為偶數個,包含灰白兩種套環),計算並輸出所有套環的最佳移動順序及所需步驟數(最少的移動步驟)。

Input:

輸入一個正整數 N (2<=N<=16),且 N 為偶數。

Output:

請依照下面輸出範例的格式,輸出最佳移動順序及所需的最少步驟數

Sample Input:help

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

Sample Output :

ring 1 : A => B
ring 2 : A => C
ring 1 : B => C
ring 3 : A => B
ring 1 : C => A
ring 2 : C => B
ring 1 : A => B
ring 4 : A => C
ring 1 : B => A
ring 2 : B => C
ring 1 : A => B
共需11個步驟

Hint :

Author :

97年雲嘉區複賽 (管理員:sagit)

  Solve it!   Status Forum