大斐波那契數

斐波那契數計算公式  :

f(n)=f(n-1)+f(n-2)        (n>=3)

f(1)=1

f(2)=1

對于 n 比較小的情況下，下邊的程式就可以實作這個功能

#include<cstdio>
#define ll long long 
const int n=100;
int main() 
{
  ll a[n];
  a[2]=1;a[1]=1;
  for(int i=3;i<n;i++)
    a[i]=a[i-1]+a[i-2];
  for(int i=1;i<n;i++)
    printf("%d   %lld\n",i,a[i]);
  return 0;
}      

結果如下：

請注意，當 n = 92的時候，結果還是正确的，但是 n 一旦超過92.long long 類型就無法儲存這麼大的數了

溢出了，是以我們需要尋找新的方法來計算 n 比較大的時候那些情況的斐波那契數

我們需要用到模拟的思想，開一個比較大的二維數組來儲存每一個斐波那契數，再讓它們的每一位相加最後得出的結果就是答案了，詳情請看代碼，

/*
  大斐波那契數 

*/
#include<cstdio>
#include<cstring>
#define ll long long
const int MAXN=1e4+3;
const int c=10000;
ll a[MAXN][MAXN];
int main()
{
  int n;
  while(~scanf("%d",&n))
  {
    a[1][0]=1;a[2][0]=1;//初始化 第一個數和第二個數 
    int dight=0;//斐波那契數的 位數 
    int temp=0;//儲存進位
    for(int i=3;i<=n;i++)  //從3算到N
    {
      temp=0;//進位每次計算都要初始化為0
      for(int j=0;j<=dight;j++)
      {
        a[i][j]=a[i-1][j]+a[i-2][j]+temp;
        temp=a[i][j]/10;
        a[i][j]%=10;
       } 
      if(temp)//如果有進位的話 
      {
        dight++;//位數加一 
        a[i][dight]=temp;//給最高位指派 
      }
     } 
    for(int i=dight;i>=0;i--)//逆序輸出這個數組 
      printf("%lld",a[n][i]);//n代表是第n個斐波那契數，i是這個數的第i位 
    printf("\n");      
  }
  return 0;
}      

應該可以把這個代碼優化一下，以便于計算更大的數

/*
  大斐波那契數 

*/

//這段代碼讓每一個a[i][j]的值都是9位 
#include<cstdio>
#include<cstring>
#define ll long long
const int MAXN=1e4+3;
const int c=1e9;
ll a[MAXN][MAXN];
int main()
{
  int n;
  while(~scanf("%d",&n))
  {
    a[1][0]=1;a[2][0]=1;
    int temp=0;
    int d=0;
    for(int i=3;i<=n;i++)
    {
      temp=0;
      for(int j=0;j<=d;j++)
      {
        a[i][j]=a[i-1][j]+a[i-2][j]+temp;
        temp=a[i][j]/c;
        a[i][j]%=c;
      }
      if(temp)
      {
        d++;
        a[i][d]=temp;
      }  
    }  
    printf("%lld",a[n][d]);
    for(int i=d-1;i>=0;i--)
      printf("%010lld",a[n][i]);
    printf("\n");
  }
  return 0;
}      

可以來這裡聯系一下：​​HDU_1715​​

AC代碼如下：

#include<cstdio>
#include<cstring>
const int MAXN=1004;
int a[MAXN][MAXN];
int main()
{
  int t,n;
  scanf("%d",&t);
  while(t--)
  {
    scanf("%d",&n);
    a[1][0]=1,a[2][0]=1;
    int d=0;
    int temp=0;
    for(int i=3;i<=n;i++)
    {
      temp=0;
      for(int j=0;j<=d;j++)
      {
        a[i][j]=a[i-1][j]+a[i-2][j]+temp;
        temp=a[i][j]/10;
        a[i][j]%=10;
      }
      if(temp)
      {
        d++;
        a[i][d]=temp;
      }
    }
    for(int i=d;i>=0;i--)
      printf("%d",a[n][i]);
    printf("\n");
  }
  return 0;
}      

大斐波那契數和大數階乘的思想是一樣的，不同的是大數階乘隻用了一維數組，比這個要簡單一些

import java.math.*;
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner cin = new Scanner(System.in);
    BigInteger[] a;
    a = new BigInteger[2000];
    a[0] = BigInteger.ZERO;
    a[1] = BigInteger.ONE;
    for(int i=2;i<1005;i++)
      a[i] = a[i-1].add(a[i-2]);
    int  n = cin.nextInt();
    while(n-->0){
      int i = cin.nextInt();
      System.out.println(a[i]);
    }
  }
}