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 diện tích mặt cầu, thể tích khối cầu
-
Công thức tính diện tích hình hộp chữ nhật
-
Công thức tính diện tích hình bình hành, chu vi hình bình hành
-
Công thức tính diện tích hình thoi, chu vi hình thoi
-
Công thức tính diện tích hình thang: thường, vuông, cân
-
Công thức tính chu vi hình tứ giác, diện tích hình tứ giác
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
-
PowerShell và mọi điều bạn cần biết về tiện ích này
Hôm qua -
Hàm COUNT trong Excel: Công thức, cách dùng hàm đếm này đơn giản nhất
Hôm qua -
12 cách truy cập nhanh Settings trên Windows 10
Hôm qua 1 -
Cách thêm máy in vào Windows 10
Hôm qua 2 -
Cách sửa lỗi “Ethernet doesn’t have a valid IP configuration”
Hôm qua -
5 cách kiểm tra ổ cứng là SSD hay HDD trên máy tính Windows
Hôm qua -
Hàm RIGHT, cách dùng hàm cắt chuỗi ký tự bên phải trong Excel
Hôm qua -
Lộ địa chỉ IP nguy hiểm như thế nào?
Hôm qua 2 -
Cách cài đặt TWRP Recovery trên Android (không cần root)
Hôm qua 1 -
Cách sửa lỗi mất thanh Language bar trên Windows 10
Hôm qua