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