2506.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <stdio.h>
#include <memory.h>
#include <string.h>
#define MAX 550
class BigInteger
{
	public:
		int len;
		char cNum[MAX];
		BigInteger( int s = 0 )
		{
			len = 0;
			memset( cNum, 0, sizeof( cNum ) );
			while ( s != 0 )
			{
				cNum[ len ++ ] = s % 10;
				s /= 10;
			}	
		}		
		BigInteger( char* s )
		{
			len = strlen( s );
			memset( cNum, 0, sizeof( cNum ) );
			for (int i=0; i<len; i++)
			{
				cNum[i] = s[len-i-1] - '0';
			}
		}		
		BigInteger& operator=( int s )
		{
			len = 0;
			memset( cNum, 0, sizeof( cNum ) );
			while ( s != 0 )
			{
				cNum[ len ++ ] = s % 10;
				s /= 10;
			}
			return *this;		
		}
		BigInteger operator+(const BigInteger& b )
		{
			BigInteger temp,* c = &temp;
			int mmax = ( len > b.len ) ? len : b.len;
			int up = 0;
			int i = 0;
			for (i=0; i<mmax; i++)
			{
				c->cNum[i] = cNum[i] + b.cNum[i] + up;
				up = c->cNum[i] / 10;
				c->cNum[i] %= 10;
			}
			if ( up != 0 )
			{
				c->cNum[mmax] = up;
				mmax ++;
			}
			c->len = mmax;
			return *c;
		}		
		BigInteger operator*(const BigInteger& b )
		{
			BigInteger temp,* c = &temp;;
			int mmax = 0;
			int p = 0;
			int up = 0;
			for (int i=0; i<len; i++)
			{
				p = i;
				for (int j=0; j<b.len; j++)
				{
					c->cNum[p] += cNum[i] * b.cNum[j] + up;
					up = c->cNum[p] / 10;
					c->cNum[p] %= 10;
					p ++;
				}
				while ( up != 0 )
				{
					c->cNum[p] += up % 10;
					up /= 10;
					up += c->cNum[p] / 10;
					c->cNum[p] %= 10;
					p ++;
				}
				if ( p > mmax )
					mmax = p;
			}
			for (int k=mmax-1; k>0; k--)
			{
				if ( c->cNum[k] == 0 )
					mmax --;
				else
					break;
			}
			c->len = mmax;
			return *c;
		}		
		void output( char c = '\0' )
		{
			if ( len == 0 ) putchar('0');
			for (int i=len - 1; i>=0; i--)
			{
				putchar( cNum[i] + '0' );
			}
			putchar( c );
		}
};
BigInteger f[251];
int main()
{
	int i, j;
	f[0] = BigInteger(1);
	f[1] = BigInteger(1);
	for( i=2; i<=250; i++ )
		f[i] = f[i-1] + f[i-2] + f[i-2];
	while( scanf( "%d", &j ) == 1 )
	{
		f[j].output( '\n' );
	}

	return 0;
}