Dãy Fibonacci là một dãy số nguyên khá nổi tiếng. Trình tự xuất hiện một cách tự nhiên trong nhiều vấn đề và có một định nghĩa đệ quy đẹp. Học cách tạo nó là một bước thiết yếu trong hành trình của lập trình viên thực dụng hướng tới việc làm chủ đệ quy. Trong hướng dẫn này, bạn sẽ tập trung tìm hiểu dãy Fibonacci là gì và cách tạo dãy bằng Python
Trong hướng dẫn này, bạn sẽ học cách
- Tạo dãy Fibonacci bằng thuật toán đệ quy
- Tối ưu hóa thuật toán Fibonacci đệ quy sử dụng ghi nhớ
- Tạo dãy Fibonacci bằng thuật toán lặp
Để tận dụng tối đa hướng dẫn này, bạn nên biết kiến thức cơ bản về ký hiệu Big O, lập trình hướng đối tượng, các phương thức đặc biệt của Python, câu lệnh điều kiện, hàm và cấu trúc dữ liệu cơ bản như danh sách, hàng đợi và ngăn xếp. Làm quen với những khái niệm này sẽ giúp bạn hiểu rất nhiều về những khái niệm mới mà bạn sẽ khám phá trong hướng dẫn này
Hãy đi sâu vào ngay
Tải xuống miễn phí. Nhận một chương mẫu từ Python Basics. Giới thiệu thực tế về Python 3 để xem cách bạn có thể đi từ trình độ mới bắt đầu lên trình độ trung cấp trong Python với một chương trình giảng dạy hoàn chỉnh, cập nhật về Python 3. 8
Bắt đầu với dãy Fibonacci
Leonardo Fibonacci là một nhà toán học người Ý, người đã có thể nhanh chóng đưa ra câu trả lời cho câu hỏi này của Hoàng đế Frederick II của Swabia. “Một năm thu được bao nhiêu cặp thỏ, không kể số thỏ chết, giả sử mỗi cặp thỏ sinh thêm một cặp mỗi tháng và cặp vợ chồng trẻ nhất đã có thể sinh sản vào tháng thứ hai của cuộc đời?”
Câu trả lời là trình tự sau đây
Mẫu bắt đầu sau hai số đầu tiên, 0 và 1, trong đó mỗi số trong dãy luôn là tổng của hai số trước nó. Các nhà toán học Ấn Độ đã biết về dãy số này từ thế kỷ thứ sáu và Fibonacci đã tận dụng nó để tính toán sự tăng trưởng của quần thể thỏ
F[n] được dùng để chỉ số cặp thỏ có mặt trong tháng thứ n, do đó, dãy có thể được biểu thị như sau
Trong thuật ngữ toán học, bạn gọi đây là một quan hệ lặp lại, nghĩa là mỗi phần tử của chuỗi [ngoài 0 và 1] là một hàm của các phần tử trước đó
Ngoài ra còn có một phiên bản của dãy số mà hai số đầu tiên đều là 1, như vậy
Trong phiên bản thay thế này, F[0] vẫn hoàn toàn là 0, nhưng thay vào đó, bạn bắt đầu từ F[1] và F[2]. Thuật toán vẫn giữ nguyên vì bạn luôn tính tổng hai số trước đó để lấy số tiếp theo trong dãy
Với mục đích của hướng dẫn này, bạn sẽ sử dụng phiên bản của chuỗi bắt đầu bằng 0
Loại bỏ các quảng cáoKiểm tra đệ quy đằng sau dãy Fibonacci
Tạo dãy Fibonacci là một bài toán đệ quy kinh điển. Đệ quy là khi một hàm tham chiếu đến chính nó để chia nhỏ vấn đề mà nó đang cố giải quyết. Trong mọi lệnh gọi hàm, vấn đề trở nên nhỏ hơn cho đến khi nó đạt đến trường hợp cơ sở, sau đó, nó sẽ trả về kết quả cho từng người gọi trung gian cho đến khi nó trả lại kết quả cuối cùng cho người gọi ban đầu
Nếu bạn muốn tính số Fibonacci F[5], trước tiên, bạn cần tính các số trước của nó, F[4] và F[3]. Và để tính F[4] và F[3], bạn cần tính các tiền thân của chúng. Việc phân tích F[5] thành các bài toán con nhỏ hơn sẽ như thế này
Mỗi khi hàm Fibonacci được gọi, nó sẽ được chia thành hai bài toán con nhỏ hơn vì đó là cách bạn đã xác định quan hệ truy hồi. Khi nó đạt đến trường hợp cơ bản của F[0] hoặc F[1], cuối cùng nó có thể trả lại kết quả cho người gọi nó
Để tính số thứ năm trong dãy Fibonacci, bạn giải các bài toán nhỏ hơn nhưng giống hệt nhau cho đến khi đạt đến các trường hợp cơ bản, nơi bạn có thể bắt đầu trả về kết quả
Các bài toán con được tô màu trên biểu đồ này thể hiện các nghiệm lặp đi lặp lại cho cùng một bài toán. Nếu bạn đi sâu hơn vào cây, bạn sẽ tìm thấy nhiều giải pháp lặp đi lặp lại này. Điều này có nghĩa là để tạo ra một dãy Fibonacci theo cách đệ quy, bạn phải tính đi tính lại nhiều số trung gian. Đây là một trong những vấn đề cơ bản trong cách tiếp cận đệ quy đối với dãy Fibonacci
Tạo đệ quy dãy Fibonacci trong Python
Thuật toán tối thiểu và phổ biến nhất để tạo dãy Fibonacci yêu cầu bạn viết mã một hàm đệ quy tự gọi chính nó nhiều lần nếu cần cho đến khi tính được số Fibonacci mong muốn
>>>
>>> def fibonacci_of[n]:
.. if n in {0, 1}: # Base case
.. return n
.. return fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
...
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
Bên trong
>>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
7, trước tiên bạn kiểm tra trường hợp cơ sở. Sau đó, bạn trả về tổng các giá trị có được từ việc gọi hàm với hai giá trị trước đó là >>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
8. Việc hiểu danh sách ở cuối ví dụ tạo ra một dãy Fibonacci với mười lăm số đầu tiênChức năng này nhanh chóng rơi vào vấn đề lặp lại mà bạn đã thấy ở phần trên. Tính toán ngày càng đắt hơn khi
>>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
8 lớn hơn. Thời gian cần thiết tăng theo cấp số nhân vì hàm tính toán lặp đi lặp lại nhiều bài toán con giống hệt nhauGhi chú. Không thử chức năng này tại nhà với số lớn hơn 50. Tùy thuộc vào phần cứng của bạn, bạn có thể phải đợi một thời gian dài trước khi thấy kết quả—nếu bạn làm đến cùng
Để tính F[5],
>>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
7 phải gọi chính nó mười lăm lần. Để tính F[n], độ sâu tối đa của cây lệnh gọi là n và vì mỗi lệnh gọi hàm tạo ra hai lệnh gọi hàm bổ sung, nên độ phức tạp về thời gian của hàm đệ quy này là O[2n]Hầu hết các cuộc gọi đó là dư thừa vì bạn đã tính toán kết quả của chúng. F[3] xuất hiện hai lần và F[2] xuất hiện ba lần. F[1] và F[0] là trường hợp cơ bản, vì vậy có thể gọi chúng nhiều lần. Bạn có thể muốn tránh sự lặp lại lãng phí này, đó là chủ đề của các phần sau
Tối ưu hóa thuật toán đệ quy cho dãy Fibonacci
Có ít nhất hai kỹ thuật bạn có thể sử dụng để làm cho thuật toán tạo dãy Fibonacci hiệu quả hơn—nói cách khác, để làm cho việc tính toán mất ít thời gian hơn. Những kỹ thuật này đảm bảo rằng bạn không phải tính đi tính lại cùng một giá trị, đó là điều khiến thuật toán ban đầu trở nên kém hiệu quả. Chúng được gọi là ghi nhớ và lặp lại
Ghi nhớ thuật toán đệ quy
Như bạn đã thấy trong đoạn mã trên, hàm Fibonacci tự gọi chính nó nhiều lần với cùng một đầu vào. Thay vì một cuộc gọi mới mỗi lần, bạn có thể lưu trữ kết quả của các cuộc gọi trước đó trong một thứ gì đó giống như bộ nhớ cache. Bạn có thể sử dụng danh sách Python để lưu trữ kết quả của các phép tính trước đó. Kỹ thuật này được gọi là ghi nhớ
Ghi nhớ tăng tốc độ thực thi các hàm đệ quy đắt tiền bằng cách lưu trữ các kết quả đã tính toán trước đó vào bộ đệm. Bằng cách này, khi cùng một đầu vào xảy ra lần nữa, hàm chỉ cần tra cứu kết quả tương ứng và trả về kết quả đó mà không phải chạy lại tính toán. Bạn có thể tham khảo các kết quả này dưới dạng lưu trữ hoặc ghi nhớ
Với tính năng ghi nhớ, bạn chỉ cần duyệt qua cây cuộc gọi có độ sâu n một lần sau khi trở về từ trường hợp cơ sở, khi bạn truy xuất tất cả các giá trị được tính toán trước đó được đánh dấu bằng màu vàng, F[2] và F[3], từ bộ đệm trước đó
Đường màu cam cho biết không có đầu vào nào của hàm Fibonacci được gọi nhiều lần. Điều này làm giảm đáng kể độ phức tạp về thời gian của thuật toán từ hàm mũ O[2n] thành tuyến tính O[n]
Ngay cả đối với các trường hợp cơ bản, bạn có thể thay thế việc gọi F[0] và F[1] bằng cách chỉ truy xuất các giá trị trực tiếp từ bộ đệm tại các chỉ số 0 và 1, vì vậy cuối cùng bạn chỉ gọi hàm sáu lần thay vì mười lăm lần
Đây là bản dịch có thể có của việc tối ưu hóa này sang mã Python
>>>
>>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
Trong ví dụ này, bạn sử dụng từ điển Python để lưu trữ các số Fibonacci đã tính. Ban đầu,
>>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
0 chứa các giá trị bắt đầu của dãy Fibonacci, 0 và 1. Bên trong hàm, trước tiên bạn kiểm tra xem số Fibonacci cho giá trị đầu vào hiện tại của >>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
8 đã có trong >>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
0 chưa. Nếu vậy thì bạn trả lại số trong tầm tayNếu không có số Fibonacci cho giá trị hiện tại của
>>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
8, thì bạn tính toán nó bằng cách gọi đệ quy >>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
7 và cập nhật >>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
0. Bước cuối cùng là trả về số Fibonacci được yêu cầuLoại bỏ các quảng cáoKhám phá thuật toán lặp
Điều gì sẽ xảy ra nếu bạn thậm chí không phải gọi hàm Fibonacci đệ quy?
Bạn biết rằng hai số đầu tiên trong dãy là 0 và 1 và mỗi số tiếp theo trong dãy là tổng của hai số liền trước nó. Vì vậy, bạn chỉ cần tạo một vòng lặp cộng hai số trước đó,
>>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
7 và >>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
8, với nhau để tìm số ở vị trí >>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
8 trong dãyCác số màu tím được in đậm trong sơ đồ bên dưới biểu thị các số mới cần được tính toán và thêm vào
>>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
0 trong mỗi bước lặpĐể tính số Fibonacci tại vị trí
>>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
8, bạn lưu trữ hai số đầu tiên của dãy, 0 và 1, trong >>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
0. Sau đó, tính liên tiếp các số tiếp theo cho đến khi bạn có thể trả về 1# fibonacci_class.py
2
3class Fibonacci:
4 def __init__[self]:
5 self.cache = [0, 1]
6
7 def __call__[self, n]:
8 # Validate the value of n
9 if not [isinstance[n, int] and n >= 0]:
10 raise ValueError[f'Positive integer number expected, got "{n}"']
11
12 # Check for computed Fibonacci numbers
13 if n >> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
0 là một đối tượng hoàn toàn riêng biệt, vì vậy bạn không có quyền kiểm soát đối với nóDưới đây là mã triển khai giải pháp dựa trên lớp của bạn
1# fibonacci_class.py
2
3class Fibonacci:
4 def __init__[self]:
5 self.cache = [0, 1]
6
7 def __call__[self, n]:
8 # Validate the value of n
9 if not [isinstance[n, int] and n >= 0]:
10 raise ValueError[f'Positive integer number expected, got "{n}"']
11
12 # Check for computed Fibonacci numbers
13 if n = 0]:
10 raise ValueError[f'Positive integer number expected, got "{n}"']
11
12 # Check for computed Fibonacci numbers
13 if n = 0]:
10 raise ValueError[f'Positive integer number expected, got "{n}"']
11
12 # Check for computed Fibonacci numbers
13 if n = 0]:
10 raise ValueError[f'Positive integer number expected, got "{n}"']
11
12 # Check for computed Fibonacci numbers
13 if n = 0]:
10 raise ValueError[f'Positive integer number expected, got "{n}"']
11
12 # Check for computed Fibonacci numbers
13 if n = 0]:
10 raise ValueError[f'Positive integer number expected, got "{n}"']
11
12 # Check for computed Fibonacci numbers
13 if n = 0]:
10 raise ValueError[f'Positive integer number expected, got "{n}"']
11
12 # Check for computed Fibonacci numbers
13 if n >> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
8 bằng cách sử dụng câu lệnh có điều kiện. Nếu >>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
8 không phải là số nguyên dương, thì phương thức này sẽ tăng >>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
83Dòng 13 định nghĩa một câu lệnh có điều kiện để kiểm tra các số Fibonacci đã được tính toán và có sẵn trong
1# fibonacci_class.py
2
3class Fibonacci:
4 def __init__[self]:
5 self.cache = [0, 1]
6
7 def __call__[self, n]:
8 # Validate the value of n
9 if not [isinstance[n, int] and n >= 0]:
10 raise ValueError[f'Positive integer number expected, got "{n}"']
11
12 # Check for computed Fibonacci numbers
13 if n >> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
8 đã có trong 1# fibonacci_class.py
2
3class Fibonacci:
4 def __init__[self]:
5 self.cache = [0, 1]
6
7 def __call__[self, n]:
8 # Validate the value of n
9 if not [isinstance[n, int] and n >= 0]:
10 raise ValueError[f'Positive integer number expected, got "{n}"']
11
12 # Check for computed Fibonacci numbers
13 if n = 0]:
10 raise ValueError[f'Positive integer number expected, got "{n}"']
11
12 # Check for computed Fibonacci numbers
13 if n >> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
88. Sau đó chạy mã này trong vỏ tương tác của bạn>>>
>>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
8Tại đây, bạn tạo rồi gọi một thể hiện của lớp
1# fibonacci_class.py
2
3class Fibonacci:
4 def __init__[self]:
5 self.cache = [0, 1]
6
7 def __call__[self, n]:
8 # Validate the value of n
9 if not [isinstance[n, int] and n >= 0]:
10 raise ValueError[f'Positive integer number expected, got "{n}"']
11
12 # Check for computed Fibonacci numbers
13 if n >> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
50. Cuộc gọi đầu tiên sử dụng >>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
51 làm đối số và trả về >>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
51, đây là số Fibonacci thứ sáu vì bạn đang sử dụng các chỉ số dựa trên số khôngViệc triển khai thuật toán dãy Fibonacci này khá hiệu quả. Khi bạn có một thể hiện của lớp, thuộc tính
1# fibonacci_class.py
2
3class Fibonacci:
4 def __init__[self]:
5 self.cache = [0, 1]
6
7 def __call__[self, n]:
8 # Validate the value of n
9 if not [isinstance[n, int] and n >= 0]:
10 raise ValueError[f'Positive integer number expected, got "{n}"']
11
12 # Check for computed Fibonacci numbers
13 if n >> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
5Bây giờ, thay vì sử dụng đệ quy trong
>>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
7, bạn đang sử dụng phép lặp. Việc triển khai thuật toán dãy Fibonacci này chạy trong thời gian tuyến tính O[n]. Đây là một sự cố của mãDòng 3 định nghĩa
7, lấy một số nguyên dương,>>> cache = {0: 0, 1: 1} >>> def fibonacci_of[n]: .. if n in cache: # Base case .. return cache[n] .. # Compute and cache the Fibonacci number .. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case .. return cache[n] >>> [fibonacci_of[n] for n in range[15]] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
8, làm đối số>>> cache = {0: 0, 1: 1} >>> def fibonacci_of[n]: .. if n in cache: # Base case .. return cache[n] .. # Compute and cache the Fibonacci number .. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case .. return cache[n] >>> [fibonacci_of[n] for n in range[15]] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
Dòng 5 và 6 thực hiện xác thực thông thường của
8>>> cache = {0: 0, 1: 1} >>> def fibonacci_of[n]: .. if n in cache: # Base case .. return cache[n] .. # Compute and cache the Fibonacci number .. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case .. return cache[n] >>> [fibonacci_of[n] for n in range[15]] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
Dòng 9 và 10 xử lý các trường hợp cơ sở trong đó
8 là 0 hoặc 1>>> cache = {0: 0, 1: 1} >>> def fibonacci_of[n]: .. if n in cache: # Base case .. return cache[n] .. # Compute and cache the Fibonacci number .. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case .. return cache[n] >>> [fibonacci_of[n] for n in range[15]] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
Dòng 12 định nghĩa hai biến cục bộ,
59 và>>> cache = {0: 0, 1: 1} >>> def fibonacci_of[n]: .. if n in cache: # Base case .. return cache[n] .. # Compute and cache the Fibonacci number .. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case .. return cache[n] >>> [fibonacci_of[n] for n in range[15]] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
10, đồng thời khởi tạo chúng bằng hai số đầu tiên trong dãy Fibonacci>>> cache = {0: 0, 1: 1} >>> def fibonacci_of[n]: .. if n in cache: # Base case .. return cache[n] .. # Compute and cache the Fibonacci number .. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case .. return cache[n] >>> [fibonacci_of[n] for n in range[15]] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
Dòng 13 bắt đầu một vòng lặp
11 lặp từ>>> cache = {0: 0, 1: 1} >>> def fibonacci_of[n]: .. if n in cache: # Base case .. return cache[n] .. # Compute and cache the Fibonacci number .. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case .. return cache[n] >>> [fibonacci_of[n] for n in range[15]] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
12 đến>>> cache = {0: 0, 1: 1} >>> def fibonacci_of[n]: .. if n in cache: # Base case .. return cache[n] .. # Compute and cache the Fibonacci number .. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case .. return cache[n] >>> [fibonacci_of[n] for n in range[15]] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
13. Vòng lặp sử dụng dấu gạch dưới [>>> cache = {0: 0, 1: 1} >>> def fibonacci_of[n]: .. if n in cache: # Base case .. return cache[n] .. # Compute and cache the Fibonacci number .. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case .. return cache[n] >>> [fibonacci_of[n] for n in range[15]] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
14] cho biến vòng lặp vì nó là biến loại bỏ và bạn sẽ không sử dụng giá trị này trong mã>>> cache = {0: 0, 1: 1} >>> def fibonacci_of[n]: .. if n in cache: # Base case .. return cache[n] .. # Compute and cache the Fibonacci number .. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case .. return cache[n] >>> [fibonacci_of[n] for n in range[15]] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
Dòng 15 tính toán số Fibonacci tiếp theo trong dãy và ghi nhớ số trước đó
Dòng 17 trả về số Fibonacci được yêu cầu
Để dùng thử mã này, hãy quay lại phiên tương tác của bạn và chạy mã sau
>>>
>>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
1Việc triển khai
>>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
7 này khá tối thiểu. Nó sử dụng tính năng giải nén lặp lại để tính toán các số Fibonacci trong các vòng lặp, điều này khá hiệu quả về mặt bộ nhớ. Tuy nhiên, mỗi khi bạn gọi hàm với một giá trị khác của >>> cache = {0: 0, 1: 1}
>>> def fibonacci_of[n]:
.. if n in cache: # Base case
.. return cache[n]
.. # Compute and cache the Fibonacci number
.. cache[n] = fibonacci_of[n - 1] + fibonacci_of[n - 2] # Recursive case
.. return cache[n]
>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
8, nó phải tính toán lại chuỗi đó một lần nữa. Để khắc phục điều này, bạn có thể sử dụng các bao đóng và làm cho chức năng của bạn ghi nhớ các giá trị đã được tính toán giữa các lần gọi. Đi trước và cung cấp cho nó một thửPhần kết luận
Dãy Fibonacci có thể giúp bạn hiểu rõ hơn về đệ quy. Trong hướng dẫn này, bạn đã học dãy Fibonacci là gì. Bạn cũng đã tìm hiểu về một số thuật toán phổ biến để tạo chuỗi và cách dịch chúng sang mã Python
Dãy Fibonacci có thể là một bàn đạp tuyệt vời và là điểm khởi đầu để bước vào thế giới đệ quy, đây là một kỹ năng cơ bản cần có của một lập trình viên
Trong hướng dẫn này, bạn đã học cách
- Tạo dãy Fibonacci bằng thuật toán đệ quy
- Tối ưu hóa thuật toán Fibonacci đệ quy của bạn bằng cách sử dụng tính năng ghi nhớ
- Tạo dãy Fibonacci bằng thuật toán lặp
Bạn cũng đã hình dung thuật toán đệ quy được ghi nhớ để hiểu rõ hơn về cách nó hoạt động đằng sau hậu trường. Để làm điều đó, bạn đã sử dụng sơ đồ ngăn xếp cuộc gọi
Khi bạn nắm vững các khái niệm trong hướng dẫn này, kỹ năng lập trình Python của bạn sẽ được cải thiện cùng với tư duy thuật toán đệ quy của bạn
Đánh dấu là đã hoàn thành
Xem ngay Hướng dẫn này có một khóa học video liên quan do nhóm Real Python tạo. Xem nó cùng với hướng dẫn bằng văn bản để hiểu sâu hơn. Khám phá dãy Fibonacci bằng Python
🐍 Thủ thuật Python 💌
Nhận một Thủ thuật Python ngắn và hấp dẫn được gửi đến hộp thư đến của bạn vài ngày một lần. Không có thư rác bao giờ. Hủy đăng ký bất cứ lúc nào. Được quản lý bởi nhóm Real Python
Gửi cho tôi thủ thuật Python »
Giới thiệu về Mandy Wong
Mandy là một Pythonista vừa chớm nở muốn chia sẻ tình yêu và kiến thức của mình về Python và công nghệ phần mềm với thế giới. Cô ấy cũng là một TinyML + Kỹ sư dữ liệu trong đào tạo, một Muley và một vận động viên chơi gôn cạnh tranh hàng đầu bán thời gian đầy tham vọng
» Thông tin thêm về MandyMỗi hướng dẫn tại Real Python được tạo bởi một nhóm các nhà phát triển để nó đáp ứng các tiêu chuẩn chất lượng cao của chúng tôi. Các thành viên trong nhóm đã làm việc trong hướng dẫn này là
Aldren
David
Geir Arne
Joanna
Gia-cốp
leodanis
Sadie
Bậc thầy Kỹ năng Python trong thế giới thực Với quyền truy cập không giới hạn vào Python thực
Tham gia với chúng tôi và có quyền truy cập vào hàng nghìn hướng dẫn, khóa học video thực hành và cộng đồng các Pythonistas chuyên gia
Nâng cao kỹ năng Python của bạn »
Bậc thầy Kỹ năng Python trong thế giới thực
Với quyền truy cập không giới hạn vào Python thực
Tham gia với chúng tôi và có quyền truy cập vào hàng ngàn hướng dẫn, khóa học video thực hành và cộng đồng Pythonistas chuyên gia
Nâng cao kỹ năng Python của bạn »
Bạn nghĩ sao?
Đánh giá bài viết này
Tweet Chia sẻ Chia sẻ EmailBài học số 1 hoặc điều yêu thích mà bạn đã học được là gì?
Mẹo bình luận. Những nhận xét hữu ích nhất là những nhận xét được viết với mục đích học hỏi hoặc giúp đỡ các sinh viên khác. Nhận các mẹo để đặt câu hỏi hay và nhận câu trả lời cho các câu hỏi phổ biến trong cổng thông tin hỗ trợ của chúng tôi