Posted on 2010-08-06 15:21
MiYu 閱讀(759)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
ACM ( 數(shù)論 )
MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(zhuǎn)載自 ______________白白の屋
題目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2077
題目描述:
Problem Description
還記得漢諾塔III嗎？他的規(guī)則是這樣的：不允許直接從最左(右)邊移到最右(左)邊(每次移動(dòng)一定是移到中間桿或從中間移出)，也不允許大盤放到小盤的上面。xhd在想如果我們?cè)试S最大的盤子放到最上面會(huì)怎么樣呢？（只允許最大的放在最上面）當(dāng)然最后需要的結(jié)果是盤子從小到大排在最右邊。
Input
輸入數(shù)據(jù)的第一行是一個(gè)數(shù)據(jù)T，表示有T組數(shù)據(jù)。
每組數(shù)據(jù)有一個(gè)正整數(shù)n(1 <= n <= 20)，表示有n個(gè)盤子。
Output
對(duì)于每組輸入數(shù)據(jù)，最少需要的擺放次數(shù)。
Sample Input
2
1
10
Sample Output
2
19684
因?yàn)樽畲蟮目梢苑旁谧钌厦? 所以就不能像 漢諾塔III那樣把前n-1個(gè)盤全部從1->3了.
只要把前n-1個(gè)盤從1->2,然后把第n個(gè)盤1->2->3,然后把前n-1個(gè)盤2->3, 這樣就完成了.
所以,問題現(xiàn)在轉(zhuǎn)換成 n 個(gè)盤
移動(dòng)一步需要多少次. 我們可以看到, 除了最后一個(gè)最
大的盤n以外, 前n-1個(gè)盤的移動(dòng)方式是和 漢諾塔III的規(guī)則是一樣的.所以我們先把前
n-2 個(gè)盤 1->3, 然后把 第n-1個(gè)盤 1->2, 再把前n-2個(gè)盤 3->2, 這樣就把前 n-1個(gè)盤
1->2 移動(dòng)了一步.
因?yàn)榘?n 個(gè)盤 按找漢諾塔III的方法 1->3 需要 3
n -1 推導(dǎo)見 :
HDOJ HDU 2064 漢諾塔III ACM 2064 IN HDU
所以由上面描述的步驟知道把 n 個(gè)盤移動(dòng)一步需要 : f(n) = f(n-1) + ( 3
n-1 - 1 ) + 1 = f (n-1) + 3
n-1 而 f(1) = 1
由遞推式化簡(jiǎn)得: f(n) = 3
n-1 + 3
n-2 + ...+ 3 + 1 = ( 3
n -1 ) / 2
所以按 漢諾塔IV的規(guī)則, 移動(dòng) n 個(gè)盤 需要 : m(n) = 2 * f (n-1) + 2 = 3
n-1 + 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 ) + 1 << endl;
}
return 0;
}