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