题目地址:http://xcacm.hfut.edu.cn/problem.php?id=1216

题目描述

Fibonacci数列,定义如下:

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

计算第n项Fibonacci数值。

思路

大数处理,这里测试了一下Java和C++。C++速度真给力啊。
http://7xibui.com1.z0.glb.clouddn.com/2015/05/3.jpg

AC代码(C++)

/*************************************************************************
    > File Name: 1715.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: Thu 28 May 2015 08:35:15 AM CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>

#define Len 100000000
#define L "%08d"
using namespace std;

int f[10005][1000]; // f[n][0...1000]分别依次存放较低位每8位。
void sum(int n) {
    int k=0;
    for(int i=0; i<1000; ++i) {
        k += f[n-1][i] + f[n-2][i];
        if(k==0) // 这里有Bug,对于这题暂时无视。。
            break;
        f[n][i] = k%Len;
        k/=Len;
    }
}
int main()
{
#ifdef Oj
     // freopen("1715.in", "r", stdin);
     // freopen("1715.out", "w", stdout);
#endif
    memset(f, 0, sizeof(f));
    f[1][0] = 1;
    f[2][0] = 1;
    for(int n=3; n<=10000; ++n)
        sum(n); // 求数列第n项
    int n;
    while(cin >> n) {
        int j;
        for(j=999; j>=0; --j)
            if(f[n][j] != 0)
                break;
        printf("%d", f[n][j--]);
        for(;j>=0; --j)
            printf(L, f[n][j]);
        puts("");
    }
    return 0;
}

AC代码(Java)

/*************************************************************************
    > File Name: fibonacci.java
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: Sat 30 May 2015 07:11:36 PM CST
 ************************************************************************/

import java.io.*;
import java.math.*;
import java.util.*;
import java.text.*;

public class fibonacci {
    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        BigInteger f[] = new BigInteger[10005];
        f[1] = BigInteger.valueOf(1);
        f[2] = BigInteger.valueOf(1);
        for (int n = 3; n <= 10000; n++) {
            f[n] = f[n-1];
            f[n] = f[n].add(f[n-2]);  // 求数列第n项
        }
        int n;
        while(cin.hasNextInt()) {
            n=cin.nextInt();
            System.out.println(f[n]);
        }
    }
}