Tìm phần tử thứ N của dãy FIBONACCI

Em xin chào tất cả anh chị!
Chuyện là em đã cố gắng đọc tài liệu và dùng vector để xử lý bài này, nhưng ra kết quả không chính xác.
Mong các tiền bối lập trình giúp em những điều nên sửa để hoàn thiện bài này ạ.
Em xin chân thành cảm ơn!!
My code

#include <iostream>

using namespace std;
#include <vector>
typedef long long LL;
const long  mod =1e9+7;
LL FiboTab( int n){
    vector <LL> tab(n,0);
    if (n<=1) return n;
    tab[0]=0; tab[1]=1;
    for (int i=2;i<n;i++)
    {
        tab[i]=(tab[i-1] + tab[i-2]) % mod;
    }
    return tab[n];
}
int main(){
    int n;
    cin>> n;
    cout<< FiboTab(n);
    return 0;
}

Bạn khai báo 1 vector n phần tử, chỉ số từ 0 -> n-1, nhưng bạn lại gọi

thì làm sao mà được.

3 Likes

Dạ, em cảm ơn anh, anh nói chi tiết sửa ntn giúp em đc ko ạ.
Vì em đọc tài liệu của trường và nghĩ làm thế là đc.

Test case 45 trở đi không đúng, anh chị có thể giúp em chỉnh lại thuật toán với số lớn không ạ?

Bạn khai báo vector thành n+1 phần tử (chỉ số từ 0 -> n) là được.

3 Likes

Dạ, em khai báo kết quả kiểu long long.
Nhưng mà test case N=45 trở đi thì kq lại sai.
Còn các test case N<=44 có 9 chữ số là đúng.
Anh có thể giúp em gợi ý khắc phục được không ạ.
Em cảm ơn rất nhiều!

Bạn khai báo kiểu mod lên long long là được.

1 Like

Dạ không được kết quả đúng ạ
Chỉ ra được 9 chữ số thôi ạ
mà test này phải là 10 chữ số

Sửa dòng khai báo mod thành

const long long mod = 1000'000'007LL;

xem sao.

1 Like

Dạ cũng như thế anh ạ.
Bài này là test của trường em
có 10 test case mà em chỉ mới đúng 4 test
Em hơi thắc mắc là có thiếu trường hợp nào ko hay em xử lý chưa hết trường hợp ạ.

Bạn đăng link nộp bài lên đây được không?

dạ đây ạ
http://oj.husc.edu.vn/practice/problem/759/details

Bài này n <= 10^18 nên bạn không thể dùng vector để lưu dãy Fibonacci được. Bạn tìm hiểu cách tính số Fibonacci thứ n trong O(log n). Có 2 cách:

  1. Nhân ma trận.

  2. Dùng công thức truy hồi. Gợi ý: xét 2 trường hợp: n chẵn và n lẻ.

6 Likes

Dạ, cảm ơn anh chỉ hướng ạ.
Em sẽ học để giải quyết bài này ạ.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?