Hướng dẫn is there a fibonacci function in python? - có một hàm fibonacci trong python không?

Ghi nhớ thuật toán đệ quy

Như bạn đã thấy trong mã trên, hàm Fibonacci tự gọi mình 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 cái gì đó như bộ nhớ bộ nhớ. Bạn có thể sử dụng danh sách Python để lưu trữ kết quả của các tính toán trước đó. Kỹ thuật này được gọi là ghi nhớ.memoization.

Ghi nhớ tăng tốc độ thực hiện các hàm đệ quy đắt tiền bằng cách lưu trữ kết quả được tính toán trước đó trong bộ đệm. Bằng cách này, khi cùng một đầu vào xảy ra một lần nữa, chức năng chỉ cần tra cứu kết quả tương ứng và trả về nó mà không phải chạy lại tính toán. Bạn có thể tham khảo những kết quả này là bộ nhớ cache hoặc ghi nhớ:cached or memoized:

Với ghi nhớ, bạn chỉ cần đi 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 lấy tất cả các giá trị được tính toán trước đó được tô màu vàng, F (2) và F (3), từ bộ đệm trước đó.

Đường dẫn màu cam cho thấy rằng không có đầu vào cho hàm fibonacci được gọi là nhiều lần. Điều này làm giảm đáng kể độ phức tạp thời gian của thuật toán từ O (2N) theo cấp số nhân đến tuyến tính O (N).

Ngay cả đối với các trường hợp cơ sở, bạn có thể thay thế gọi F (0) và F (1) chỉ bằng cá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 bạn sẽ gọi hàm chỉ sáu lần thay vì mười lăm!

Ở đây, một bản dịch có thể có của 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 được tính toán. 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]

Nếu không có số Fibonacci cho giá trị hiện tại là n, thì bạn tính toán nó bằng cách gọi fibonacci_of() đệ quy và cập nhật ____10. Bước cuối cùng là trả về số Fibonacci được yêu cầu.

Khám phá một thuật toán lặp

Điều gì sẽ xảy ra nếu bạn không cần phải gọi chức năng Fibonacci đệ quy thì sao? Bạn thực sự có thể sử dụng một thuật toán lặp để tính toán số tại vị trí n trong chuỗi Fibonacci.

Bạn biết rằng hai số đầu tiên trong chuỗi là 0 và 1 và mỗi số tiếp theo trong chuỗi là tổng của hai người tiền nhiệm trước đó. Vì vậy, bạn chỉ có thể tạo một vòng lặp thêm 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 đậm trong sơ đồ dưới đây thể hiện 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 toán số Fibonacci tại vị trí n, bạn lưu trữ hai số đầu tiên của chuỗi, 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]

 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 < len(self.cache):
14            return self.cache[n]
15        else:
16            # Compute and cache the requested Fibonacci number
17            fib_number = self(n - 1) + self(n - 2)
18            self.cache.append(fib_number)
19
20        return self.cache[n]

Sử dụng đệ quy và lớp Python

Cách tiếp cận đầu tiên của bạn để tạo chuỗi Fibonacci sẽ sử dụng lớp Python và đệ quy. Một lợi thế của việc sử dụng lớp so với hàm đệ quy được ghi nhớ mà bạn đã thấy trước đó là một lớp giữ trạng thái và hành vi (đóng gói) với nhau trong cùng một đối tượng. Tuy nhiên, trong ví dụ chức nă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]

Dưới đây là mã thực hiện 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 < len(self.cache):
14            return self.cache[n]
15        else:
16            # Compute and cache the requested Fibonacci number
17            fib_number = self(n - 1) + self(n - 2)
18            self.cache.append(fib_number)
19
20        return self.cache[n]

Ở đây, một sự cố về những gì mà xảy ra trong mã:

• Dòng 3 xác định 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 < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  5. defines the

   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 < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  5 class.

• Dòng 4 xác định trình khởi tạo 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 < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  6. Nó có một phương pháp đặc biệt mà bạn có thể sử dụng để khởi tạo các phiên bản lớp của mình. Các phương pháp đặc biệt đôi khi được gọi là các phương pháp Dunder, viết tắt cho các phương pháp nhấn mạnh gấp đôi. defines the class initializer,

   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 < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  6. It’s a special method that you can use to initialize your class instances. Special methods are sometimes referred to as dunder methods, short for double underscore methods.

