FIBO1 - Tìm số Fibonacci thứ N

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Tác giả:
Hieu Nguyen
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Dãy số Fibonacci được định nghĩa  $$\left\{ \begin{array}{l}{F_0} = {F_1} = 1\\{F_n} = {F_{n - 1}} + {F_{n - 2}},\forall n \ge 2\end{array} \right.$$

Yêu cầu:

Cho số nguyên không âm ~n~, hãy tính ~F_n~

Input

  • Dòng đầu chứa số nguyên ~T~ là số bộ test.
  • Dòng sau chứa ~T~ số nguyên không âm, hai số liên tiếp cách nhau một dấu cách.

Giới hạn:

  • ~0 ≤ n ≤ 10000; 1 ≤ T ≤ 100~.

Output

  • Gồm ~T~ dòng là, mỗi dòng là kết quả của test đầu vào tương ứng.

Sample

Input #1
3
0 1 2
Output #1
1
1
2
Input #2
2
5 3
Output #2
8
3

Problem source: Chuyên Sơn La Online Judge

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • -3
    thh  đã bình luận lúc 4, Tháng 2, 2024, 5:10

    pragma GCC optimize("O3","unroll-loops")

    pragma GCC target("avx2")

    include <bits/stdc++.h>

    using namespace std; const int base = 1000000000; const int base_digits = 9;

    void solve() {

    int n;
cin >> n;
bigint a[10001];
a[0] = {{1}};
a[1] = a[0];
for(int i = 2;i <= 10000; i += 1)
    a[i] = a[i - 1] + a[i - 2];
while(n--)
{
    int num;
    cin >> num;
    cout << a[num] << '\n';
}

    } int main() {

    ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);

solve();
return 0;

    } Code C++ nè ai thấy hay cho mik xin upvote nha :)


    • -3
      thh  đã bình luận lúc 4, Tháng 2, 2024, 5:15

      Đây là code phần bigint

      https://www.ideone.com/h3dNXg


  • 1
    ______  đã bình luận lúc 28, Tháng 1, 2024, 8:31

    include <iostream>

    include <iomanip>

    include <vector>

    using namespace std;

    void fibonacci(int n) { vector<int> a = {1}; vector<int> b = {1};

    for (int i = 2; i <= n; ++i) {
    int carry = 0;

    for (size_t j = 0; j < max(a.size(), b.size()) || carry; ++j) {
        if (j == b.size()) {
            b.push_back(0);
        }

        long long sum = carry + (j < a.size() ? a[j] : 0) + (j < b.size() ? b[j] : 0);
        b[j] = sum % 1000000000;
        carry = sum / 1000000000;
    }

    while (b.size() > 1 && b.back() == 0) {
        b.pop_back();
    }

    a.swap(b);
}
for (auto it = a.rbegin(); it != a.rend(); ++it) {
    if (it == a.rbegin()) {
        cout << *it;
    } else {

        cout << setw(9) << setfill('0') << *it;
    }
}
cout << endl;

    }

    int main() { int T; cin >> T;

    for (int t = 0; t < T; ++t) {
    int n;
    cin >> n;

    fibonacci(n);
}

return 0;

    } full ac nha xin upvote


  • -2
    huy132004  đã bình luận lúc 23, Tháng 10, 2023, 15:59

    Java phải dùng tới BigInteger mới được.


  • -1
    hnguyen  đã bình luận lúc 8, Tháng 10, 2023, 9:13

    xử lí số nguyên lớn


  • -1
    lch101  đã bình luận lúc 29, Tháng 8, 2023, 8:46

    hơi thắc mắc chút là n = 92 93 là đã vượt giới hạn long long r thì làm như nào nhỉ ?


  • -5
    P_love_N  đã bình luận lúc 13, Tháng 7, 2023, 13:59

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.