題目 1684:
數(shù)據(jù)結(jié)構(gòu)-n階Hanoi塔問題
時間限制: 2s
內(nèi)存限制: 96MB 提交: 677 解決: 225
題目描述
假設(shè)有三個分別命名為X、Y和Z的塔座，在塔座X上插有n個直徑大小各不相同、依小到大編號為1,2,...,n的圓盤。現(xiàn)要求將X軸上的n個圓盤移至塔座Z上并仍按同樣順序疊排，圓盤移動時必須遵循下列規(guī)則：
1）每次只能移動一個圓盤；
2）圓盤可以插在X、Y和Z中的任一塔座上；
3）任何時刻都不能將一個較大的圓盤壓在較小的圓盤之上。
如何實現(xiàn)移動圓盤的操作呢？當n=1時，問題比較簡單，只要將編號為1的圓盤從塔座X直接移至塔座Z上即可；當n>1時，需利用塔座Y作輔助塔座，若能設(shè)法將壓在編號為n的圓盤之上的n-1個圓盤從塔座X（依照上述法則）移至塔座Y上，則可先將編號為n的圓盤從塔座X移至塔座Z上，然后再將塔座Y上的n-1個圓盤（依照上述法則）移至塔座Z上。而如何將n-1個圓盤從一個塔座移至另一個塔座的問題是一個和原問題具有相同特征屬性的問題，只是問題的規(guī)模小1，因此可以用同樣的方法求解。由此可得如下圖算法所示的求解n階Hanoi塔問題的C函數(shù)。
圖：求解n階Hanoi塔問題的C函數(shù)
現(xiàn)在就請你將上述算法實現(xiàn)吧。
輸入格式
輸入數(shù)據(jù)有多組，每組1個整數(shù)n，表示Hanoi塔的階數(shù)。
輸出格式
將每次移動（move）按照以下格式輸出：%2d. Move disk %d from %c to %c\n
上述格式中第一個整數(shù)表示第幾次移動，第二個整數(shù)表示移動第幾個圓盤，后兩個字符表示將圓盤從哪個塔座移至哪個塔座上。每組輸出后面輸出一個空行。
樣例輸入
1 2 3
樣例輸出
1. Move disk 1 from X to Z 1. Move disk 1 from X to Y 2. Move disk 2 from X to Z 3. Move disk 1 from Y to Z 1. Move disk 1 from X to Z 2. Move disk 2 from X to Y 3. Move disk 1 from Z to Y 4. Move disk 3 from X to Z 5. Move disk 1 from Y to X 6. Move disk 2 from Y to Z 7. Move disk 1 from X to Z