HDU——2064ハノータIII
1397 ワード
ハノータIII
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 13272 Accepted Submission(s): 6096
Problem Description
約19世紀末、欧州の商店で知能玩具が販売され、銅板に3本の棒があり、一番左の棒には上から下へ、64個の円盤からなる塔が小さい順に並んでいた.一番左のレバーの上のディスクをすべて右のレバーに移動することを目的とし、一度に1つのディスクしか移動できないことを条件とし、大皿を小皿の上に置くことは許されない.
今、ゲームの遊び方を変えて、一番左(右)から一番右(左)に直接移動することは許されません(移動するたびに必ず中間棒に移動したり、真ん中から移動したりします)、大皿を下盤の上に置くことも許されません.
Daisyはすでに元のハノータ問題とハノータIIをしたことがあるが、この問題に出会ったとき、彼女は長い間解決できないと思っていたので、今助けてください.今N個の円盤があって、彼女は少なくとも何回移動してこれらの円盤を一番左から一番右に移動することができますか?
Input
複数組のデータを含み、毎回1つのN値(1<=N=35)を入力する.
Output
データのセットごとに、移動の最小回数を出力します.
Sample Input
Sample Output
式:Fn=3*F(n-1)+2、すなわちFn=3^n-1
コード:
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 13272 Accepted Submission(s): 6096
Problem Description
約19世紀末、欧州の商店で知能玩具が販売され、銅板に3本の棒があり、一番左の棒には上から下へ、64個の円盤からなる塔が小さい順に並んでいた.一番左のレバーの上のディスクをすべて右のレバーに移動することを目的とし、一度に1つのディスクしか移動できないことを条件とし、大皿を小皿の上に置くことは許されない.
今、ゲームの遊び方を変えて、一番左(右)から一番右(左)に直接移動することは許されません(移動するたびに必ず中間棒に移動したり、真ん中から移動したりします)、大皿を下盤の上に置くことも許されません.
Daisyはすでに元のハノータ問題とハノータIIをしたことがあるが、この問題に出会ったとき、彼女は長い間解決できないと思っていたので、今助けてください.今N個の円盤があって、彼女は少なくとも何回移動してこれらの円盤を一番左から一番右に移動することができますか?
Input
複数組のデータを含み、毎回1つのN値(1<=N=35)を入力する.
Output
データのセットごとに、移動の最小回数を出力します.
Sample Input
1
3
12
Sample Output
2
26
531440
式:Fn=3*F(n-1)+2、すなわちFn=3^n-1
コード:
#include<iostream>
using namespace std;
int main(void)
{
__int64 sum,n,i;
while(cin>>n)
{
sum=1;
for (i=1; i<=n; i++)
sum=sum*3;
cout<<sum-1<<endl;
}
return 0;
}