Fbonacci模板

Fbonacci递归算法：(n最大为100以内)
============================================================

int fib(int n)
{
   if(n<=1)return 1;
   return fib(n-1)+fib(n-2);
}

============================================================
Fibonacci数学方法：(n最大为1473)
============================================================
F(n)=1/sqrt(5)*((pow((1+sqrt(5))/2,n+1)-(pow((1-sqrt(5))/2,n+1));


============================================================
Fbonacci前4位和后4位：
前4位测周期，后4位打表:
============================================================

#include <stdio.h>
#include <math.h>
#define aa (sqrt(5.0)+1.0)/2
int last[15000]={0,1,1,2,3,5};
int main()
{
    int i,n,Fibonacci[40]={0,1,1,2,3,5};
    double ans;
    /*测试周期    
    int T = 0;
    for (i=3;i<=120000;i++)
    {
        last[i] = (last[i-2]+last[i-1])%10000;
        if(last[i] == last[2]&&last[i-1] == last[1])
        {
            T = i;
            break;
        }
    }
    printf("%d\n",T-2);
    */
    /*后4位打表*/
    for (i=3;i<15000;i++)
        last[i] = (last[i-2]+last[i-1])%10000;
    for(i=6;i<40;i++)
        Fibonacci[i] = Fibonacci[i-1]+Fibonacci[i-2];
    while (scanf("%d",&n)!=EOF)
    {
        if(n<40)
            printf("%d\n",Fibonacci[n]);
        else
        {
            ans=-0.5*(log10(5.0))+n*log10(aa);
            ans-=(int)ans;
            ans=pow(10.0,ans);
            while(ans<1000)
                ans*=10;
            printf("%d...",(int)ans);
            printf("%4.4d\n",last[n%15000]);
        }
    }
    return 0;
}

============================================================
公式：sum(0-n)( com(n,k)*fibonacci(k) )= fibonacci(2*n);
再根据下面模板求得f(2n)即可。
============================================================
示例题目：A Problem With Fibonacci Sequence

Fibonacci sequence is well-known in the world. We define Fibonacci sequence as follows: F(0) = 0, F(1) = 1.
F(n) = F(n-1) + F(n-2). It’s easy for us to calculate F(n) mod m. But this time we want to make the problem
more difficult. We want to calculate the formula: sum(0-n)( com(n,k)*fibonacci(k) ) is the combination number.

Sample Input
2
1 30000
2 30000


Sample Output
1
3

============================================================
Fbonacci模板，求f(n) % m的值：
f(n) = p * f(n - 1) + q * f(n - 2);
============================================================

#include <iostream>
using namespace std;
int main()
{
	__int64 p , q , f[ 3 ] , n , m , y , yi;
	__int64 a[ 64 ][ 4 ], g[ 4 ] , h[ 4 ] , ans;
	int i , j , k , ff[ 64 ];
	while (scanf ("%I64d %I64d %I64d %I64d %I64d %I64d" , 
&p , &q , &f[ 1 ] , &f[ 2 ] , &n , &m) != EOF)
	{
		if (n < 3)
		{
			printf ("%I64d\n" , f[ n ] % m);
			continue;
		}
		a[ 0 ][ 0 ] = p % m;
		a[ 0 ][ 1 ] = q % m;
		a[ 0 ][ 2 ] = 1 % m;
		a[ 0 ][ 3 ] = 0 % m;
		y = n;yi = 0;
		while (y)
		{
			y /= 2 ;
			yi ++;
		}
		for (i = 1 ; i < yi ; ++ i)
		{
			a[ i ][ 0 ] = (a[i - 1][ 0 ] * a[i - 1][ 0 ] + a[i - 1][ 1 ] * a[i - 1][ 2 ]) % m;
			a[ i ][ 1 ] = (a[i - 1][ 0 ] * a[i - 1][ 1 ] + a[i - 1][ 1 ] * a[i - 1][ 3 ]) % m;
			a[ i ][ 2 ] = (a[i - 1][ 2 ] * a[i - 1][ 0 ] + a[i - 1][ 3 ] * a[i - 1][ 2 ]) % m;
			a[ i ][ 3 ] = (a[i - 1][ 2 ] * a[i - 1][ 1 ] + a[i - 1][ 3 ] * a[i - 1][ 3 ]) % m;
		}
		memset (ff , 0 , sizeof (ff));
		n = n - 2;
		k = 0;
		while (n)
		{
			ff[ k ] = n % 2;
			n = n / 2;
			k ++;
		}
		g[ 0 ] = g[ 3 ] = 1;
		g[ 1 ] = g[ 2 ] = 0;
		for (i = 0 ; i < k ; ++ i)
		{
			if (ff[ i ])
			{
				h[ 0 ] = (g[ 0 ] * a[ i ][ 0 ] + g[ 1 ] * a[ i ][ 2 ]) % m;
				h[ 1 ] = (g[ 0 ] * a[ i ][ 1 ] + g[ 1 ] * a[ i ][ 3 ]) % m;
				h[ 2 ] = (g[ 2 ] * a[ i ][ 0 ] + g[ 3 ] * a[ i ][ 2 ]) % m;
				h[ 3 ] = (g[ 2 ] * a[ i ][ 1 ] + g[ 3 ] * a[ i ][ 3 ]) % m;
				for (j = 0 ; j < 4 ; ++ j)
					g[ j ] = h[ j ];
			}
		}
		ans  = (g[ 0 ] * f[ 2 ] + g[ 1 ] * f[ 1 ]) % m;
		printf ("%I64d\n" , ans);
	}
	return 0;
}

============================================================
大斐波数
求的是F(n)的1000位内的大斐波数，可扩展（自己修改）
============================================================

#include <iostream>
#include <iomanip>
using namespace std;
#define MAX 10000000
#define SIZE 100
class BigNum
{
public:    
    int a[SIZE];
    BigNum()
    {
        for(int i=0;i<SIZE;i++)
            a[i]=0;
    }
    BigNum  operator+(BigNum & b);
    void  operator=(BigNum & b);
    void f();
    void display();
};
BigNum  BigNum::operator+(BigNum & b)
{
    BigNum p;
    for(int i=0;i<SIZE;i++)
    {
        p.a[i]=a[i]+b.a[i];
    }
    return p;
}
void  BigNum::operator=(BigNum & b)
{
    for(int i=0;i<SIZE;i++)
    {
        a[i]=b.a[i];
    }
}
void BigNum::f()
{
    for(int i=0;i<SIZE;i++)
    {
        if(a[i]>MAX)
        {
            a[i+1]+=a[i]/MAX;
            a[i]%=MAX;
        }
    }
}
void BigNum::display()
{
    for(int i=SIZE-1;i>=0;i--)
    {
        if(a[i]!=0)
        {
            cout<<a[i];
            while(i--)
            {
                cout << setw(7) << setfill('0') << a[i];
            }
            break;
        }
    }
    cout<<endl;        
}
int main()
{
    BigNum num[1001];
    num[1].a[0]=1;
    num[2].a[0]=1;
    for(int i=3;i<=1000;i++)
    {
        num[i]=num[i-1]+num[i-2];
        num[i].f();
    }
    int n,m;
    cin>>n;
    
        while(n--)
        {
            cin >> m;
            num[m].display();
        }
    
    return 0;
}