2084.txt

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

#include"stdio.h"
#include"iostream.h"
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<memory.h>
#include<stdlib.h>
//ifstream in("game.in");
#define in cin
/////////////////////////////////////////////////////
void add(char *a,char *b,char * result);
void multiply(char *a,char *b,char * result)
{char c[10][1000];
 int i,j,p,k;
 if(a[0]=='-'&&b[0]!='-'){
	 printf("-");
	 multiply(a+1,b,result);
 }
 else if(a[0]!='-'&&b[0]=='-'){
	 printf("-");
	 multiply(a,b+1,result);
 }
 else if(a[0]=='-'&&b[0]=='-') multiply(a+1,b+1,result);
 else if(a[0]=='+'&&b[0]=='+') multiply(a+1,b+1,result);
 else if(a[0]!='+'&&b[0]=='+') multiply(a,b+1,result);
 else if(a[0]=='+'&&b[0]!='+') multiply(a+1,b,result);
 else{
	 strcpy(c[1],a);
	 for(i=2;i<10;i++)
		 add(c[i-1],a,c[i]);
	 result[0]='0';
	 result[1]='\0';
	 i=j=strlen(b)-1;
	 for(;j>=0;j--){
		 if(b[j]!='0'){
			 strcpy(c[0],c[b[j]-'0']);
			 p=strlen(c[0]);
			 for(k=0;k<i-j;k++)
				 c[0][p+k]='0';
			 c[0][p+k]='\0';
			 add(result,c[0],result);
		 }
	 }
 }
}
void minus(char *a,char *b,char * result)
{char c[1000];
 int i,j,k,temp=0;
 if(a[0]=='-'&&b[0]!='-'){
	 printf("-");
	 add(a+1,b,result);
 }
 else if(a[0]!='-'&&b[0]=='-') add(a,b+1,result);
 else if(a[0]=='-'&&b[0]=='-') 
	 minus(b+1,a+1,result);
 else if(a[0]=='+'&&b[0]=='+') minus(a+1,b+1,result);
 else if(a[0]=='+') minus(a+1,b,result);
 else if(b[0]=='+') minus(a,b+1,result);
 else if(strlen(a)<strlen(b)||(strlen(a)==strlen(b)&&strcmp(a,b)<0)){
	 printf("-");
	 minus(b,a,result);
 }
 else{
	 i=strlen(a)-1;
	 j=strlen(b)-1;
	 k=0;
	 while(j>=0){
		 if(a[i]-b[j]-temp>=0){
		     c[k]=a[i]-b[j]+'0'-temp;
		 temp=0;
		 }
		 else{
		     c[k]=10+a[i]-b[j]+'0'-temp;
			 temp=1;
		 }
		 k++;j--;i--;
	 }
	 while(temp!=0){
		 if(a[i]-temp-'0'>=0){
			 c[k]=a[i]-temp;
			 temp=0;
		 }
		 else{
			 c[k]=10+a[i]-temp;
			 temp=1;
		 }
		 k++;i--;
	 }
	 while(i>=0){
		 c[k]=a[i];
		 k++;i--;
	 }
	 k--;
	 while(k>=0&&c[k]=='0') k--;
	 if(k<0) {result[0]='0';result[1]='\0';}
	 else{
		 i=0;
		 while(k>=0){
		 result[i]=c[k];
		 k--;
		 i++;
		 }
	 result[i]='\0';
	 }
 }
}
void add(char *a,char *b,char * result)
{char c[1000],temp=0;
 int i,j,k;
 if(a[0]=='-'&&b[0]!='-') minus(b,a+1,result);
 else if(a[0]!='-'&&b[0]=='-') minus(a,b+1,result);
 else if(a[0]=='-'&&b[0]=='-') {
	 printf("-");
	 add(a+1,b+1,result);
 }
 else if(a[0]=='+'&&b[0]=='+') add(a+1,b+1,result);
 else if(a[0]=='+') add(a+1,b,result);
 else if(b[0]=='+') add(a,b+1,result);
 else {
	 i=strlen(a)-1;
	 j=strlen(b)-1;
	 k=0;
	 while(i>=0&&j>=0){
		 c[k]=a[i]+b[j]-'0'+temp;
		 temp=(c[k]-'0')/10;
		 c[k]=(c[k]-'0')%10+'0';
		 k++;j--;i--;
	 }
	 while(i>=0){
		 c[k]=a[i]+temp;
		 temp=(c[k]-'0')/10;
		 c[k]=(c[k]-'0')%10+'0';
		 i--;
		 k++;
	 }
	 while(j>=0){
	     c[k]=b[j]+temp;
		 temp=(c[k]-'0')/10;
		 c[k]=(c[k]-'0')%10+'0';
		 j--;
		 k++;
	 }
	 if(temp!=0)
		 c[k++]=temp+'0';
	 k--;
	 i=0;
	 while(k>=0){
		 result[i]=c[k];
		 k--;
		 i++;
	 }
	 result[i]='\0';
 }
}
////////////////////////////////////////////////////
char a[101][1000];
char result1[1000];
char result2[1000];
int main()
{
	int i,j,n;
	a[0][0]='1';
	a[0][1]='\0';
	
	for(i=1;i<=100;i++)
	{
		a[i][0]='0';
		a[i][1]=0;
		for(j=0;j<i;j++)
		{
			multiply(a[j],a[i-1-j],result1);
			add(result1,a[i],result2);

			strcpy(a[i],result2);
			
		}
	}
	while(1)
	{
		in>>n;
		if(n<0)break;
		
		printf("%s\n",a[n]);
	}
	return 0;
}