- vừa được xem lúc

Tính tổng các số Fibonacci từ 1 tới 4 triệu

0 0 66

Người đăng: Huy Tran

Theo The Full Snack

Tính tổng các số Fibonacci từ 1 tới 4 triệu

Cuối tuần này có nói chuyện với bác @haond về một đề tài khá là thú vị, đó là bài toán: Tính tổng các số Fibonacci từ 1 tới 4 triệu

Giải pháp đơn giản

Để tính một số Fibonacci thì cực kì đơn giản, chỉ cần làm theo công thức:

$F_{n}=F_{n-1}+F_{n-2}$

Code thì khá là đơn giản bằng cách dùng đệ quy:

func Fibonacci(n: Int) -> Int { if n <= 2 { return 1 } return Fibonacci(n - 1) + Fibonacci(n - 2)
}

Hoặc dùng vòng lặp để khử đệ quy:

func Fibonacci(n: Int) -> Int { var a = 0 var b = 1 var next = 0 for i in 0..<n { if i <= 1 { next = i } else { next = a + b a = b b = next } } return next
}

Quay lại bài toán tính tổng các số Fibonacci, ta có thể implement một hàm tính tổng đơn giản như sau:

func Sum(n: Int) -> Int { var sum = 0 for i in 0..<n { sum += Fibonacci(n) } return sum
}

Tuy nhiên thì với thuật toán như vậy, chúng ta có gặp phải vấn đề gì không?

Câu trả lời là có, vấn đề rất lớn!

Đầu tiên hãy nhìn vào đồ thị biểu diễn thời gian cần để tính Fibonacci dưới đây:

Bình luận

Bài viết tương tự

- vừa được xem lúc

Thuật toán quay lui (Backtracking)

Quay lui là một kĩ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong số các lựa chọn khả dĩ và đệ quy.

0 0 38

- vừa được xem lúc

Các thuật toán cơ bản trong AI - Phân biệt Best First Search và Uniform Cost Search (UCS)

Nếu bạn từng đọc các thuật toán trong AI (Artificial Intelligence - Trí tuệ nhân tạo), rất có thể bạn từng nghe qua về các thuật toán tìm kiếm cơ bản: UCS (thuộc chiến lược tìm kiếm mù) và Best First Search (thuộc chiến lược tìm kiếm kinh nghiệm). Khác nhau rõ từ khâu phân loại rồi, thế nhưng hai th

0 0 152

- vừa được xem lúc

Sử dụng vector trong lập trình C++ - giải bài toán lập trình muôn thủa

Chào buổi tối mọi người, hôm nay lang thang trên mạng bắt gặp bài toán quen thuộc một thời của quãng đường sinh viên IT. Đấy chính là câu số 1 trong đề thi dưới đây:.

0 0 35

- vừa được xem lúc

MÔ PHỎNG THUẬT TOÁN VƯƠNG HẠO TRONG PROLOG

. 1. Các luật suy diễn trong thuật toán Vương Hạo. Luật 1: Chuyển vế các giả thuyết và kết luận ở dạng phủ định. Ví dụ: p v q, !(r ^ s), !q, p v r -> s, !p <=> p v q, p v r, p -> s, r ^ s, q.

0 0 76

- vừa được xem lúc

A* Search Algorithm

What is A* Search Algorithm. How it works. . Explanation.

0 0 42

- vừa được xem lúc

Python: Jump Search

Search là một từ khóa khá là quen thuộc đối với chúng ta. Hiểu theo đúng nghĩa đen của nó chính là "Tìm kiếm".

0 0 35