2285305_ac_46ms_48k.c

北大大牛代码 1240道题的原代码 超级权威

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

char cat[101][70];

void res(char a[])
{
	char ch;
	int i, l;

	l = strlen(a);
	for(i = 0; i < l/2; i++)
	{
		ch = a[i];
		a[i] = a[l-i-1];
		a[l-i-1] =ch;
	}
}

void add(char a[],char b[])
{
	int i, l, w, t;
	int l1, l2;

	l1 = strlen(a);
	l2 = strlen(b);
	l = l1>l2?l1:l2;
	w = 0;
	for(i = 0; i < l; i++)
	{
		if(i>=l1)
			a[i] = '0';
		if(i>=l2)
			b[i] = '0';
		t = a[i]+b[i]-'0'-'0'+w;
		if(t>=10)
			t%=10,w=1;
		else
			w = 0;
		a[i] = t + '0';
	}
	if(w)
		a[i++] = '1';
	a[i] = '\0';
}

void muti(char a[],char b[])
{
	int i, p, w, j;
	int l1, l2, tmp;
	char ans[70];

	res(a);
	res(b);
	l1 = strlen(a);
	l2 = strlen(b);
	p = 1;
	for(i = 0; i < 70; i++)
		ans[i] = '0';
	for(i = 0; i < l2; i++)
	{
		w = 0;
		for(j = 0; j < l1; j++)
		{
			tmp = (a[j]-'0')*(b[i]-'0')+w;
			tmp += ans[j+i]-'0';
			ans[j+i] = tmp%10+'0';
			w = tmp/10;
		}
		if(w)
			ans[j+i] = '0'+w;
	}
	if(w)
		p = 0;
	ans[j+i-p] = '\0';
	strcpy(a,ans);
}

void cal(char *tmp,int n)
{
	int i;
	char Tmp[70], Tmp1[70];

	memset(tmp,0,sizeof(tmp));
	for(i = 0; i < n; i++)
	{
		strcpy(Tmp,cat[i]);
		strcpy(Tmp1,cat[n-i-1]);
		muti(Tmp,Tmp1);
		add(tmp,Tmp);
	}
}

void init()
{
	int n;
	char tmp[70];

	strcpy(cat[0],"1");
	strcpy(cat[1],"1");
	strcpy(cat[2],"2");
	for(n = 3; n <= 100; n++)
	{
		cal(tmp,n);
		res(tmp);
		strcpy(cat[n],tmp);
	}
}

int main()
{
	int n;

	init();
	while(scanf("%d",&n)&&(n+1))
		puts(cat[n]);
	return 1;
}