• Dòng 5 tạo thuộc tính thể hiệ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 < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  7, có nghĩa là bất cứ khi nào bạn tạo đối tượng

   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 < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  5, sẽ có bộ đệm cho nó. Thuộc tính này ban đầu chứa các số đầu tiên trong chuỗi Fibonacci. creates the

   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 < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  7 instance attribute, which means that whenever you create a

   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 < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  5 object, there will be a cache for it. This attribute initially contains the first numbers in the Fibonacci sequence.

• Dòng 7 xác định một phương pháp đặc biệt khác,

   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 < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  9. Phương pháp này biến các phiên bản của

   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 < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  5 thành các đối tượng có thể gọi được. defines another special method,

   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 < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  9. This method turns the instances of

   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 < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  5 into callable objects.

• Dòng 9 và 10 xác nhận giá trị của n bằng cách sử dụng câu lệnh có điều kiện. Nếu n không phải là số nguyên dương, thì phương pháp này sẽ tăng

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

  3. validate the value of n by using a conditional statement. If n is not a positive integer number, then the method raises a

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

  3.

• Dòng 13 xác định 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 < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  7. Nếu số tại Index n đã 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 < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  7, thì dòng 14 sẽ trả về nó. Mặt khác, dòng 17 tính toán số và dòng 18 nối nó vào

   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 < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  7 để bạn không phải tính toán lại. defines a conditional statement to check for those Fibonacci numbers that were already calculated and are available in

   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 < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  7. If the number at index n is already in

   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 < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  7, then line 14 returns it. Otherwise, line 17 computes the number, and line 18 appends it to

   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 < len(self.cache):
  14            return self.cache[n]
  15        else:
  16            # Compute and cache the requested Fibonacci number
  17            fib_number = self(n - 1) + self(n - 2)
  18            self.cache.append(fib_number)
  19
  20        return self.cache[n]
  

  7 so you don’t have to compute it again.

• Dòng 20 Trả về số Fibonacci được yêu cầu. returns the requested Fibonacci number.

Để thử mã này, hãy tiếp tục và lưu nó vào

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

Tại đây, bạn tạo và sau đó 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 < len(self.cache):
14            return self.cache[n]
15        else:
16            # Compute and cache the requested Fibonacci number
17            fib_number = self(n - 1) + self(n - 2)
18            self.cache.append(fib_number)
19
20        return self.cache[n]

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

Việc triển khai thuật toán trình tự Fibonacci này khá hiệu quả. Khi bạn có một phiên bả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 < len(self.cache):
14            return self.cache[n]
15        else:
16            # Compute and cache the requested Fibonacci number
17            fib_number = self(n - 1) + self(n - 2)
18            self.cache.append(fib_number)
19
20        return self.cache[n]

Hình dung thuật toán trình tự Fibonacci đã ghi nhớ

Bạn có thể hiểu một cách hiệu quả mỗi cuộc gọi đến hàm Fibonacci đệ quy được xử lý bằng cách sử dụng biểu diễn ngăn xếp cuộc gọi. Cách mỗi cuộc gọi được đẩy lên ngăn xếp và bật ra phản ánh chính xác cách chương trình chạy. Nó thể hiện rõ ràng cách tính toán số lượng lớn sẽ mất nhiều thời gian nếu bạn không tối ưu hóa thuật toán.

Trong một ngăn xếp cuộc gọi, bất cứ khi nào một hàm trả về kết quả, một khung ngăn xếp biểu thị cuộc gọi hàm được bật ra khỏi ngăn xếp. Bất cứ khi nào bạn gọi một hàm, bạn thêm một khung ngăn xếp mới vào đầu ngăn xếp. Nói chung, hoạt động này có độ phức tạp không gian của O (N) vì không có nhiều hơn N khung ngăn xếp trên ngăn xếp cuộc gọi tại một thời điểm.

