題目描述

斐波那契數(shù)列是指這樣的數(shù)列：數(shù)列的第一個和第二個數(shù)都為?11，接下來每個數(shù)都等于前面?22?個數(shù)之和。

給出一個正整數(shù)?aa，要求斐波那契數(shù)列中第?aa?個數(shù)是多少。

輸入格式

第?11?行是測試數(shù)據(jù)的組數(shù)?nn，后面跟著?nn?行輸入。每組測試數(shù)據(jù)占?11?行，包括一個正整數(shù)?aa（1≤a≤301≤a≤30）。

輸出格式

輸出有?nn?行，每行輸出對應(yīng)一個輸入。輸出應(yīng)是一個正整數(shù)，為斐波那契數(shù)列中第?aa?個數(shù)的大小。

輸入輸出樣例

輸入 #1復(fù)制

4
5
2
19
1

輸出 #1復(fù)制

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])