Solutions of Fibonacci

Select solution language

hvnamyd Created at 2 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; } ```

minhnhatha Created at 0 likes

Dãy Fibonacci là dãy bắt đầu bằng 0, 1 và các số sau bằng tổng 2 số trước đó: ``` f[0] = 0 f[1] = 1 f[n] = f[n - 1] + f[n - 2] ``` Nếu các bạn học dãy rồi thì đơn giản lưu vào một dãy xong cần số Fibonacci thứ bao nhiêu thì lấy ra. Mình sẽ cho các bạn code tham khảo mà không dùng dãy. **Code Python:** ``` n = int(input()) if n == 1: print(1) x = 0 y = 1 ans = 1 for i in range(1, n, 1): ans = x + y x = y y = ans print(ans) ``` Trường hợp cơ sở là $f[1] = 1$ Ở đây có $x$ và $y$ là 2 số đứng trước số cần chọn (ban đầu là $f[0] = 0$ và $f[1] = 1$). Mỗi lần đến số Fibonacci thứ $i$ thì $ans$ gán bằng tổng của $x$ và $y$ Sau đó cập nhật $x = y$ (lúc này là số Fibonacci thứ $i - 1$) và $y$ là số Fibonacci thứ $i$ (là $ans$ đã gán trước đó) để chuẩn bị cho số Fibonacci thứ $i + 1$ Tiếp tục cho đến $n$ thì in ra