Để trực quan hóa thuật toán Fibonacci đệ quy đã ghi nhớ, bạn sẽ sử dụng một tập hợp các sơ đồ đại diện cho ngăn xếp cuộc gọi. Số bước được biểu thị bằng nhãn màu xanh bên dưới mỗi ngăn xếp cuộc gọi.

Nói rằng bạn muốn tính toán F (5). Để thực hiện việc này, bạn đẩy cuộc gọi đầu tiên đến chức năng vào ngăn xếp cuộc gọi:

Để tính toán F (5), bạn phải tính toán F (4) như được phác thảo bởi mối quan hệ tái phát Fibonacci, vì vậy bạn thêm cuộc gọi chức năng mới đó vào ngăn xếp:

Để tính toán F (4), bạn phải tính toán F (3), vì vậy bạn thêm một cuộc gọi chức năng khác vào ngăn xếp:

Để tính toán F (3), bạn phải tính toán F (2), do đó bạn thêm một cuộc gọi chức năng khác vào ngăn xếp cuộc gọi:

Để tính toán F (2), bạn phải tính toán F (1), vì vậy bạn thêm nó vào ngăn xếp. Vì F (1) là một trường hợp cơ sở, nó trở lại ngay lập tức với 1 và bạn xóa cuộc gọi này khỏi ngăn xếp:

Bây giờ bạn bắt đầu thư giãn kết quả đệ quy. F (1) Trả lại kết quả trở lại chức năng gọi của nó, F (2). Để tính toán F (2), bạn cũng cần tính toán F (0):

Bạn thêm f (0) vào ngăn xếp. Vì F (0) là một trường hợp cơ sở, nó trở lại ngay lập tức, cung cấp cho bạn 0. Bây giờ bạn có thể xóa nó khỏi ngăn xếp cuộc gọi:

Kết quả gọi F (0) này được trả lại cho F (2). Bây giờ bạn có những gì bạn cần tính toán F (2) và loại bỏ nó khỏi ngăn xếp:

Kết quả của F (2) được trả lại cho người gọi của nó, F (3). F (3) cũng cần kết quả của F (1) để hoàn thành tính toán của nó, do đó bạn thêm nó trở lại vào ngăn xếp:

F (1) là trường hợp cơ sở và giá trị của nó có sẵn trong bộ đệm, do đó bạn có thể trả lại kết quả ngay lập tức và xóa F (1) khỏi ngăn xếp:

Bạn có thể hoàn thành tính toán cho F (3), đó là 2:

Bạn xóa F (3) khỏi ngăn xếp sau khi hoàn thành tính toán của nó và trả lại kết quả cho người gọi của nó, F (4). F (4) cũng cần kết quả của F (2) để tính toán giá trị của nó:

Bạn đẩy cuộc gọi đến F (2) lên ngăn xếp. Đây là nơi bộ đệm tiện lợi xuất hiện. Bạn đã tính toán nó trước đây, vì vậy bạn chỉ có thể lấy giá trị từ bộ đệm, tránh một cuộc gọi đệ quy để tính toán kết quả của F (2). Bộ đệm trả về 1 và bạn xóa F (2) khỏi ngăn xếp:

F (2) được trả lại cho người gọi của nó và bây giờ F (4) có tất cả những gì nó cần để tính toán giá trị của nó, đó là 3:

Tiếp theo, bạn xóa F (4) khỏi ngăn xếp và trả lại kết quả của nó cho người gọi cuối cùng và nguyên bản, F (5):

F (5) hiện có kết quả của F (4) và cũng là kết quả của F (3). Bạn đẩy một cuộc gọi F (3) vào ngăn xếp và bộ đệm tiện lợi lại phát huy tác dụng. Trước đây bạn đã tính F (3), vì vậy tất cả những gì bạn cần làm là lấy nó từ bộ đệm. Không có quá trình đệ quy để tính toán F (3). Nó trả về 2 và bạn loại bỏ F (3) khỏi ngăn xếp:

Bây giờ F (5) có tất cả các giá trị cần thiết để tính toán giá trị của chính nó. Bạn nhận được 5 bằng cách thêm 3 và 2, và đó là bước cuối cùng trước khi bạn bật F (5) gọi ra khỏi ngăn xếp. Hành động này kết thúc chuỗi các cuộc gọi chức năng đệ quy của bạn:

