回分類題庫
d068: 6.三色河內塔
關鍵字: 103年台中區複賽

測資點 : 4 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 77 Times / 66 Users | Submit : 154 Times / 69 Users | Accepted rate : 96%
題目加入時間 : 2015-09-07 14:54

Content: 简体中文

本題為三色河內塔,雙色河內塔請參閱97年雲嘉區第五題。 

下圖為河內塔問題(Towers of Hanoi)的一種,共有A、B、C三個柱子,一開始A柱子可以放個數為3倍數的套環,都是花白灰相間的三種不同顏色套環,每種大小的套環都有三個,花色在上,白色在中,灰色在下。套環依序由上到下的編號分別為1~N,假設每次的移動都只能從柱子的頂端移動一個套環,搬到其他柱子放,而且編號較大的套環永遠都不能放在較小套環的上方。最後要將所有花套環移動到A,白套環移動到B,以及所有灰套環移動到C。請寫出一個程式,輸入套環總數(為 3的倍數,包含花白灰三種套環),計算並輸出所有套環的最佳移動順序(移動次數最少)及其移動次數。

 

Input:

輸入一個整數n,n為3的倍數。

Output:

請依序輸出每個移動,包括套環(ring)編號(1~n),從一個柱名稱移動(=>)到另一個柱名稱(A、B、或C)。最後一列輸出總移動次數。

Sample Input:help

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

輸入2:
6

Sample Output :

輸出1:
ring 1 : A => C
ring 2 : A => B
ring 1 : C => B
ring 3 : A => C
ring 1 : B => A
共需5個移動

輸出2:
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 => C
ring 2 : B => A
ring 1 : C => A
ring 3 : B => C
ring 1 : A => B
ring 2 : A => C
ring 1 : B => C
ring 5 : A => B
ring 1 : C => A
ring 2 : C => B
ring 1 : A => B
ring 3 : C => A
ring 1 : B => C
ring 2 : B => A
ring 1 : C => A
ring 4 : C => B
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 6 : A => C
ring 1 : B => C
ring 2 : B => A
ring 1 : C => A
ring 3 : B => C
ring 1 : A => B
ring 2 : A => C
ring 1 : B => C
ring 4 : B => A
ring 1 : C => A
ring 2 : C => B
共需42個移動

Hint :

Author :

103年台中區複賽 (管理員:sagit)

  Solve it!   Status Forum