题目描述

输入整数 N，求出斐波那契数列中的第 N 项是多少。

斐波那契数列的第 0 项是 0，第 1 项是 1，从第 2 项开始的每一项都等于前两项之和。

输入格式
第一行包含整数 T，表示共有 T 个测试数据。

接下来 T 行，每行包含一个整数 N。

输出格式
每个测试数据输出一个结果，每个结果占一行，

结果格式为 Fib(N) = x，其中 N 为项数，x 为第 N 项的值。

数据范围
0≤N≤60

样例

输入样例：

3
0
4
2

输出样例：

Fib(0) = 0
Fib(4) = 3
Fib(2) = 1

咱们第一个思路就是存两个数组：一个存项数，一个存值

C++ 代码

#include<iostream>

using namespace std;

const int N = 65;
int n;
int a[N];//a数组用来存项数
int e[N];//e数组用来存对应项数的值

int main(){

    //接收输入
    scanf("%d", &n);
    for(int i = 0;i < n;i++){
        scanf("%d", &a[i]);
    }

    //枚举数值，后面会一一对应
    e[0] = 0;e[1] = 1;
    for(int i = 2;i < 65;i ++){
        e[i] = e[i - 1] + e[i - 2];
    }

    //输出
    for(int i = 0;i < n;i++){
        cout << "Fib(" << a[i] << ") = " << e[a[i]] << endl;
    }

    return 0;
}

好的，这个代码很明显，最多一重循环，故时间复杂度是O（n）

可你以为这样就完了？！

你会发现输出是这样的：

输入
10
40
24
46
44
39
59
44
14
34
9

输出

Fib(40) = 102334155
Fib(24) = 46368
Fib(46) = 1836311903
Fib(44) = 701408733
Fib(39) = 63245986
Fib(59) = -1055680967(请注意)
Fib(44) = 701408733
Fib(14) = 377
Fib(34) = 5702887
Fib(9) = 34

标准答案

Fib(40) = 102334155
Fib(24) = 46368
Fib(46) = 1836311903
Fib(44) = 701408733
Fib(39) = 63245986
Fib(59) = 956722026041(请注意)
Fib(44) = 701408733
Fib(14) = 377
Fib(34) = 5702887
Fib(9) = 34

我们这才意识到，哦，数值好像溢出了

所以——AC代码如下不再卖关子了：

#include<iostream>

using namespace std;

const int N = 65;
int n;
int a[N];//a数组用来存项数
long long int e[N];//e数组用来存对应项数的值

int main(){

    //接收输入
    scanf("%lld", &n);
    for(int i = 0;i < n;i++){
        scanf("%d", &a[i]);
    }

    //枚举数值，后面会一一对应
    e[0] = 0;e[1] = 1;
    for(int i = 2;i < 65;i ++){
        e[i] = e[i - 1] + e[i - 2];
    }

    //输出
    for(int i = 0;i < n;i++){
        cout << "Fib(" << a[i] << ") = " << e[a[i]] << endl;
    }

    return 0;
}