HDU 1715 大菲波数

大菲波数

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 16771    Accepted Submission(s): 5537

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

 

Source

2007省赛集训队练习赛（2）

 

 

 

解析：大数。可以查到，斐波那契数列第1000个数的位数为209。

 

 

 

#include <cstdio>
#include <cstring>

int fib[1005][215];

void init()
{
    memset(fib,0,sizeof(fib));
    fib[1][1] = 1;
    fib[2][1] = 1;
    int tmp;
    int carry = 0;  //进位
    for(int i = 3; i <= 1000; ++i){
        for(int j = 1; j <= 209; ++j){
            tmp = fib[i-1][j]+fib[i-2][j]+carry;
            fib[i][j] = tmp%10;
            carry = tmp/10;
        }
    }
}

int main()
{
    init();
    int t,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        int i;
        for(i = 215; i>0 && fib[n][i] == 0; --i)
            ;
        for(; i>0; --i){
            printf("%d",fib[n][i]);
        }
        printf("
");
    }
    return 0;
}

另外，JAVA中有功能强大的大数类可供我们直接调用。

 

 

 

import java.util.Scanner;
import java.math.BigInteger;

class Main{
    public static void main(String[] args) {
        BigInteger[] bi = new BigInteger[1001];
        bi[1] = new BigInteger("1");
        bi[2] = new BigInteger("1");;
        for(int i=  3; i <= 1000; ++i){
            bi[i] = bi[i-1].add(bi[i-2]);
        }
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        int n;
        for(int i = 0; i<t; ++i){
            n = in.nextInt();
            System.out.println(bi[n]);
        }
    }
}