2663664_ac_31ms_184k.c

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

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

char a[111], b[111];
char fib[1000][111];
int n;

void add()
{
	int a, b, t, w;
	int i, len1, len2, max;
	char t1[111], t2[111], ans[111];

	len1 = strlen(fib[n-1]);
	for (i = 0; i < len1; i++)
		t1[len1-i-1] = fib[n-1][i];
	t1[len1] = '\0';
	len2 = strlen(fib[n-2]);
	for (i = 0; i < len2; i++)
		t2[len2-i-1] = fib[n-2][i];
	t2[len2] = '\0';
	max = len2>len1?len2:len1;
	w = 0;
	for (i = 0; i < max; i++)
	{
		a = t1[i]-'0';
		b = t2[i]-'0';
		if(i>=len1)	a = 0;
		if(i>=len2) b = 0;
		t = a+b+w;
		if(t>9)
			t -= 10, w = 1;
		else
			w = 0;
		ans[i] = t+'0';
	}
	if(w)
		ans[i++] = '1';
	ans[i] = '\0';
	max = strlen(ans);
	for(i = 0; i < max; i++)
		fib[n][i] = ans[max-i-1];
	fib[n][max] = '\0';
}

void init()
{
	strcpy(fib[1],"1");
	strcpy(fib[2],"2");
	for (n = 3; ; n++)
	{
		add();
	//	puts(fib[n]);
		if (strlen(fib[n])>=101)
		{
			break;
		}
	}
	//printf("%d\n",n);
}

int biggerb(int i)
{
	if(strlen(fib[i])>strlen(b))
		return 1;
	if(strlen(fib[i])==strlen(b)&&strcmp(fib[i],b)>0)
		return 1;
	return 0;
}

int biggera(int i)
{
	if(strlen(fib[i])>strlen(a))
		return 1;
	if(strlen(fib[i])==strlen(a)&&strcmp(fib[i],a)>=0)
		return 1;
	return 0;
}

int main()
{
	int i, j;

	//freopen("fibs.in","r",stdin);
	//freopen("out","w",stdout);
	init();
	while (scanf("%s%s",a,b)==2)
	{
		if (strcmp(a,"0")==0&&strcmp(b,"0")==0)
			break;
		for (i = 1; ; i++)
			if(biggera(i))
				break;
		for (j = 1; ;j++)
			if(biggerb(j))
				break;
		printf("%d\n",j-i);
	}
	return 0;
}