Chuỗi Fibonacci trong Python sử dụng phạm vi

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ì thực hiện 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ớ. 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]

>>> 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]

Nếu không có số Fibonacci cho giá trị hiện tại của n, thì bạn tính toán nó bằng cách gọi đệ quy fibonacci_of[] 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]

Khá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]

>>> 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]

Cá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]

Để tính số Fibonacci tại vị trí n, bạn lưu hai số đầu tiên của dãy, 0 và 1, 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]

 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]

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 >> from fibonacci_class import Fibonacci

>>> fibonacci_of = Fibonacci[]

>>> fibonacci_of[5]
5
>>> fibonacci_of[6]
8
>>> fibonacci_of[7]
13

>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

 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 >> from fibonacci_class import Fibonacci

>>> fibonacci_of = Fibonacci[]

>>> fibonacci_of[5]
5
>>> fibonacci_of[6]
8
>>> fibonacci_of[7]
13

>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

>>> from fibonacci_class import Fibonacci

>>> fibonacci_of = Fibonacci[]

>>> fibonacci_of[5]
5
>>> fibonacci_of[6]
8
>>> fibonacci_of[7]
13

>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

 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]:
 6        raise ValueError[f'Positive integer number expected, got "{n}"']
 7
 8    # Handle the base cases
 9    if n in {0, 1}:
10        return n
11
12    previous, fib_number = 0, 1
13    for _ in range[2, n + 1]:
14        # Compute the next Fibonacci number, remember the previous one
15        previous, fib_number = fib_number, previous + fib_number
16
17    return fib_number

 1# fibonacci_func.py
 2
 3def fibonacci_of[n]:
 4    # Validate the value of n
 5    if not [isinstance[n, int] and n >= 0]:
 6        raise ValueError[f'Positive integer number expected, got "{n}"']
 7
 8    # Handle the base cases
 9    if n in {0, 1}:
10        return n
11
12    previous, fib_number = 0, 1
13    for _ in range[2, n + 1]:
14        # Compute the next Fibonacci number, remember the previous one
15        previous, fib_number = fib_number, previous + fib_number
16
17    return fib_number

 1# fibonacci_func.py
 2
 3def fibonacci_of[n]:
 4    # Validate the value of n
 5    if not [isinstance[n, int] and n >= 0]:
 6        raise ValueError[f'Positive integer number expected, got "{n}"']
 7
 8    # Handle the base cases
 9    if n in {0, 1}:
10        return n
11
12    previous, fib_number = 0, 1
13    for _ in range[2, n + 1]:
14        # Compute the next Fibonacci number, remember the previous one
15        previous, fib_number = fib_number, previous + fib_number
16
17    return fib_number

 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]:
 6        raise ValueError[f'Positive integer number expected, got "{n}"']
 7
 8    # Handle the base cases
 9    if n in {0, 1}:
10        return n
11
12    previous, fib_number = 0, 1
13    for _ in range[2, n + 1]:
14        # Compute the next Fibonacci number, remember the previous one
15        previous, fib_number = fib_number, previous + fib_number
16
17    return fib_number

>>> from fibonacci_func import fibonacci_of

>>> fibonacci_of[5]
5
>>> fibonacci_of[6]
8
>>> fibonacci_of[7]
13

>>> [fibonacci_of[n] for n in range[15]]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]