b190: 97七區資訊學科5(改編)
Tags : 河內塔 遞迴
Accepted rate : 111人/166人 ( 67% ) [非即時]
評分方式:
Tolerant

最近更新 : 2008-12-24 20:11

Content
一個必有偶數層的河內塔,有a b c三根柱子,假設所有的環原本在a柱上,請將奇數號的環移到b柱上,偶數號的環移到c柱上,大的環不能疊在小的環上,請輸出移動過程和最少步數。

河內塔的規則為:
有三根柱子a、b、c。a桿上有N個(N>1)穿孔圓盤,盤的尺寸由下到上依次變小。
要求按下列規則進行移動:
1. 每次只能移動一個圓盤,
2. 大盤不能疊在小盤上面。
Input
每一組只有一個整數,代表有n個環。
Output

輸出移動步驟時,需按照『ring x : y -> z'的格式,其中x為整數,y、z為a、b、c其中一個。
最後在輸出最少步數。
Sample Input
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 步
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (70%): 1.0s , <1K
公開 測資點#1 (30%): 1.0s , <1K
Hint :
請善用遞迴(以兩層分隔)
Tags:
河內塔 遞迴
出處:
97學年度彰雲嘉區資訊學科能力競賽 [管理者:
taichunmin (和風信使)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」