漢諾塔問題hdu 2065——找規律

這類題目就是紙上模拟，找規律。

問題描述：在一塊銅闆上有三根杆，目的是将最左邊杆上的盤全部移到右邊的杆上，條件是不允許直接從最左(右)邊移到最右(左)邊(每次移動一定是移到中間杆或從中間移出)，也不允許大盤放到下盤的上面

問：現在有N個圓盤，她至少多少次移動才能把這些圓盤從最左邊移到最右邊？ 

紙上模拟：模拟之後發現将圓盤從左移動到中間的次數=從中間移到右邊=1/2從左邊移到右邊次數

f(n)表示至少n次移動才能把這些圓盤從最左邊移到中間    a(n)表示第n個圓盤移動的次數

當n=1時，f(1)=1    a(1)=1

當n=2時，f(2)=4     a(1)=3   a(2)=1

當n=3時，f(3)=13    a(1)=9   a(2)=3   a(3)=1

規律：a(n)呈現以3為公比的等比數列，f(n)為等比數列的和

是以：從左邊移到中間需：s(n)=(3^n-1)/2;

從左邊移到右邊需：s(n)=(3^n-1);

代碼：

#include<iostream>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        long long sum=1;
        for(int i=0;i<n;i++)
        sum=sum*3;
        sum=sum-1;
        cout<<sum<<endl;
     } 
}      

View Code

轉載于:https://www.cnblogs.com/Aiahtwo/p/10460535.html