Dãy Fibonacci [Bài tập Python]

14796

Bài viết được sự cho phép của tác giả Khiêm Lê

Dãy Fibonacci

Dãy Fibonacci là một dãy vô hạn các số tự nhiên, bắt đầu dãy là hai phần tử 1, các phần tử sau đó là tổng của hai phần tử trước đó. Công thức truy hồi của số dãy Fibonacci là:

  • Nếu n = 1 hoặc n = 2
    • F(n) := 1
  • Nếu n > 2
    • F(n) := F(n – 1) + F(n – 2)

Trong lập trình, bài toán tĩnh dãy Fibonacci thường được dùng để làm quen với đệ quy hoặc quy hoạch động cơ bản. Trước khi bắt đầu cài đặt thuật toán, hãy chắc chắn rằng bạn đã biết cơ bản về python, còn bây giờ thì bắt đầu thôi.

Lưu ý: trong bài viết mình có đề cập đến thời gian thực thi, thời gian này chỉ để tham khảo, thời gian thực thi sẽ luôn sai khác do cấu hình mỗi máy là khác nhau.

Việc làm lập trình Python tuyển gấp

Đệ quy

Theo như khái niệm về dãy Fibonacci, chúng ta sẽ có 2 trường hợp cơ sở (base case) là n = 1 và n = 2, lúc đó F(n) := 1, đây chính là điều kiện dừng cho hàm đệ quy của chúng ta.

Ngược lại đối với n > 2, lúc này F(n) := F(n – 1) + F(n – 2), F(n – 1) và F(n – 2) chính là phần gọi lại chính hàm F(n) với n lúc này là n – 1 và n – 2, hay chính là phương thức đệ quy. Vậy chúng ta sẽ có đoạn code sau:

def F(n):
    if n == 1 or n == 2: # base case
        return 1
    return F(n - 1) + F(n - 2) # recursion

Giờ hãy cùng xem hàm tính số Fibonacci của chúng ta hoạt động như thế nào nha!

print(F(5)) # 5, mất 0.1s
print(F(15)) # 610, mất 0.1s
print(F(35)) # 9227465, mất 3.9s
print(F(40)) # 102334155, mất 42.9s

Bạn có nhận thấy là thời gian thực thi khi của F(35) mất 3.9s nhưng của F(40) lại đến 42.9s mặc dù n chỉ cách nhau có 5 đơn vị. Hãy nhìn vào đồ thị sau:

Dãy Fibonacci [Bài tập Python]
Đồ thị đệ quy của hàm F(5)

Bạn có thể dễ dàng nhận thấy là các hàm với n giống nhau được lặp lại nhiều lần, F(3) 2 lần, F(2) 3 lần và F(1) 2 lần. Đây chỉ mới là tính F(5) thôi, nếu bạn tĩnh các số lớn hơn thì hãy tưởng tượng có bao nhiều hàm với tham số trùng nhau được lặp lại. Đây chính là nhược điểm của thuật toán trên, vậy chúng ta xử lý vấn đề đó như thế nào?

  Tuple Python là gì? Tìm hiểu về tuple python

Quy hoạch động

Để xử lý vấn đề trên, cách tốt nhất là xử dụng quy hoạch động (dynamic programming). Như đã giải thích ở trên, các hàm tính số Fibonacci với tham số n trùng nhau bị gọi lặp lại nhiều lần, vậy nên chúng ta sẽ lưu chúng lại và sử dụng cho lần khác (memoize).

Thuật toán được đưa ra là chúng ta sẽ dùng một mảng lưu lại các giá trị của hàm F(n), nếu như phần tử n có tồn tại giá trị trong mảng thì ta sử dụng luôn mà không cần tính toán lại giá trị. Ngược lại thì tính F(n – 1) + F(n – 2) và lưu nó vào mảng, sau đó trả về giá trị vừa tính.

Chúng ta sẽ không gọi trực tiếp hàm tính số Fibonacci với chiến lược quy hoạch động mà thông qua một hàm khác, hàm này có chức năng tạo mảng gồm n + 1 phần tử, sau đó gọi hàm tính số Fibonacci thực sự với tham số là n và mảng vừa tạo.

Với ý tưởng trên, chúng ta sẽ có thuật toán như sau:

def F_memo(n, memo):
    if n == 1 or n == 2: # base case
        return 1
    if not memo[n] == None: # kiểm tra có tồn tại giá trị của F(n) trong mảng không
    	return memo[n]
    result = F_memo(n - 1, memo) + F_memo(n - 2, memo) # gọi đệ quy và lưu vào biến result
    memo[n] = result # thêm F(n) vào mảng
    return result


