Dãy Fibonacci trong Cấu trúc dữ liệu và giải thuật
Dãy Fibonacci là gì?
Dãy Fibonacci tạo dãy các số bằng cách cộng hai số đằng trước. Dãy Fibonacci bắt đầu từ hai số: F0 & F1. Giá trị ban đầu của F0 & F1 có thể tương ứng là 0, 1 hoặc 1, 1.
Điều kiện của dãy Fibonacci là:
Fn = Fn-1 + Fn-2
Ví dụ một dãy Fibonacci:
F8 = 0 1 1 2 3 5 8 13
Ví dụ một dãy Fibonacci khác:
F8 = 1 1 2 3 5 8 13 21
Dưới đây là phần minh họa cho dãy Fibonacci trên:
Giải thuật sử dụng vòng lặp cho dãy Fibonacci
Đầu tiên, giải thuật của chúng ta sẽ sử dụng vòng lặp để tạo dãy Fibonacci:
Bắt đầu giải thuật Fibonacci(n) khai báo f0, f1, fib, loop Thiết lập f0 là 0 Thiết lập f1 là 1 hiển thị f0, f1 for loop ← 1 tới n fib ← f0 + f1 f0 ← f1 f1 ← fib hiển thị dãy fib kết thúc for Kết thúc giải thuật
Giải thuật sử dụng đệ qui cho dãy Fibonacci
Tiếp theo, dựa vào đệ qui chúng ta sẽ thiết kế giải thuật cho dãy Fibonacci như sau:
Bắt đầu giải thuật Fibonacci(n) khai báo f0, f1, fib, loop Thiết lập f0 là 0 Thiết lập f1 là 1 hiển thị f0, f1 for loop ← 1 tới n fib ← f0 + f1 f0 ← f1 f1 ← fib hiển thị dãy fib kết thúc for Kết thúc giải thuật
Theo Tutorialspoint
Bài trước: Bài toán Tháp Hà Nội (Tower of Hanoi)
Bài tiếp: assert.h trong C
Bạn nên đọc
-
Công thức tính đường chéo hình vuông, đường chéo hình chữ nhật
-
Trọng tâm là gì? Công thức tính trọng tâm của tam giác
-
Cách tính diện tích hình tròn và chu vi hình tròn
-
Công thức tính diện tích hình quạt tròn
-
Công thức tính đường cao trong tam giác thường, cân, đều, vuông
-
Công thức tính tỉ số thể tích các khối đa diện
Theo Nghị định 147/2024/ND-CP, bạn cần xác thực tài khoản trước khi sử dụng tính năng này. Chúng tôi sẽ gửi mã xác thực qua SMS hoặc Zalo tới số điện thoại mà bạn nhập dưới đây:


Cũ vẫn chất
-
Mệnh đề GROUP BY trong SQL Server
Hôm qua -
Điều kiện BETWEEN trong SQL Server
Hôm qua -
3 cách hiển thị mật khẩu *** trên trình duyệt vô cùng đơn giản
Hôm qua -
Những bài thơ đám cưới, thơ chúc mừng đám cưới cực hay và hài hước
Hôm qua -
Cách xóa khoảng trắng và lỗi xuống dòng trong Word
Hôm qua 3 -
Kí tự khoảng trống Liên Quân, ký tự khoảng trống Liên Quân
Hôm qua 19 -
Pick me là gì? Pick me girl, Pick me boy là gì?
Hôm qua -
Cách sửa lỗi VCRUNTIME140_1.dll not found, is missing trong Windows
Hôm qua 28 -
Hướng dẫn tạo một website cho người mới bắt đầu
Hôm qua -
Khai báo biến trong SQL Server
Hôm qua