Số Fibonacci bằng ngôn ngữ Python

Số Fibonacci là một dãy cụ thể trong đó giá trị đầu tiên được khai báo trước là 0 và giá trị thứ hai được khai báo trước là 1. Phần còn lại của các số được tạo ra từ hai số này bằng cách cộng hai số trước đó. Tất cả các số Fibonacci đều là số nguyên dương, bắt đầu từ 0. Mười hai số Fibonacci đầu tiên và cách lấy chúng như sau:

0
1
1 + 0 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
13 + 8 = 21
21 + 13 = 34
34 + 21 = 55
55 + 34 = 89

Nếu không có biểu thức tổng, các số Fibonacci này có thể được đặt trong một bảng như sau:

Hàng đầu tiên có các số Fibonacci. Hàng thứ hai có các chỉ mục dựa trên 0, giả sử rằng các số Fibonacci nằm trong một mảng.

Số Fibonacci có thể được tạo ra trong thời gian O (n) và trong thời gian O (1). Trong các biểu thức độ phức tạp thời gian này, n có nghĩa là n hoạt động chính và 1 có nghĩa là 1 hoạt động chính. Với O (n), n số Fibonacci được tạo ra, bắt đầu từ 0. Với O (1), một số Fibonacci được tạo ra từ một chỉ số tương ứng. Đó là lý do tại sao nó chỉ cần một hoạt động chính thay vì n hoạt động chính.

Mục đích của bài viết này là giải thích cách tạo số Fibonacci, bằng cách sử dụng Python.

Công thức cho một số Fibonacci

Định nghĩa chính thức của số Fibonacci là:

nơi F _N là số Fibonacci ở chỉ số n

Sản xuất số Fibonacci trong thời gian O (n)

Nếu n là 1, thì chỉ có 0 được in dưới dạng số Fibonacci. Nếu n là 2, thì 0 và 1 sẽ được in dưới dạng số Fibonacci, theo thứ tự đó. Nếu n là 3, thì 0, 1 và 1 sẽ được in dưới dạng số Fibonacci theo thứ tự đó. Nếu n là 4, thì 0, 1, 1 và 2 sẽ được in dưới dạng số Fibonacci theo thứ tự đó. Nếu n là 5, thì 0, 1, 1, 2 và 3 sẽ được in dưới dạng số Fibonacci, theo thứ tự đó. Nếu n là 6, thì 0, 1, 1, 2, 3 và 5 sẽ được in dưới dạng số Fibonacci, theo thứ tự đó - và cứ tiếp tục như vậy.

Hàm Python để tạo ra n số Fibonacci đầu tiên là:

Nó bắt đầu bằng cách tạo một mảng gồm n phần tử, tất cả đều được khởi tạo bằng số 0. Mảng này sẽ chứa các số Fibonacci. Số Fibonacci đầu tiên, 0, đã ở đó. Số Fibonacci thứ hai, 1, được gán bởi câu lệnh tiếp theo (trong hàm). Sau đó là vòng lặp for, bắt đầu từ chỉ số 2 đến ngay trước n. Nó có tuyên bố:

Điều này thêm hai số trước đó ngay lập tức.

Mã để gọi hàm và in ra mười hai số Fibonacci đầu tiên có thể là:

N = 12
A = fibonacci (N)
đối với tôi trong phạm vi (N):
print (A [i], end = ’‘)
in()

Đầu ra là:

Sản xuất một số Fibonacci trong thời gian không đổi

Có một công thức toán học liên quan chỉ số dựa trên số 0 với số Fibonacci tương ứng của nó. Công thức là:

Lưu ý rằng ở vế phải của phương trình, nó không phải là căn bậc hai của 5 được nâng lên lũy thừa n; nó là biểu thức trong ngoặc đơn được nâng lên lũy thừa n. Có hai cách diễn đạt như vậy.

Nếu n là 0, Fibn sẽ bằng 0. Nếu n là 1, Fib _N sẽ là 1. Nếu n là 2, Fib _N sẽ là 1. Nếu n là 3, Fib _N sẽ là 2. Nếu n là 4, Fib _N sẽ là 3 - và như vậy. Người đọc có thể xác minh công thức này về mặt toán học bằng cách thay thế các giá trị khác nhau cho n và đánh giá. n là chỉ số dựa trên 0 trong công thức này.

Mã Python cho công thức này là:

nhập toán

Mô-đun toán học đã được nhập. Nó có chức năng căn bậc hai. Toán tử, ** được sử dụng cho quyền lực. Hàm fibNo () thực hiện công thức trực tiếp. Lệnh gọi và in phù hợp cho hàm fibNo () là:

N = 11
right = fibNo (N)
in (ret)

Đầu ra là:

Có thể loại bỏ các chữ số thập phân không cần thiết khỏi câu trả lời. Tuy nhiên, đó là một cuộc thảo luận cho một số thời gian khác.

Nếu các số Fibonacci khác nhau được yêu cầu cho n chỉ mục khác nhau, thì hàm fibNo () phải được gọi một lần cho mỗi chỉ số n để trả về các số Fibonacci tương ứng khác nhau. Chương trình sau đây thực hiện điều này cho các chỉ mục dựa trên 0, 7 đến 9 (bao gồm):

nhập toán

Đầu ra là:

Lưu ý cách mã hóa vòng lặp for bằng Python. Chỉ số đầu tiên là 7. Chỉ số tiếp theo là 8 và chỉ số cuối cùng là 9. 10 trong đối số phạm vi là 9 + 1. Giá trị ở vị trí 10 phải là chỉ số dựa trên 0 cuối cùng cộng với 1. Giá trị đầu tiên đối số, 7, là chỉ số bắt đầu dựa trên số 0.

Sự kết luận

Số Fibonacci là một dãy số nguyên cụ thể (số nguyên dương). Nó bắt đầu bằng 0, theo sau là 1 vô điều kiện. Phần còn lại của các số được phát triển từ đó bằng cách thêm hai số liền kề trước đó.

Để lấy n số Fibonacci đầu tiên, hãy chấp nhận 0 và 1 là hai số đầu tiên, sau đó đối với phần còn lại, hãy sử dụng vòng lặp for với câu lệnh như:

mà thêm hai số trước đó ngay lập tức.

Để chỉ lấy một số Fibonacci từ chỉ số n dựa trên 0, hãy sử dụng công thức: