2413.cpp

各种算法

#include"iostream"
#include"math.h"
#include"string.h"
#include"stdio.h"
using namespace std;
#define M 105
#define N 482
int fib[N][M]  = {0};
int len[N] = {0};
int sub(int c[M],int d[M],int e[M],int n0)
{	int i;
	if(n0 == 0) return -1;
	for(i = 0;i < n0+2; i++){
		e[i] = c[i];
	}
	for(i = 0;i < n0; i++){
		if(e[i] < d[i]) e[i+1]--;
		e[i] = (e[i] + 10 - d[i]) %10;
	}
	if(e[n0] == -1 ) return -1;
	while(e[n0] == 0) n0--;
	return n0 + 1;
}
int cmp(int i,int c[M],int l)
{	int e[M] = {0};
	if(len[i] > l) return 1;
	else if(len[i] == l && sub(c,fib[i],e,l) < 0) 
			return 1;
	else	return 0;//小于and 等于
}
 int range(int c[M],int l)
 {	 if(l <= 0) return 0;
	 for(int i = 1;i < N-1;i++)
		if( cmp(i,c,l) <= 0 && cmp(i+1,c,l) > 0)
			return i;
	 return 0;
 }
 long input(int e[M])
 {	 char c[M];int i,j = 0;
	 scanf("%s",c); i = strlen(c);
	 while( j < i)
	 {	 j++;
		 e[j-1] = c[i-j] - '0';
	 }
	 e[i] = e[i+1] = 0;		//要给首位前附前导0，以便做加减法运算时利用进位借位，利用到前导0
	 if(j == 1 && e[0] == 0) { return 0;}
	 return i;
 }
 int plus(int a[M],int b[M],int d[M],int n0)
{	int i,c = 0;
	for (i = 0;i < n0; i++){
		d[i] = a[i] + b[i] + c;
		c = d[i]/10;
	    d[i] %= 10;
	}
   	if (c>0)   {d[n0] = c; n0++; }
	d[n0] = 0;
	return n0;
}
 void init()
 {	  int plus(int a[M],int b[M],int d[M],int n0);
	 fib[1][0] = 1;len[1] = 1;
     fib[2][0] = 2;len[2] = 1;
	 for(int i = 3;i < N; i++)
	 {	len[i] = plus(fib[i-2],fib[i-1],fib[i],len[i-1]);
	 }
 }
int main()
{	int e[M],f[M];int e1[M]={0};int l1,l2;int g[M] = {1,0};
	init();
	l1 = input(e);
	l2 = input(f);
	while(l1 != 0 || l2 !=0)
	{	l1 = sub(e,g,e1,l1);
		cout<<range(f,l2) - range(e1,l1)<<endl;
		l1  = input(e);l2 = input(f);
	};
	return 1;
}