Ngăn xếp cuộc gọi hiện đang trống. Bạn đã hoàn thành bước cuối cùng để tính toán F (5):

Đại diện cho các cuộc gọi chức năng đệ quy bằng sơ đồ ngăn xếp cuộc gọi giúp bạn hiểu tất cả các công việc diễn ra phía sau hậu trường. Nó cũng cho phép bạn xem có bao nhiêu tài nguyên một chức năng đệ quy có thể chiếm.

Đặt tất cả các sơ đồ này lại với nhau cho phép bạn hình dung toàn bộ quá trình trông như thế nào:

Bạn có thể nhấp vào hình ảnh ở trên để phóng to các bước riêng lẻ. Nếu bạn không có bộ đệm được tính toán trước đó, một số giai đoạn ngăn xếp trong sơ đồ này sẽ cao hơn, điều đó có nghĩa là họ sẽ mất nhiều thời gian hơn để trả về kết quả cho người gọi tương ứng.

Sử dụng phép lặp và chức năng Python

Ví dụ trong các phần trước thực hiện một giải pháp đệ quy sử dụng ghi nhớ như một chiến lược tối ưu hóa. Trong phần này, bạn sẽ mã hóa một hàm sử dụng lặp. Mã bên dưới thực hiện một phiên bản lặp của thuật toán trình tự Fibonacci của bạn:

 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

Bây giờ, thay vì sử dụng đệ quy trong fibonacci_of(), bạn đã sử dụng phép lặp. Việc triển khai thuật toán trình tự Fibonacci này chạy trong thời gian tuyến tính O (n). Ở đây, một sự cố của mã:

• Dòng 3 định nghĩa fibonacci_of(), có số nguyên dương, n, làm đối số. defines fibonacci_of(), which takes a positive integer, n, as an argument.

• Dòng 5 và 6 thực hiện xác thực thông thường của n. perform the usual validation of n.

• Dòng 9 và 10 xử lý các trường hợp cơ sở trong đó n là 0 hoặc 1. handle the base cases where n is either 0 or 1.

• Dòng 12 xác định hai biến cục bộ,

   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
  

  9 và

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

  0 và khởi tạo chúng với hai số đầu tiên trong chuỗi Fibonacci. defines two local variables,

   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
  

  9 and

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

  0, and initializes them with the first two numbers in the Fibonacci sequence.

• Dòng 13 bắt đầu một vòng

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

  1 lặp lại từ

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

  2 đến

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

  3. Vòng lặp sử dụng một dấu gạch dưới (

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

  4) cho biến vòng lặp vì nó là một biến vứt bỏ và bạn đã giành được giá trị này trong mã. starts a

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

  1 loop that iterates from

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

  2 to

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

  3. The loop uses an underscore (

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

  4) for the loop variable because it’s a throwaway variable and you won’t be using this value in the code.

• Dòng 15 tính toán số Fibonacci tiếp theo trong chuỗi và nhớ số trước. computes the next Fibonacci number in the sequence and remembers the previous one.

• Dòng 17 Trả về số Fibonacci được yêu cầu. returns the requested Fibonacci number.

Để thử mã này, hãy quay lại phiên tương tác của bạn và chạy mã sau:

>>>

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

Việc thực hiện fibonacci_of() này là khá tối thiểu. Nó sử dụng không bao gồm việc giải nén để tính toán các số fibonacci trong các vòng lặp, điều này khá hiệu quả. Tuy nhiên, mỗi khi bạn gọi hàm có giá trị khác nhau là n, nó phải tái tính trình tự một lần nữa. Để khắc phục điều này, bạn có thể sử dụng đóng cửa và làm cho chức năng của bạn nhớ các giá trị đã được tính toán giữa các cuộc gọi. Hãy tiếp tục và thử nó!iterable unpacking to compute the Fibonacci numbers during the loops, which is quite efficient memory-wise. However, every time you call the function with a different value of n, it has to recompute the sequence over again. To fix this, you can use closures and make your function remember the already computed values between calls. Go ahead and give it a try!