JOJ-2033-Towers of Hanoi

类别:软件工程 点击:0 评论:0 推荐:

Tomorrow is Kate's birthday,  Kate is a lovely girl aged 20. This Contest  is held for her birthday and I want everyone will be happy today. My name is sea .I'm not so good at English and Programming. But when I know that it is possible to have a personal contest on JOJ. I want to have a try. Just for her.

Kate : Wish you beauty and healthy forever happy birthday!

Do you know the game "Towers of Hanoi"?  It is a very famous game. But people stopped moving discs from peg to peg after they know the number of steps needed to complete the entire task !  Kate loves the game. She want to know how many times she has to  move the disks at least to complete the game?

As we all know , for n disks the game takes 2^n-1 moves at least. But kate want to know the exact numble. Sea want to tell her ,but he is poor at math. So he want to write a program to help her.

Input SpecificationEach line contains a numbe 'N' (0 <= N <= 500). N stand for the number of the disks. Output SpecificationJust output the least time that kate has to move the disks to complete the game. one per line. Sample Input

7 10 Sample Output

127 1023


#include<iostream> using namespace std; const int MAX=501; const int D=1000000000; const int width=9; void main() { int fact[MAX][17]={0};//151/9==16.777 int len[MAX]={0}; fact[0][0]=1; len[0]=1; for(int i=1;i<MAX;++i) { int c=0; int idx=0; for(idx=0;idx<len[i-1];++idx) { int t=fact[i-1][idx]*2+c; fact[i][idx]=t%D; c=t/D; } if(c>0) { len[i]=len[i-1]+1; fact[i][idx]=c; } else len[i]=len[i-1]; } int n; while(cin>>n) { if(len[n]==1) { cout<<fact[n][len[n]-1]-1<<endl; continue; } cout<<fact[n][len[n]-1]; for(int i=len[n]-2;i>0;--i) { cout.width(width); cout.fill('0'); cout<<fact[n][i]; } cout.width(width); cout.fill('0'); cout<<fact[n][0]-1; cout<<endl; } }

 
 

说简单点就是用数组计算2的乘幂 两点教训:第一,要计算2^0。在这道题里可能很自然考虑到,然而在一道计算N!的程
序可难住了我,郁闷了好久。实际上这个程序就是用计算N!的程序改。第二,不要以为加法比乘法快。开始我是用加法,
用时0.01秒,而用乘法是0.00秒,做移位运算毕竟要比加法快多了。

本文地址:http://com.8s8s.com/it/it33150.htm