def F(n):
	memo = [None] * (n + 1) # tạo mảng n + 1 phần tử có giá trị None
	return F_memo(n, memo)

Giờ hãy cùng thử xem thời gian thực thi có được cải thiện hay không, hãy cùng bắt đầu với F(40) ban nãy.

print(F(40)) # 102334155, mất 0.1s

Với F(40), ban đầu thực thi đến 42.9s nhưng sau khi dùng quy hoạch động thì chỉ còn 0.1s, thực sự rất hiệu quả. Giờ hãy cùng test với những bộ test lớn hơn xem như thế nào.

print(F(100)) # 354224848179261915075, mất 0.1s
print(F(995))
# 3919377061614427623668052985592742430389065042819420493170692719480242247392252775480208752179017313071371501566248877239254299341332131655760767122899079117071192049598939666199865808814650408864891823186505
# F(995) mất 0.1s

Bạn thấy là thậm chí chúng ta đã có thể tính đến F(995), kết quả là một con số cực kỳ lớn nhưng cũng chỉ mất 0.1s để thực thi. Tuy nhiên, vấn đề xảy ra khi bạn tính với n > 1000, bạn sẽ nhận được một thông báo lỗi là “RecursionError: maximum recursion depth exceeded in comparison”. Lỗi RecursionError xảy ra khi bạn thực hiện đệ quy quá sâu.

Để tính F(995), bạn phải gọi đệ quy tính F(994), F(993), … F(2), F(1), sau đó mới truy hồi ngược lên, nghĩa là phải gọi đến 1000 lần hàm F(n), sau đó truy hồi lên thì ta mới có được kết quả. Điều này làm giảm đáng kể hiệu suất của chương trình. Vậy làm sao để tối ưu thuật toán này hơn nữa?

  Python: Tạo một máy chủ HTTP đơn giản

Bottom-Up approach

Bottom-Up approach hay tiếp cận từ dưới lên sẽ giải quyết được vấn đề đệ quy sâu. Từ khái niệm “các phần tử sau đó là tổng của hai phần tử trước đó”, cùng với công thức truy hồi, ta sẽ lập được thuật toán theo cách Bottom-Up. Theo như đồ thị của hàm đệ quy, thay vì tính từ đỉnh của đồ thị là F(5) đi xuống, ta sẽ tính từ các phần tử cuối đồ thị tính dần lên trên, tức là tính F(1), F(2) … F(n).

Ta sẽ sử dụng một mảng để lưu trữ giá trị F(n), với base case là n = 1 và n = 2, ta sẽ gán phần tử thứ nhất và hai của mảng bằng 1. Tiếp theo, chúng ta cho một biến chạy từ 3 đến n, phần tử thứ i của mảng sẽ bằng hai phần tử trước đó cộng lại, tức là phần tử i – 1 và i – 2. Kết quả cuối cùng, phần tử thứ n chính là kết quả F(n) cần tìm, chúng ta sẽ có thuật toán sau:

def F_bottom_up(n, memo):
	if n == 1 or n == 2:
		return 1
	memo[1] = 1
	memo[2] = 1
	for i in range(3, n + 1):
		memo[i] = memo[i - 1] + memo[i - 2]
	return memo[n]


def F(n):
	memo = [None] * (n + 1)
	return F_bottom_up(n, memo)

Giờ hãy cùng thử xem, với n = 1000, thuật toán của chúng ta có thực thi được không và hiệu suất như thế nào nhé. Do kết quả quá dài nên mình sẽ không tiện ghi kết quả ra, mình sẽ chỉ ghi thời gian thực thi.

print(F(1000)) # mất 0.1s
print(F(10000)) # mất 0.1s
print(F(100000)) # mất 2.0s
print(F(150000)) # mất 4.1s
print(F(200000)) # mất 15.8s

So với lúc đầu, tính F(40) mà đã mất 42.9s, giờ đây chúng ta đã có thể tính lên đến F(200000) mà chỉ mất có 15.8s. Vậy là thuật toán mình cài đặt thực sự có hiệu suất rất cao.

Tổng kết

Vậy là trong bài viết này, mình đã giới thiệu đến các bạn về dãy Fibonacci, thuật toán tính số Fibonacci sử dụng ngôn ngữ Python, tối ưu thuật toán. Nếu bạn có thuật toán hay, đừng ngại chia sẻ nó bằng cách comment bên dưới bài viết. Đừng quên chia sẻ bài viết với bạn bè nha. Cảm ơn các bạn đã theo dõi bài viết!

Bài viết gốc được đăng tải tại khiemle.dev

Xem thêm các việc làm ngành cntt hấp dẫn tại TopDev

RELATED ARTICLESMORE FROM AUTHOR