Hướng dẫn giải của [200 đề thầy Đức] Bài 126: Chuỗi Fibonacci
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Chuỗi Fibonacci được định nghĩa đệ quy, với phép cộng là ghép chuỗi. Cần in chuỗi thứ n.
Sub 1: Đệ quy đúng định nghĩa — ~O(φ^n)~
Viết hàm đệ quy fib(i) trả về fib(i-1) + fib(i-2). Cách này chậm với n lớn vì các lời gọi bị lặp lại. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
char X, Y;
// Đúng theo định nghĩa đệ quy: F_1 = x, F_2 = y, F_i = F_{i-1} + F_{i-2}
string fib(int i) {
if (i == 1) return string(1, X);
if (i == 2) return string(1, Y);
return fib(i - 1) + fib(i - 2); // đệ quy, chậm với n lớn
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> X >> Y;
int n;
cin >> n;
cout << fib(n) << "\n";
return 0;
}
Sub 2: Lặp giữ hai chuỗi liền trước — ~O(n · độ dài)~
Giữ hai chuỗi F(i-2) và F(i-1), mỗi bước tính F(i) = F(i-1) + F(i-2) rồi dịch cửa sổ. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
char x, y;
cin >> x >> y;
int n;
cin >> n;
// Lặp: giữ hai chuỗi liền trước (F_{i-2}, F_{i-1}), tính F_i = F_{i-1} + F_{i-2}
string a(1, x); // F_1
string b(1, y); // F_2
if (n == 1) {
cout << a << "\n";
return 0;
}
for (int i = 3; i <= n; i++) {
string c = b + a; // F_i
a = b;
b = c;
}
cout << b << "\n";
return 0;
}
Bình luận