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