大菲波数（大数多次相加）

约定不等于承诺〃 2022-07-31 17:24 14阅读 0赞

# 大菲波数 #

**Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 13712    Accepted Submission(s): 4665**

Problem Description

Fibonacci数列，定义如下：  
f(1)=f(2)=1  
f(n)=f(n-1)+f(n-2) n>=3。  
计算第n项Fibonacci数值。

Input

输入第一行为一个整数N，接下来N行为整数Pi（1<=Pi<=1000）。

Output

输出为N行，每行为对应的f(Pi)。

Sample Input

5
    1
    2
    3
    4
    5

Sample Output

1
    1
    2
    3
    5

**一看大数就想到用java,但是却超内存了，一开始我以为是开的**

**数组太大，想每次获得一个m时开一个数组，估计m很大，也超**

**了**

**被逼无奈选择用数组存**

**二维数组存数用的很舒服，第一次用！**

**但是二维数组有缺陷就是数组不能开大，还好这道题目数据位数**

**不是很大，否则就真的要死翘翘了（用char数组存）**

**发一下java代码**

import java.math.BigInteger;
    import java.util.Scanner;
    public class Main {
    	public static void main(String[] args)
    	{
    		int i,j;
    		Scanner cin=new Scanner(System.in);
    		int n=cin.nextInt();
    		while (n-->0) {
    			j=cin.nextInt();
    			BigInteger[]p=new BigInteger[j+1];
    			p[0]=BigInteger.valueOf(1);
    			p[1]=BigInteger.valueOf(1);
    			p[2]=BigInteger.valueOf(1);
    			for(i=3;i<=j;i++)
    			{
    				p[i]=p[i-2].add(p[i-1]);
    			}
    			System.out.println(p[j]);
    		}
    	}
    }

发一下AC代码

#include<cstdio>
    #include<iostream>
    #include<vector>
    using namespace std;
    int a[1005][220];
    void chushihua()
    {
        int i,ans=0,j,tmp;
        a[1][0]=1;
        a[2][0]=1;
        for(i=3;i<=1000;i++)
        {
            ans=0;
            for(j=0;j<215;j++)
            {
                a[i][j]=a[i-1][j]+a[i-2][j];
            }
            for(j=0;j<215;j++)
            {
                tmp=a[i][j]+ans;
                ans=tmp/10;
                a[i][j]=tmp%10;
            }
        }
    }
    int main()
    {
        int n,m,i,j;
        chushihua();
        cin>>n;
            while(n--)
           {
             cin>>m;
             for(i=215;;)
             {
                 if(a[m][i]==0)
                 {
                     i--;
                 }
                else
                {
                    break;
                }
            }
            for(j=i;j>=0;j--)
            {
                printf("%d",a[m][j]);
            }
            printf("\n");
       }
    }