Thông báo: Download 4 khóa học Python từ cơ bản đến nâng cao tại đây.
Dãy số Fibonacci trong Python
Trong bài viết này, bạn sẽ học cách định nghĩa một loại chuỗi (Sequence) tùy chỉnh trong Python và cách triển khai chuỗi Fibonacci bằng loại chuỗi tùy chỉnh này. Việc hiểu và tạo ra các loại chuỗi tùy chỉnh giúp bạn mở rộng khả năng lập trình và tối ưu hóa các thao tác trên dữ liệu. Chuỗi Fibonacci, với cấu trúc đơn giản nhưng mạnh mẽ, sẽ là ví dụ hoàn hảo để minh họa cho quá trình này. Bằng cách xây dựng một loại chuỗi tùy chỉnh cho Fibonacci, bạn sẽ nắm vững cách thức hoạt động của các phương thức quan trọng và cách áp dụng chúng vào các tình huống thực tế.
![banquyen png](https://freetuts.net/public/banquyen.png)
Giới thiệu về loại chuỗi tùy chỉnh trong Python
Đôi khi, việc triển khai một loại chuỗi tùy chỉnh có các chức năng tương tự như các loại chuỗi tích hợp sẵn như tuples và lists là rất hữu ích.
Như bạn đã học được cho đến nay, một chuỗi có thể là bất biến hoặc có thể thay đổi. Trong bài hướng dẫn này, bạn sẽ tập trung vào việc định nghĩa một loại chuỗi bất biến tùy chỉnh.
Về cơ bản, một loại chuỗi bất biến nên hỗ trợ hai chức năng chính:
Bài viết này được đăng tại [free tuts .net]
- Trả về số lượng phần tử của chuỗi. Về mặt kỹ thuật, yêu cầu này không cần thiết.
- Trả về một phần tử tại một chỉ số nhất định hoặc ném ra ngoại lệ
IndexError
nếu chỉ số vượt quá giới hạn.
Nếu một đối tượng có thể thực hiện các yêu cầu trên, thì bạn có thể:
- Sử dụng cú pháp ngoặc vuông
[]
để truy xuất một phần tử theo chỉ số. - Duyệt qua các phần tử của chuỗi bằng vòng lặp
for
, comprehension, v.v.
Về mặt kỹ thuật, một loại chuỗi tùy chỉnh cần triển khai các phương thức sau:
__getitem__
– trả về một phần tử tại một chỉ số nhất định.__len__
– trả về độ dài của chuỗi.
Phương thức __getitem__
Phương thức __getitem__
có tham số chỉ số là một số nguyên. __getitem__
nên trả về một phần tử từ chuỗi dựa trên chỉ số được chỉ định.
Phạm vi của chỉ số nên từ 0 đến độ dài - 1. Nếu chỉ số vượt quá giới hạn, phương thức __getitem__
nên ném ra ngoại lệ IndexError
.
Ngoài ra, phương thức __getitem__
có thể chấp nhận một đối tượng slice để hỗ trợ slicing.
Phương thức __len__
Nếu một chuỗi tùy chỉnh có phương thức __len__
, bạn có thể sử dụng hàm tích hợp len
để lấy số lượng phần tử từ chuỗi.
Giới thiệu về chuỗi Fibonacci trong Python
Chuỗi Fibonacci được phát hiện lần đầu tiên bởi Leonardo Fibonacci, một nhà toán học người Ý, vào khoảng năm 1170 sau Công nguyên.
Trong chuỗi Fibonacci, mỗi số là tổng của hai số đứng trước nó. Ví dụ:
1, 1, 2, 3, 5, 8, 13, 21, ...
Công thức sau mô tả chuỗi Fibonacci:
f(1) = 1 f(2) = 1 f(n) = f(n-1) + f(n-2) nếu n > 2
Một số nguồn tài liệu cho rằng chuỗi Fibonacci bắt đầu từ số 0, không phải 1 như sau:
0, 1, 1, 2, 3, 5, 8, 13, 21, ...
Nhưng chúng ta sẽ tuân theo chuỗi Fibonacci gốc bắt đầu từ số 1.
Để tính toán một số Fibonacci trong Python, bạn định nghĩa một hàm đệ quy như sau:
def fib(n): if n < 2: return 1 return fib(n-2) + fib(n-1)
Trong hàm đệ quy này, fib(1)
và fib(2)
luôn trả về 1. Và khi n
lớn hơn 2, fib(n) = fib(n-2) + fib(n-1)
.
Để thêm câu lệnh ghi log để debug trong hàm fib
, bạn có thể làm như sau:
def fib(n): print(f'Calculate Fibonacci of {n}') if n < 2: return 1 return fib(n-2) + fib(n-1)
Và đây là kết quả của hàm fib
khi tính toán Fibonacci của 6:
Calculate the Fibonacci of 6 Calculate the Fibonacci of 4 Calculate the Fibonacci of 2 Calculate the Fibonacci of 0 Calculate the Fibonacci of 1 Calculate the Fibonacci of 3 Calculate the Fibonacci of 1 Calculate the Fibonacci of 2 Calculate the Fibonacci of 0 Calculate the Fibonacci of 1 Calculate the Fibonacci of 5 Calculate the Fibonacci of 3 Calculate the Fibonacci of 1 Calculate the Fibonacci of 2 Calculate the Fibonacci of 0 Calculate the Fibonacci of 1 Calculate the Fibonacci of 4 Calculate the Fibonacci of 2 Calculate the Fibonacci of 0 Calculate the Fibonacci of 1 Calculate the Fibonacci of 3 Calculate the Fibonacci of 1 Calculate the Fibonacci of 2 Calculate the Fibonacci of 0 Calculate the Fibonacci of 1
Như rõ ràng từ đầu ra, hàm fib
có nhiều phép tính lặp lại. Ví dụ, nó phải tính Fibonacci của 3 ba lần. Điều này không hiệu quả.
Để giải quyết điều này, Python cung cấp một decorator gọi là lru_cache
từ module functools
.
lru_cache
cho phép bạn lưu trữ kết quả của một hàm. Khi bạn truyền cùng một đối số cho hàm, hàm chỉ cần lấy kết quả từ bộ nhớ đệm thay vì tính toán lại.
Dưới đây là cách sử dụng decorator lru_cache
để tăng tốc hàm fib
:
from functools import lru_cache @lru_cache def fib(n): print(f'Calculate the Fibonacci of {n}') if n < 2: return 1 return fib(n-2) + fib(n-1) fib(6)
Kết quả:
Calculate the Fibonacci of 6 Calculate the Fibonacci of 4 Calculate the Fibonacci of 2 Calculate the Fibonacci of 0 Calculate the Fibonacci of 1 Calculate the Fibonacci of 3 Calculate the Fibonacci of 5
Như rõ ràng từ đầu ra, số lượng phép tính đã giảm đáng kể.
Ví dụ về chuỗi Fibonacci trong Python
Đầu tiên, định nghĩa một lớp triển khai chuỗi Fibonacci:
class Fibonacci: def __init__(self, n): self.n = n
Phương thức __init__
nhận một số nguyên n
chỉ định độ dài của chuỗi.
Thứ hai, định nghĩa một phương thức tĩnh để tính toán một số Fibonacci của một số nguyên:
@staticmethod @lru_cache(2**16) def fib(n): if n < 2: return 1 return Fibonacci.fib(n-2) + Fibonacci.fib(n-1)
Thứ ba, triển khai phương thức __len__
để bạn có thể sử dụng hàm tích hợp len
để lấy số lượng phần tử từ chuỗi Fibonacci
def __len__(self): return self.n
Cuối cùng, triển khai phương thức __getitem__
để hỗ trợ việc truy xuất bằng cú pháp ngoặc vuông:
def __getitem__(self, index): if isinstance(index, int): if index < 0 hoặc index > self.n - 1: raise IndexError return Fibonacci.fib(index)
Phương thức __getitem__
nhận một chỉ số là một số nguyên. __getitem__
kiểm tra xem chỉ số có phải là số nguyên bằng cách sử dụng hàm isinstance
.
Phương thức __getitem__
ném ra ngoại lệ IndexError
nếu chỉ số vượt quá giới hạn. Nếu không, nó trả về số Fibonacci của chỉ số.
Đặt tất cả lại với nhau:
from functools import lru_cache class Fibonacci: def __init__(self, n): self.n = n def __len__(self): return self.n def __getitem__(self, index): if isinstance(index, int): if index < 0 hoặc index > self.n - 1: raise IndexError return Fibonacci.fib(index) @staticmethod @lru_cache(2**16) def fib(n): if n < 2: return 1 return Fibonacci.fib(n-2) + Fibonacci.fib(n-1)
Bây giờ, bạn có thể lưu lớp Fibonacci trong module fibonacci.py
và sử dụng nó trong một script mới.
Sử dụng chuỗi Fibonacci trong Python
Dưới đây là cách sử dụng chuỗi Fibonacci từ module fibonacci
:
from fibonacci import Fibonacci fibonacci = Fibonacci(10) # truy xuất các phần tử qua chỉ số print('Truy xuất chuỗi Fibonacci bằng ngoặc vuông []:') print(fibonacci[0]) print(fibonacci[1]) print(fibonacci[2]) print('Truy xuất chuỗi Fibonacci bằng vòng lặp for:') # sử dụng vòng lặp for for f in fibonacci: print(f)
Kết quả:
Truy xuất chuỗi Fibonacci bằng ngoặc vuông []: 1 1 2 Truy xuất chuỗi Fibonacci bằng vòng lặp for: 1 1 2 3 5 8 13 21 34 55
Cách hoạt động:
- Tạo một instance mới của chuỗi Fibonacci chứa 10 phần tử.
- Truy xuất các phần tử của chuỗi Fibonacci bằng ngoặc vuông
[]
. - Sử dụng chuỗi Fibonacci trong vòng lặp for.
Thêm hỗ trợ slicing
Để hỗ trợ slicing như sau:
fibonacci[1:5]
...bạn cần thêm logic để xử lý đối tượng slice.
Trong fibonacci[1:5]
, đối số index
của phương thức __getitem__
là một đối tượng slice có start
là 1 và stop
là 5.
Và bạn có thể sử dụng phương thức indices
của đối tượng slice để lấy các chỉ số của các phần tử sẽ được trả về từ chuỗi:
indices = index.indices(self.n)
self.n
là độ dài của chuỗi sẽ được slice. Trong trường hợp này, đó là số lượng phần tử trong chuỗi Fibonacci.
Để trả về một danh sách các số Fibonacci từ slice, bạn có thể truyền các chỉ số vào hàm range
và sử dụng list comprehension như sau:
[Fibonacci.fib(k) for k in range(*indices)]
Dưới đây là phiên bản mới của chuỗi Fibonacci hỗ trợ slicing:
from functools import lru_cache class Fibonacci: def __init__(self, n): self.n = n def __len__(self): return self.n def __getitem__(self, index): if isinstance(index, int): if index < 0 hoặc index > self.n - 1: raise IndexError return Fibonacci.fib(index) else: indices = index.indices(self.n) return [Fibonacci.fib(k) for k in range(*indices)] @staticmethod @lru_cache def fib(n): if n < 2: return 1 return Fibonacci.fib(n-2) + Fibonacci.fib(n-1)
Bây giờ, bạn có thể slice chuỗi Fibonacci như sau:
from fibonacci import Fibonacci fibonacci = Fibonacci(10) print(fibonacci[1:5])
Kết quả:
[1, 2, 3, 5]
Kết bài
Triển khai phương thức __len__
và __getitem__
để định nghĩa một chuỗi tùy chỉnh là bước quan trọng trong việc tạo ra các loại chuỗi mạnh mẽ và linh hoạt trong Python. Phương thức __len__
cho phép bạn sử dụng hàm len()
để lấy số lượng phần tử trong chuỗi, trong khi phương thức __getitem__
giúp truy xuất phần tử theo chỉ số hoặc ném ra ngoại lệ IndexError
nếu chỉ số vượt quá giới hạn. Bằng cách nắm vững cách triển khai hai phương thức này, bạn có thể dễ dàng xây dựng các loại chuỗi tùy chỉnh phù hợp với nhu cầu cụ thể của mình, tối ưu hóa các thao tác trên dữ liệu và làm cho mã nguồn của bạn trở nên hiệu quả hơn.