Posted on 2010-08-06 09:00
MiYu 閱讀(1276)
評論(0) 編輯 收藏 引用 所屬分類:
ACM ( 水題 ) 、
ACM ( 遞推 & 遞歸 )
//MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋題目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2064題目描述:
漢諾塔III
約19世紀末，在歐州的商店中出售一種智力玩具，在一塊銅板上有三根桿，最左邊的桿上自上而下、由小到大順序串著由64個圓盤構(gòu)成的塔。目的是將最左邊桿上的盤全部移到右邊的桿上，條件是一次只能移動一個盤，且不允許大盤放在小盤的上面。
現(xiàn)在我們改變游戲的玩法，不允許直接從最左(右)邊移到最右(左)邊(每次移動一定是移到中間桿或從中間移出)，也不允許大盤放到下盤的上面。
Daisy已經(jīng)做過原來的漢諾塔問題和漢諾塔II，但碰到這個問題時，她想了很久都不能解決，現(xiàn)在請你幫助她。現(xiàn)在有N個圓盤，她至少多少次移動才能把這些圓盤從最左邊移到最右邊？
漢諾塔是個很經(jīng)典的遞推實例, 如果規(guī)則沒這么變態(tài)，允許直接從1跨越到3，那n個盤最少需要2n - 1次。
而這里增加了一些新的規(guī)則, 我們可以如下分析, 怎樣把
n個盤從
1搬到
3 :
第1步:初始狀態(tài):
第2步:把上面的n-1個盤移到第3號桿上:
第3步:把第n個盤從1移到2:
第4步:把前n-1個從3移到1，給第個盤讓路:
第5步:把第n個盤從2移到3:
第6步:把前n-1個從移到3，完成移動:
我們設f(n)為把n個盤從1移到3所需要的步數(shù)，當然也等于從3移到1的步數(shù)。
由上面的圖我們可以看到,要想把第n個盤從1移到3，需要3個步驟 :
1.) 把前n-1個從1移動3 .
2.) 第n個盤要從1->2->3經(jīng)歷2步.
3.) 而前n-1個盤需要先 3->1 ( 這是為了給 第n個盤讓路 ), 最后再 1->3。
∴f(n) = 3 × f(n-1) + 2;
f(1) = 2;
這樣我們就得到了這一題的遞推公式, 當然我們可以做進一步的優(yōu)化 , 優(yōu)化方法如下:
f(n) = 3 × f(n-1) + 2
f(1) = 2
=>
f(n) + 1 = 3 × [f(n-1) + 1]
f(1) + 1 = 2 + 1 = 3
=>
f(n) + 1 = 3n
=>
f(n) = 3n - 1
最后貼上代碼 :
//MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋
#include <iostream>
#include <cmath>
using namespace std;
long long myPow ( int n , int e )
{
long long mlt = 1;
for ( int i = 1; i <= e ; ++ i )
{
mlt *= n;
}
return mlt;
}
int main ()
{
int N;
while ( cin >> N )
{
cout << myPow ( 3, N ) - 1 << endl;
}
return 0;
}