2680.txt

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

Problem Id:2680  User Id:fzk 
Memory:2124K  Time:46MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <memory.h>
#include <string.h>

class BigInteger
{
	public:
		enum { MAX = 1050 };
		int len;
		char cNum[MAX];
		int sign;

		BigInteger( int s = 0 )
		{
			len = 0;
			sign = ( s < 0 ) ? -1 : 1;
			s *= sign ;

			memset( cNum, 0, sizeof( cNum ) );
			while ( s != 0 )
			{
				cNum[ len ++ ] = s % 10;
				s /= 10;
			}
		
		}
		
		BigInteger( char* s )
		{
			
			sign = ( s[0] == '-' ) ? -1 : 1;
			
			if( s[0]=='+' || s[0]=='-' ) s++;
			len = strlen( s );
			
			memset( cNum, 0, sizeof( cNum ) );
			for (int i=0; i<len; i++)
			{
				cNum[i] = s[len-i-1] - '0';
			}
		}

		bool no_more_than( BigInteger& b )
		{
			int i;
			if ( len != b.len )
				return len < b.len;
			else for(i = len-1; i && cNum[i]==b.cNum[i] ; i--)
				;
			return cNum[i] <= b.cNum[i];
		}

		bool operator<( BigInteger& b )
		{
			if ( sign != b.sign )
				return sign < b.sign;
			else return ( sign==1 && !b.no_more_than(*this) ) || ( sign==-1 && !no_more_than(b) );
		}

		BigInteger& operator=( int s )
		{
			len = 0;
			sign = ( s < 0 ) ? -1 : 1;

			memset( cNum, 0, sizeof( cNum ) );
			
			while ( s != 0 )
			{
				cNum[ len ++ ] = s % 10;
				s /= 10;
			}
			return *this;		
		}
		
		BigInteger plus( BigInteger& b )
		{
			BigInteger c;
			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;
			c.sign = sign;
			return c;
		}
		
		BigInteger minus( BigInteger& b )
		{
			int i;
			BigInteger c;
		
			for(i=0; i<b.len ; i++)
			{
				c.cNum[i] += cNum[i] - b.cNum[i];
				if( c.cNum[i] < 0 )
				{
					c.cNum[i] += 10;
					c.cNum[i+1]--;
				}
			}
			for( ; i<len ; i++)
			{
				c.cNum[i] += cNum[i];
				if( c.cNum[i] < 0 )
				{
					c.cNum[i] += 10;
					c.cNum[i+1]--;
				}
			}
			c.len = len;
			while( c.len && c.cNum[c.len-1]==0 )
				c.len--;
			
			c.sign = sign;
			return c;
		}

		BigInteger operator+( BigInteger& b )
		{
			if ( sign == b.sign )
			{
				return plus ( b );
			}
			else if( no_more_than( b ) )
				return b.minus ( *this );
			else return minus ( b );
		}

		BigInteger operator-( BigInteger& b )
		{
			BigInteger c=b;
			c.sign=-b.sign;
			return operator+(c);
		}

		BigInteger operator*( BigInteger& t )
		{
			BigInteger s;
			int a;
			if( t.len==0 || len==0 )return 0;
			
			s.sign = sign * t.sign;
			
			for(int i=0 ; i<t.len ; i++)
			if( a = t.cNum[i] )
			{
				for(int j=0 ; j<len ; j++)
				{
					s.cNum[i+j] += a*cNum[j];
					if( s.cNum[i+j] >= 10 )
					{
						s.cNum[i+j+1] += s.cNum[i+j] / 10;
						s.cNum[i+j] %= 10;
					}
				}
			}

			for(s.len = len+t.len+2 ; s.cNum[s.len] == 0 ; s.len-- )
				;
			s.len++;
			return s;
		}
		
		int toOut(char *w)
		{
			int l=0;
			if( len && sign==-1 )
				w[l++] = '-';
			for (int i=len - 1; i>=0; i--)
			{
				w[l++] = cNum[i] + '0';
			}

			if( !len ) w[l++] = '0';
			w[l] = '\0';
			return l;
		}
};

BigInteger s[2][1001];
int l[2][1001];
int f[2][1001];
char w[1000];

int main( )
{
	int i, j;
	s[1][0] = BigInteger(0);
	s[0][0] = BigInteger(0);
	f[1][0] = l[1][0] = 1;
	f[0][0] = l[0][0] = 0;

	for( i=1; i<1001; i++ )
	{
		s[1][i] = s[0][i-1] + s[1][i-1] + BigInteger( (l[0][i-1]==f[1][i-1]&&l[0][i-1]==0)?1:0 );
		f[1][i] = f[0][i-1];
		l[1][i] = l[1][i-1];
		
		s[0][i] = s[1][i-1] + s[0][i-1] + BigInteger( (l[1][i-1]==f[0][i-1]&&l[1][i-1]==0)?1:0 );
		f[0][i] = f[1][i-1];
		l[0][i] = l[0][i-1];
	}

	while( scanf( "%d", &j ) == 1 )
	{
		s[1][j].toOut( w );
		printf( "%s\n", w );
	}

	return 0;
}