Xây dụng thuật toán tính tổng của n số Fibonacci đầu tiên

Đã đăng vào thg 12 12, 2018 6:44 SA 4 phút đọc

Bài đăng này đã không được cập nhật trong 3 năm

Có lẽ là một trong những thuật toán nổi tiếng nhất từ trước đến nay, nhưng vẫn còn rất nhiều người phải gặp khó khăn khi cố gắng tìm một giải pháp hiệu quả. Hãy để mình giới thiệu cho bạn về chuỗi Fibonacci.

Statement

Cho 1 số N, trả về số fibonacci thứ N, trong đó chuỗi đó như sau:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

Sau khi xem qua, bạn có thể dễ dàng nhận thấy mỗi phần tử trong chuỗi là tổng của 2 phần tử liền trước nó.

F[n] = F[n-1] + F[n-2]

First implementation
Vì vậy, bây giờ chúng ta sẽ implement đoạn code đầu tiên, chúng ta sẽ sử dụng một vòng lặp đơn giản để đi đến lời giải.

function fibonacci[num]{ var a = 1, b = 0, temp; while [num > 0]{ temp = a; a = a + b; b = temp; num--; } return b; }

Đây có lẽ là giải pháp đầu tiên trong đầu của bạn. Phần quan trọng ở đây là chúng ta tính toán số tiếp theo bằng cách thêm số hiện tại vào số cũ.
Và tin tốt là nó có độ phức tạp O[n]. Nhưng bây giờ hãy để thử xem một số cách khác để tiếp cận vấn đề.

Dùng đệ quy

Bây giờ hãy để xem nếu chúng ta có thể làm cho nó trông xịn hơn, bây giờ chúng ta sẽ sử dụng đệ quy để làm điều đó. function fibonacci[num] { if [num