Content:
简体中文
本題為三色河內塔,雙色河內塔請參閱97年雲嘉區第五題。
下圖為河內塔問題(Towers of Hanoi)的一種,共有A、B、C三個柱子,一開始A柱子可以放個數為3倍數的套環,都是花白灰相間的三種不同顏色套環,每種大小的套環都有三個,花色在上,白色在中,灰色在下。套環依序由上到下的編號分別為1~N,假設每次的移動都只能從柱子的頂端移動一個套環,搬到其他柱子放,而且編號較大的套環永遠都不能放在較小套環的上方。最後要將所有花套環移動到A,白套環移動到B,以及所有灰套環移動到C。請寫出一個程式,輸入套環總數(為 3的倍數,包含花白灰三種套環),計算並輸出所有套環的最佳移動順序(移動次數最少)及其移動次數。
Input:
Output:
Sample Input:
輸入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
: