Dãy Fibonacci trong Python: Tìm hiểu và khám phá kỹ thuật mã hóa

Dãy Fibonacci là một cách thú vị để bạn tiếp tục luyện tập Python. Trong bài viết này, bạn sẽ học cách triển khai dãy Fibonacci trong Python bằng nhiều kỹ thuật khác nhau, từ viết hàm hiệu quả và xử lý đệ quy đến áp dụng nguyên tắc hướng đối tượng cho các lời giải tối ưu hơn. 

Khi đọc xong, hãy học khóa Writing Functions in Python của chúng tôi để củng cố các khái niệm như phạm vi biến và xử lý lỗi, hoặc thử khóa Intermediate Object-Oriented Programming in Python để tìm hiểu về kế thừa và lớp cơ sở. Giờ thì hãy thử dãy Fibonacci nhé.

Câu trả lời nhanh

Dãy Fibonacci bắt đầu với 0 và 1, mỗi số là tổng của hai số liền trước. Cách đơn giản nhất để sinh dãy trong Python là dùng vòng lặp:

n = 10
a, b = 0, 1

fibonacci_numbers = []

for _ in range(n):  
    fibonacci_numbers.append(str(a)) 
    a, b = b, a + b

print(' '.join(fibonacci_numbers))

# This prints the first 10 Fibonacci numbers
# 0 1 1 2 3 5 8 13 21 34Được hỗ trợ bởi

Dãy Fibonacci là gì?

Dãy Fibonacci là một khái niệm toán học xuất hiện trong nhiều lĩnh vực khoa học và tự nhiên. Đây là một dãy số trong đó mỗi số là tổng của hai số đứng trước, bắt đầu với 0 và 1. Mẫu hình này là nền tảng cho các ứng dụng trong các lĩnh vực như khoa học máy tính và tài chính. 

Hai khía cạnh chính định nghĩa dãy Fibonacci: cấu trúc đệ quy của dãy và mối liên hệ của nó với tỷ lệ vàng.

Tính đệ quy của dãy Fibonacci

Dãy Fibonacci bắt đầu với 0 và 1. Mỗi số mới là tổng của hai số trước đó. Ví dụ:

0 + 1 = 1

1 + 1 = 2

1 + 2 = 3

2 + 3 = 5

3 + 5 = 8

5 + 8 = 13

Và cứ thế tiếp tục. 

Về mặt toán học, ta viết là F(n) = F(n-1) + F(n-2). Dãy tự xây dựng bằng cách liên tục cộng hai số cuối. Hai số đầu tiên, 0 và 1, là điểm khởi đầu hay trường hợp cơ sở. Không có chúng, dãy sẽ không hoạt động.

Mẫu hình đệ quy này là nền tảng cho một số thuật toán trong khoa học máy tính. Ví dụ, đệ quy trong lập trình vận hành trên dãy này khi giải các bài toán như sinh số Fibonacci hoặc chia nhỏ tác vụ thành các phần dễ quản lý hơn.

Mối liên hệ với tỷ lệ vàng 

Dãy Fibonacci gắn liền với tỷ lệ vàng, một số vô tỉ ký hiệu là φ (giá trị xấp xỉ 1,618). Nếu bạn chia một số Fibonacci cho số đứng trước nó, tỉ số sẽ tiến gần dần tới φ. Ví dụ:

5 ÷ 3 ≈ 1,666

8 ÷ 5 ≈ 1,6

13 ÷ 8 ≈ 1,625

Càng đi xa, tỉ số càng gần 1,618. Đây không phải ngẫu nhiên — tỉ lệ này xuất hiện tự nhiên trong dãy Fibonacci do cách các số tăng trưởng.

Euclid đã mô tả nó đầu tiên ở Hy Lạp cổ đại như tỉ số cực hạn và trung bình. Kể từ đó, nó được liên hệ với các mẫu hình trong tự nhiên, như các xoắn ốc ở vỏ sò và hoa, cũng như trong nghệ thuật và kiến trúc.

Tỷ lệ vàng trong nghệ thuật. Nguồn

Ứng dụng thực tiễn của dãy Fibonacci

Dãy Fibonacci xuất hiện theo những cách bất ngờ ở nhiều lĩnh vực. Hãy tập trung vào hai ứng dụng đáng chú ý: các mẫu hình trong tự nhiên và việc sử dụng trong khoa học máy tính.

Fibonacci trong tự nhiên

Bạn có thể thấy dãy Fibonacci ở khắp tự nhiên. Hãy nhìn các bông hoa — số cánh hoa thường khớp với các số Fibonacci. Ví dụ, cúc có thể có 34, 55 hoặc 89 cánh, và loa kèn thường có 3, 5 hoặc 8. Những mẫu hình này giúp cây cối phát triển theo cách tối đa hóa ánh sáng mặt trời và lượng mưa.

Các xoắn ốc ở nón thông và hướng dương cũng tuân theo số Fibonacci. Chẳng hạn, cách sắp xếp hạt của hoa hướng dương khớp với dãy. Thật thú vị khi điều đơn giản như cộng hai số lại có thể mô tả rất nhiều trong thế giới tự nhiên.

Fibonacci trong khoa học máy tính

Dãy Fibonacci cũng đóng vai trò quan trọng trong thuật toán và cấu trúc dữ liệu. Ví dụ, các số Fibonacci được dùng trong thuật toán tìm kiếm để phân rã bài toán thành các phần nhỏ hiệu quả. Dãy này thậm chí đứng sau Fibonacci heap, một loại cấu trúc dữ liệu dùng để tăng tốc một số thao tác như tìm đường đi ngắn nhất trong mạng.

Dưới đây là ví dụ đơn giản về cách bạn có thể sinh dãy Fibonacci trong Python:

def fibonacci(n):
	if n <= 1:
		return n
	return fibonacci(n - 1) + fibonacci(n - 2)

# Example usage
fibonacci_numbers = []

for i in range(10):
	fibonacci_numbers.append(str(fibonacci(i)))

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34Được hỗ trợ bởi

Hàm đệ quy này cho thấy cách dãy Fibonacci được xây dựng. Dù đệ quy dễ hiểu, cũng có các phiên bản tối ưu như lập trình động để tính số Fibonacci nhanh hơn nhiều.

Trong mật mã học, số Fibonacci có thể giúp tạo khóa an toàn. Còn trong trí tuệ nhân tạo, chúng tối ưu hóa mạng nơ-ron để cải thiện cách thuật toán học và thích nghi. 

Những ví dụ phổ biến khác

Dưới đây là một vài ví dụ nữa về cách dãy này xuất hiện trong đời sống hằng ngày và các lĩnh vực chuyên sâu:

• Trong Nghệ thuật: Dãy Fibonacci đã được nghệ sĩ và kiến trúc sư sử dụng suốt nhiều thế kỷ. Những công trình nổi tiếng như đền Parthenon mang các tỷ lệ này vì chúng tự nhiên gây cảm giác dễ chịu cho mắt.
• Trong Âm nhạc: Các nhà soạn nhạc dùng số Fibonacci để tạo nhịp điệu và giai điệu. Ví dụ, họ gán nốt tròn cho 1, nốt trắng cho 2 và nốt đen cho 3 để tạo mẫu hình hài hòa.
• Trong Giao dịch: Nhà giao dịch cổ phiếu áp dụng số Fibonacci để phân tích xu hướng thị trường. Họ dùng chúng để dự đoán các mức giá tiềm năng nơi cổ phiếu có thể đảo chiều, giúp quyết định khi nào mua hoặc bán.
• Trong Vật lý: Trong vật lý lượng tử, các mẫu hình Fibonacci đã được quan sát trong tương tác và hành vi của hạt, cho thấy dãy này xuất hiện ngay cả ở những thang bậc nhỏ nhất của tự nhiên.

Triển khai dãy Fibonacci trong Python

Vì Python có nhiều cách để sinh dãy Fibonacci, tôi đã trình bày từng bước các cách dùng phổ biến nhất kèm ví dụ.

Dùng phương pháp lặp

Phương pháp lặp là một trong những cách đơn giản nhất để sinh dãy Fibonacci. Nó dùng vòng lặp để tính mỗi hạng, nhờ đó tiết kiệm bộ nhớ hơn so với đệ quy. Cách hoạt động như sau:

Tôi đặt hai biến a và b thành 0 và 1. Đây là hai số đầu của dãy. Sau đó, tôi dùng vòng lặp for để tính các số tiếp theo. Tôi cập nhật a để giữ giá trị của b, và b trở thành tổng của a và b trước đó.

Dưới đây là mã Python cho cách này:

n = 10
a, b = 0, 1

fibonacci_numbers = []

for _ in range(n):
    fibonacci_numbers.append(str(a))
    a, b = b, a + b

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34Được hỗ trợ bởi

Nếu bạn muốn dùng vòng lặp while thay vì for, có thể viết như sau:

# Number of terms to print in the Fibonacci series
n = 10

# Initialize the first two terms
a, b = 0, 1
i = 0

fibonacci_numbers = []

while i < n:
	fibonacci_numbers.append(str(a))
	# Update the terms
	a, b = b, a + b
	i += 1

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34Được hỗ trợ bởi

Cả hai cách đều rất dễ hiểu, phù hợp cho người mới bắt đầu. 

Dùng phương pháp đệ quy

Phương pháp đệ quy là một cách khác để sinh số Fibonacci. Nó không nhanh bằng phương pháp lặp với dãy dài, nhưng rất tốt để hiểu logic cách dãy được xây dựng.

Ví dụ, tôi tạo hàm fibonacci_recursive. Hàm này nhận một số n. Nếu n là 0 hoặc 1, hàm trả về n. Đây là các trường hợp cơ sở để dừng đệ quy. Với số khác, hàm tự gọi để tính hai số trước rồi cộng lại.

Mã cho cách này như sau:

def fibonacci_recursive(n):
	if n <= 1:
		return n
	else:
		return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

num_terms = 10
fibonacci_numbers = []
for i in range(num_terms):
	fibonacci_numbers.append(str(fibonacci_recursive(i)))

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34Được hỗ trợ bởi

Cách này hoạt động tốt với dãy ngắn nhưng có thể chậm khi dãy dài vì tính lại cùng giá trị nhiều lần.

Dùng đệ quy tối ưu với bộ nhớ đệm

Để khắc phục sự kém hiệu quả của đệ quy thuần, tôi thường dùng bộ nhớ đệm. lru_cache của Python lưu các giá trị đã tính để hàm không phải làm lại.

Tôi làm như sau:

from functools import lru_cache

@lru_cache(maxsize = None)
def fib_cache(n):
    if n == 0:
        return 0  
    elif n == 1:
        return 1
    else:
        return fib_cache(n-1) + fib_cache(n-2)

print(f"The Fibonacci Number is {fib_cache(10)}")

# The Fibonacci Number is 55Được hỗ trợ bởi

Cách tiếp cận này kết hợp sự dễ hiểu của đệ quy với hiệu năng của bộ nhớ đệm.

Những cách nâng cao hơn để làm dãy Fibonacci trong Python

Nếu bạn muốn các cách khác để tính số Fibonacci, dưới đây là vài kỹ thuật nâng cao:

Lũy thừa ma trận

Lũy thừa ma trận là một trong những cách hiệu quả nhất để tính số Fibonacci khi n lớn. Thay vì tính lặp lại các hạng, phương pháp này dùng nhân ma trận để cho kết quả trong thời gian theo logarit.

Tôi đã triển khai trong Python như sau:

import numpy as np

def fibonacci_matrix(n):
	def matrix_power(matrix, power):
		return np.linalg.matrix_power(matrix, power)
	if n == 0:
		return 0
	matrix = np.array([[1, 1], [1, 0]])
	result = matrix_power(matrix, n-1)
	return result[0][0]

fibonacci_numbers = []

for i in range(10):
	fibonacci_numbers.append(str(fibonacci_matrix(i)))

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34Được hỗ trợ bởi

Trong đoạn mã này, nếu n là 0, nó trả về 0 như trường hợp cơ sở. Với giá trị khác, ma trận được lũy thừa (n-1) bằng hàm matrix_power của numpy. Số Fibonacci tại vị trí n nằm ở phần tử góc trên bên trái của ma trận kết quả.

Công thức Binet

Công thức Binet tính trực tiếp số Fibonacci thứ n mà không cần lặp hay đệ quy. Nó dựa trên tỷ lệ vàng φ và dùng biểu thức toán học để cho kết quả tức thì.

Công thức là:

Trong đó:

• φ = (1 + √5) / 2​​, tỷ lệ vàng.
• 1 - φ là liên hợp của φ.

Đây là mã Python cho công thức Binet:

import math

def fibonacci_binet(n):
    phi = (1 + math.sqrt(5)) / 2
    return round((phi ** n - (1 - phi) ** n) / math.sqrt(5))

# Find the 10th Fibonacci number
n = 10
result = fibonacci_binet(n)
print(f"The Fibonacci Number of {n}th term is {result}" )

# The Fibonacci Number of 10th term is 55Được hỗ trợ bởi

Trong đoạn mã này, hàm fibonacci_binet(n) tính số Fibonacci thứ n bằng công thức Binet. Bên trong hàm, tôi tính phi (tỷ lệ vàng) là (1 + math.sqrt(5)) / 2, dùng math.sqrt() để lấy căn bậc hai của 5. Sau đó áp dụng công thức (phi ** n - (1 - phi) ** n) / math.sqrt(5) để tìm trực tiếp số Fibonacci thứ n. Cuối cùng, tôi dùng hàm round() để xử lý các sai số dấu phẩy động nhỏ.

Mảng

Bạn thậm chí có thể dùng mảng để sinh và lưu toàn bộ dãy Fibonacci. Điều này hữu ích khi bạn cần nhiều hạng cùng lúc.

Mã cho cách này như sau:

def fibonacci(n):
    if n <= 0:
        return "Incorrect Output"
    data = [0, 1]  # Initialize list with first two Fibonacci terms: 0 and 1
    if n > 2:
        for i in range(2, n):  # Start loop from the third term
            data.append(data[i-1] + data[i-2])  # Calculate next term as sum of previous two
    return data[n-1]  # Return the nth term

print(f"Fibonacci Number: {fibonacci(10)}")

# Fibonacci Number: 34Được hỗ trợ bởi

Backtracking

Backtracking là một lựa chọn khác tôi có thể dùng, đặc biệt khi tôi muốn kết hợp đệ quy với ghi nhớ (memoization) để có hiệu năng tốt hơn.

Mã cho cách này như sau:

def fibonacci_backtracking(n, computed ={0: 0, 1: 1}):
    if n in computed:
        return computed[n]
    computed[n] = fibonacci_backtracking(n - 1) + fibonacci_backtracking(n - 2)
    return computed[n]

n = 10
result = fibonacci_backtracking(n)
print(f"The {n}th Fibonacci term is {result}")

# The 10th Fibonacci term is 55Được hỗ trợ bởi

Độ phức tạp của các thuật toán Fibonacci trong Python

Chúng ta đã đi qua khá nhiều ví dụ! Giờ hãy xem sự khác nhau của chúng về thời gian và không gian tính toán. Như đã đề cập, một số phương pháp nhanh nhưng tốn bộ nhớ, trong khi những cách khác chậm hơn nhưng cần ít bộ nhớ hơn. Tôi đã chuẩn bị bảng sau để so sánh hiệu quả của từng cách tiếp cận.

Trong bảng trên, ý nghĩa của từng độ phức tạp thời gian và không gian như sau:

Độ phức tạp thời gian

• O(n): Thuật toán duyệt qua dãy một lần bằng cách thực hiện số thao tác cố định cho mỗi phần tử. Thời gian chạy tăng tuyến tính theo kích thước đầu vào n.

• O(1): Số Fibonacci được tính bằng số thao tác cố định, không cần lặp hay đệ quy.

• O(2ⁿ): Thuật toán thực hiện hai lời gọi đệ quy cho mỗi đầu vào, dẫn đến số lượng lời gọi hàm tăng theo hàm mũ khi n tăng.

• O(log n): Thời gian chạy tăng theo logarit của kích thước đầu vào n.

Độ phức tạp không gian

• O(n): Thuật toán dùng bộ nhớ tăng trực tiếp theo số lượng đầu vào n. Ở đây, mỗi phần tử cần một lượng không gian cố định.

• O(1): Mức dùng bộ nhớ không đổi bất kể kích thước đầu vào.

• O(2ⁿ): Dùng bộ nhớ theo hàm mũ do tạo trạng thái mới cho mỗi nhánh.

• O(log n): Các phép nhân ma trận trung gian dùng bộ nhớ theo logarit.

Kết luận

Như bạn đã thấy, trong Python, bạn có thể tính số Fibonacci bằng nhiều phương pháp khác nhau, từ vòng lặp đơn giản đến các kỹ thuật nâng cao như lũy thừa ma trận và công thức Binet. Mỗi phương pháp đều có ưu điểm và đánh đổi riêng.

Hy vọng bạn đã học thêm điều gì đó về dãy Fibonacci cũng như về lập trình Python. Nếu muốn khám phá thêm về Python và các chủ đề liên quan, hãy xem khóa Introduction to Python của chúng tôi. Bạn cũng có thể thử lộ trình nghề nghiệp đầy đủ Python Developer và học các kỹ thuật lập trình, thậm chí bắt đầu phát triển gói của riêng bạn!