Dãy Fibonacci là một trong những dãy số nổi tiếng nhất trong toán học. Nó khá đơn giản để tính: mỗi số trong dãy là tổng của hai số trước đó.
Dãy này đã tìm đường vào lập trình. Thường được dùng để đào tạo lập trình viên về thuật toán và vòng lặp.
Trong hướng dẫn này, chúng ta sẽ nói về cách viết dãy Fibonacci trong Python. Chúng ta sẽ xem hai cách triển khai: lặp (iterative) và đệ quy (recursive).
Dãy Fibonacci là gì?
Dãy Fibonacci là một chuỗi số. Mỗi số là tích của hai số trước đó trong dãy. Dãy bắt đầu như sau:
0, 1, 1, 2, 3, 4, 8, 13, 21, 34
Nó tiếp tục mãi mãi cho đến khi bạn dừng tính số mới. Quy tắc tính số tiếp theo trong dãy là:
x(n) = x(n-1) + x(n-2)
x(n) là số tiếp theo trong dãy. x(n-1) là số hạng trước. x(n-2) là số hạng trước số cuối.
81% người tham gia cho biết họ cảm thấy tự tin hơn về cơ hội việc làm công nghệ sau khi tham gia bootcamp. Được ghép nối với bootcamp ngay hôm nay.
Sinh viên trung bình tốt nghiệp bootcamp mất chưa đến sáu tháng để chuyển đổi nghề nghiệp, từ khi bắt đầu bootcamp đến khi tìm được việc đầu tiên.
Dãy Fibonacci Python: Cách tiếp cận lặp (Iterative)
Hãy bắt đầu bằng cách lặp để triển khai dãy Fibonacci.
Cách này dùng vòng lặp "while" tính số tiếp theo trong danh sách cho đến khi điều kiện cụ thể được đáp ứng. Mỗi lần vòng lặp while chạy, mã của chúng ta lặp lại. Đó là lý do cách này gọi là lặp.
Hãy bắt đầu bằng thiết lập vài giá trị ban đầu:
terms_to_calculate = 9 n1, n2 = 0, 1 counted = 0
Chúng ta khai báo bốn biến.
Biến đầu tiên theo dõi số lượng giá trị chúng ta muốn tính. Hai biến tiếp theo, n1 và n2, là hai mục đầu tiên trong danh sách. Chúng ta cần nêu giá trị này nếu không chương trình không biết bắt đầu đâu. Các giá trị này sẽ thay đổi khi bắt đầu tính số mới.
Biến cuối theo dõi số hạng chúng ta đã tính trong chương trình Python.
Hãy viết vòng lặp tính số Fibonacci:
while counted < terms_to_calculate: print(n1) new_number = n1 + n2 n1 = n2 n2 = new_number counted += 1
Vòng lặp while chạy cho đến khi số giá trị đã tính bằng tổng số chúng ta muốn tính. Vòng lặp in giá trị n1 ra shell. Sau đó tính số tiếp theo bằng cách cộng số trước trong dãy với số trước đó.
Chúng ta hoán đổi giá trị n1 bằng n2. Điều này làm n1 thành số đầu tiên sau số mới. Sau đó đặt n2 bằng số mới. Tiếp theo, dùng toán tử += cộng 1 vào biến counted.
Mã trả về:
1
1
2
3
5
8
13
21
Chương trình đã tính thành công chín giá trị đầu trong dãy Fibonacci!
Dãy Fibonacci Python: Cách tiếp cận đệ quy (Recursive)
Tính dãy Fibonacci là trường hợp hoàn hảo cho đệ quy. Hàm đệ quy là hàm phụ thuộc vào chính nó để giải quyết vấn đề.
Hàm đệ quy chia vấn đề thành các vấn đề nhỏ hơn và dùng chính nó để giải quyết. Hãy bắt đầu bằng khởi tạo biến theo dõi số lượng số chúng ta muốn tính:
terms_to_calculate = 9
Chương trình này chỉ cần khởi tạo một biến. Tiếp theo, tạo hàm tính số tiếp theo trong dãy:
def calculate_number(number): if number <= 1: return number else: return(calculate_number(number-1) + calculate_number(number-2))
Hàm này kiểm tra số truyền vào có bằng hoặc nhỏ hơn 1 không. Nếu có, số đó trả về không tính toán. Ngược lại, gọi hàm calculate_number() hai lần để tính tổng hai mục trước trong danh sách.
Cuối cùng, viết chương trình chính thực thi hàm:
for number in range(terms_to_calculate): print(calculate_number(number))
Vòng lặp này thực thi số lần bằng giá trị terms_to_calculate. Nói cách khác, vòng lặp chạy 9 lần. Vòng lặp gọi phương thức calculate_number() để tính số tiếp theo trong dãy. In số này ra console.
Mã trả về:
1
1
2
3
5
8
13
21
Đầu ra từ mã này giống ví dụ trước.
Khác biệt nằm ở cách tiếp cận. Chúng ta định nghĩa hàm đệ quy gọi chính nó để tính số tiếp theo. Cách đệ quy thường ưu tiên hơn cách lặp vì dễ hiểu hơn.
Mã này dùng ít dòng hơn đáng kể so với ví dụ lặp. Thêm vào đó, chỉ cần khởi tạo một biến cho chương trình hoạt động; ví dụ lặp yêu cầu khởi tạo bốn biến.
Kết luận
Dãy Fibonacci có thể tạo bằng cách lặp hoặc đệ quy.
Cách lặp phụ thuộc vào vòng while để tính các số tiếp theo. Cách đệ quy liên quan đến định nghĩa hàm gọi chính nó để tính số tiếp theo.
Bây giờ bạn đã sẵn sàng tính dãy Fibonacci trong Python như chuyên gia!