B2064 斐波那契数列

题目描述

斐波那契数列是指这样的数列：数列的第一个和第二个数都为 11，接下来每个数都等于前面 22 个数之和。

给出一个正整数 aa，要求斐波那契数列中第 aa 个数是多少。

输入格式

第 11 行是测试数据的组数 nn，后面跟着 nn 行输入。每组测试数据占 11 行，包括一个正整数 aa（1≤a≤301≤a≤30）。

输出格式

输出有 nn 行，每行输出对应一个输入。输出应是一个正整数，为斐波那契数列中第 aa 个数的大小。

输入输出样例

输入 #1复制

4
5
2
19
1

输出 #1复制

5
1
4181
1

代码：

C++：

#include<iostream>
using namespace std;
const int N = 999999;
long long dp[N];
int main() {int n;cin >> n;dp[1] = 1;dp[2] = 1;for (int i = 0; i < n; i++) {int num;cin >> num;if (num <= 1) {cout << 1 << endl;continue;}if (num <= 2 && num > 1) {cout << 1 << endl;continue;}for (int i = 3; i <= num; i++) {dp[i] = dp[i - 1] + dp[i - 2];}cout << dp[num] << endl;}return 0;
}

JAVA：

import java.util.*;public class Main{public static void main(String[] args) {int dp[] = new int[999999];int n;Scanner gudu = new Scanner(System.in);dp[1] = 1;dp[2] = 1;n = gudu.nextInt();for (int i = 0; i < n; i++) {int num;Scanner gudu1 = new Scanner(System.in);num = gudu1.nextInt();if (num == 1 || num == 2) {System.out.println(dp[1]);}else {for (int j = 3; j <= num; j++) {dp[j] = dp[j - 1] + dp[j - 2];}System.out.println(dp[num]);}}}
}

Python:

n = int(input())
m = 999999
dp = [0] * m
dp[1] = 1
dp[2] = 1
for i in range(n):num = int(input())if n == 1 or n == 2:print(1)else:for j in range(3, num + 1):dp[j] = dp[j - 1] + dp[j - 2]print(dp[num])