1316 how many fibs.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

//how many fibs
#include <cstdio>
#include <string>
#include <iomanip>
#include <algorithm>
using namespace std;

#define MAXN 9999
#define DLEN 4
bool flag;

class BigNum{
private:
   int a[50];//DLEN digs for a position
   int len;
public:
   BigNum(){len = 1;memset(a,0,sizeof(a));}
   BigNum(const int b);
   BigNum(const char* b);
   BigNum(const BigNum & T);

   bool     Bigger(const BigNum &) const;
   BigNum & operator=(const BigNum &);
   BigNum & Add(const BigNum &);
   BigNum operator+(const BigNum &) const;
   
   bool operator==(const BigNum &) const;
   bool operator>(const BigNum &) const;
   bool operator<(const BigNum &) const;
   
} fib[510],num1,num2;;

BigNum::BigNum(const int b)
{
   int c,d = b;

   len = 0;
   memset(a,0,sizeof(a));
   while(d > MAXN){
      c = d - d / (MAXN + 1) * (MAXN + 1);
      d = d / (MAXN + 1);
      a[len++] = c;
   }
   a[len++] = d;
}
BigNum::BigNum(const BigNum & T) : len(T.len)
{
   int i;
   memset(a,0,sizeof(a));
   for(i = 0 ; i < len ; i++)
      a[i] = T.a[i];
}
bool  BigNum::Bigger(const BigNum & T) const
{
   int ln;
   if(len > T.len) return true;
   else if(len == T.len){
      ln = len - 1;
      while(a[ln] == T.a[ln] && ln >= 0) ln--;
      if(ln >= 0 && a[ln] > T.a[ln]) return true;
      else return false;
   }
   else return false;
}
bool  BigNum::operator==(const BigNum & T) const
{
	int i;
	if(len!=T.len)
		return false;
	for(i=0;i<len;i++)
		if(a[i]!=T.a[i])
			return false;
	return true;
}
bool  BigNum::operator>(const BigNum & T) const
{
	return Bigger(T);
}
bool  BigNum::operator<(const BigNum & T) const
{
	if(*this == T)
		return false;
	else
		return ! Bigger(T);
}
BigNum & BigNum::operator=(const BigNum & n)
{
   len = n.len;
   memset(a,0,sizeof(a));
   for(int i = 0 ; i < len ; i++)
      a[i] = n.a[i];
   return *this;
}
BigNum & BigNum::Add(const BigNum & T)
{
   int i,big;

   big = T.len > len ? T.len : len;
   for(i = 0 ; i < big ; i++)
   {
      a[i] = a[i] + T.a[i];
      if(a[i] > MAXN)
      {
         a[i + 1]++;
         a[i] = a[i] - MAXN - 1;
      }
   }
   if(a[big] != 0) len = big + 1;
   else len = big;
	
	//if(len==25 && a[len-1]>=1000)
		//flag=false;
		
   return *this;
}
BigNum BigNum::operator+(const BigNum & n) const
{
   BigNum a = *this;

   a.Add(n);
   return a;
}

//////////////////////////////
BigNum::BigNum(const char* b)
{
   int temp=0,numlen=1,s;
   int ca=0;

   len = 0;
   memset(a,0,sizeof(a));
   if(b[0]=='0' && b[1]==0)
   {
		len=1;
		return;
   }
   s=0;
   while(b[s]=='0')
   		s++;
   while(b[ca++] != '\0');
   ca--;
   while(--ca >= s)
   {
        temp += numlen * (b[ca]-'0');
        numlen*=10;
        if( numlen==(MAXN + 1) )
        {
            a[len++]=temp;
            numlen=1;
            temp=0;
        }
   }
   if(temp!=0)
   {
        a[len++]=temp;
   }
}

int construct()
{
	int i;
	fib[0]=1;fib[1]=1;fib[2]=2;
	flag=true;
	for(i=3; i<500 ;i++)
		fib[i]=fib[i-1]+fib[i-2];
	return i-1;
}

int main()
{
	int i,j,sizes,len;
	char sa[110],sb[110];
	sizes=construct();
	while( scanf("%s %s",sa,sb)!=EOF )
	{
		num1=sa;
		num2=sb;
		if(num1==0 && num2==0)
			break;
		len=0;
		for(i=1; fib[i]<num2 || fib[i]==num2 ;i++)
     		if(fib[i]>num1 || fib[i]==num1)
     			len++;
		printf("%d\n", len );
	}
	return 0;
}