M.n có thể giải thích rõ hơn hàm Fibo() với ạ!
Đề bài: Một dãy xâu ký tự G chỉ bao gồm các chữ cái A và B được gọi là dãy xâu Fibonacci nếu thỏa mãn tính chất: G(1) = A; G(2) = B; G(n) = G(n-2)+G(n-1).
Với phép cộng (+) là phép nối hai xâu với nhau. Bài toán đặt ra là tìm ký tự ở vị trí thứ i (tính từ 1) của xâu Fibonacci thứ n.
Cần giải thích về code Backtracking Fibonacci cộng xâu
Đầu tiên dễ thấy |G(n)| = F(n)
Ta có G(n) = G(n-2) \mathbin{\|} G(n-1) nên nếu k \leq F(n-2) thì phải tìm trong G(n-2)
3 Likes