Solutions of Fibonacci - MarisaOJ: Marisa Online Judge

Solutions of Fibonacci

Select solution language

Write solution here.


User Avatar hvnamyd    Created at    0 likes

Dãy số Fibonacci được xây dựng như sau : f[1] = 1 f[2] = 1 f[i] = f[i-1] + f[i-2] Đề bài bắt ta tìm số Fibonacci thứ n Để làm bài này, ta có thể dùng hàm đệ quy nhưng lại gặp vấn đề thời gian vì n <= 80 Chúng ta có thể làm bằng cách quy hoạch động như sau : B1 : nhập n B2 : gán phần thử đầu tiên và thứ 2 bằng 1 B3 : duyệt i chạy từ 3 đến n với công thức f[i] = f[i-1] + f[i-2] để tìm số Fibonacci thứ i B4 : in ra số fibonacci thứ n ( ghi ra f[n] ) Code C++ ``` #include<bits/stdc++.h> using namespace std; int n; long long f[100]; int main() { ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n; f[1]=1;f[2]=1; for(int i=3;i<=n;++i){ f[i]=f[i-1]+f[i-2]; }cout<<f[n]; return 0; } ```