Fibonacci là dãy số kinh điển trong toán học được tìm thấy cách đây hơn 800 năm. Đến nay các nhà khoa học phát hiện nhiều trùng hợp thú vị về dãy số này trong tự nhiên. Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng 1 và 1, sau đó các số tiếp theo sẽ bằng tổng của 2 số liền trước nó.
Dã số Fibonacci 1, 1, 2, 3, 5, 8, 13, 21….
Thuật toán về dãy số Fibonacci thường được dùng trong giảng dạy và kiểm tra kỹ năng về thuật toán. Do vậy, nắm rõ về thuật toán này là một lợi thế của bạn.
Yêu cầu
Viết chương trình nhập vào một số n và in ra n số đầu tiên của dãy fibonacci.
Về lý thuyết
- Dãy fibonacci bắt đầu với hai phần tử f(1)=1, f(2)=1
- Số tiếp theo sẽ bằng tổng của hai số trước đó f(n) = f(n-1) + f(n-2)
Bài toán này có thể giải bằng phương pháp đệ qui, nhưng ở đây chúng ta sẽ giải bằng vòng lặp.
Phân tích tìm cách giải
- Đầu vào: cần nhập giá trị cho n, khởi tại biến f1=1, f2=1
- Đầu ra: In ra dãy số fibonacci với n chữ số đầu tiên
Các bước thực hiện:
Nhập giá trị cho biến n
Kiểm tra n
Nếu n <=2
Thông báo nhập lại giá trị lớn hơn 2
Nếu n >2
In f1 và f2
Cho biến i chạy từ 3 đến n
Tính f=f1+f2
In f ra
Gán f1=f2
Gán f2=f
Cách biểu diễn thuật toán về dãy số Fibonacci
Trong trường hợp này, tôi sử dụng ngôn ngữ giả.
Declare int n, i, f, f1=1,f2=1
Input n
If n<=2 then
Print ‘Lỗi, n phải lớn hơn 2. Vui lòng nhập lại’
Else
Print f1,f2
Loop i=3 to n
f= f1+f2
Print f
f1=f2
f2=f
Kỹ thuật Dry Run
Kết quả Dry Run khi n=8:
