Nombor Fibonacci dalam Bahasa Python

Nombor Fibonacci ialah jujukan tertentu di mana nilai pertama pra-diisytiharkan sebagai 0 dan nilai kedua pra-diisytiharkan sebagai 1. Selebihnya nombor dihasilkan daripada kedua-dua nombor ini dengan menambah dua nombor sebelumnya. Semua nombor Fibonacci adalah integer positif, bermula dari 0. Dua belas nombor Fibonacci pertama dan cara ia diperoleh adalah seperti berikut:

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

Tanpa ungkapan jumlah, nombor Fibonacci ini boleh diletakkan dalam jadual seperti berikut:

Baris pertama mempunyai nombor Fibonacci. Baris kedua mempunyai indeks berasaskan sifar, dengan mengandaikan bahawa nombor Fibonacci berada dalam tatasusunan.

Nombor Fibonacci boleh dihasilkan dalam masa O(n) dan dalam masa O(1). Dalam ungkapan kerumitan masa ini, n bermaksud n operasi utama, dan 1 bermaksud 1 operasi utama. Dengan O(n), n nombor Fibonacci dihasilkan, bermula dari 0. Dengan O(1), satu nombor Fibonacci dihasilkan daripada indeks yang sepadan. Itulah sebabnya ia hanya memerlukan satu operasi utama dan bukannya n operasi utama.

Matlamat artikel ini adalah untuk menerangkan cara menghasilkan nombor Fibonacci, sama ada cara, menggunakan Python.

Formula untuk Nombor Fibonacci

Takrif formal nombor Fibonacci ialah:

di mana F _n ialah nombor Fibonacci pada indeks n

Menghasilkan Nombor Fibonacci dalam Masa O(n).

Jika n ialah 1, maka hanya 0 akan dicetak sebagai nombor Fibonacci. Jika n ialah 2, maka 0 dan 1 akan dicetak sebagai nombor Fibonacci, dalam susunan tersebut. Jika n ialah 3, maka 0, 1, dan 1 akan dicetak sebagai nombor Fibonacci dalam susunan tersebut. Jika n ialah 4, maka 0, 1, 1, dan 2 akan dicetak sebagai nombor Fibonacci dalam susunan tersebut. Jika n ialah 5, maka 0, 1, 1, 2, dan 3 akan dicetak sebagai nombor Fibonacci, dalam susunan tersebut. Jika n ialah 6, maka 0, 1, 1, 2, 3, dan 5 akan dicetak sebagai nombor Fibonacci, dalam susunan itu – dan seterusnya.

Fungsi Python untuk menghasilkan n nombor Fibonacci pertama ialah:

Ia bermula dengan mencipta susunan n elemen, semuanya dimulakan kepada sifar. Tatasusunan ini akan memegang nombor Fibonacci. Nombor Fibonacci pertama, 0, sudah ada. Nombor Fibonacci kedua, 1, diberikan oleh pernyataan seterusnya (dalam fungsi). Kemudian terdapat gelung untuk, yang bermula dari indeks 2 hingga sebelum n. Ia mempunyai kenyataan:

Ini menambah dua nombor sebelum ini.

Kod untuk memanggil fungsi dan mencetak dua belas nombor Fibonacci pertama boleh:

N = 12
A = fibonacci(N)
untuk i dalam julat(N):
cetak (A[i], hujung=’ ‘)
cetak()

Outputnya ialah:

Menghasilkan Satu Nombor Fibonacci dalam Masa Malar

Terdapat formula matematik yang mengaitkan indeks berasaskan sifar dengan nombor Fibonacci yang sepadan. Formulanya ialah:

Ambil perhatian bahawa di sebelah kanan persamaan, bukan punca kuasa dua bagi 5 yang dinaikkan kepada kuasa n; ia adalah ungkapan dalam kurungan yang dinaikkan kepada kuasa n. Terdapat dua ungkapan sedemikian.

Jika n ialah 0, Fibn akan menjadi 0. Jika n ialah 1, Fib _n akan menjadi 1. Jika n ialah 2, Fib _n akan menjadi 1. Jika n ialah 3, Fib _n akan menjadi 2. Jika n ialah 4, Fib _n akan menjadi 3 - dan seterusnya. Pembaca boleh mengesahkan formula ini secara matematik dengan menggantikan nilai yang berbeza untuk n dan menilai. n ialah indeks berasaskan sifar dalam formula ini.

Kod Python untuk formula ini ialah:

import matematik

Modul matematik telah diimport. Ia mempunyai fungsi punca kuasa dua. Operator, ** digunakan untuk kuasa. Fungsi fibNo() melaksanakan formula secara langsung. Panggilan dan pencetakan yang sesuai untuk fungsi fibNo() ialah:

N = 11
kanan = fibNo(N)
cetak(ret)

Outputnya ialah:

Adalah mungkin untuk mengalih keluar digit perpuluhan yang tidak diperlukan daripada jawapan. Walau bagaimanapun, itu adalah perbincangan untuk masa yang lain.

Jika nombor Fibonacci berbeza diperlukan untuk n indeks yang berbeza, fungsi fibNo() perlu dipanggil sekali untuk setiap indeks n untuk mengembalikan nombor Fibonacci yang berbeza yang sepadan. Program berikut melakukan ini untuk indeks berasaskan sifar, 7 hingga 9 (termasuk):

import matematik

Outputnya ialah:

Perhatikan cara gelung untuk dikodkan dalam Python. Indeks pertama ialah 7. Indeks seterusnya ialah 8, dan indeks terakhir ialah 9. 10 dalam hujah julat ialah 9 + 1. Nilai dalam kedudukan 10 mestilah indeks berasaskan sifar terakhir ditambah 1. Yang pertama argumen, 7, ialah indeks berasaskan sifar permulaan.

Kesimpulan

Nombor Fibonacci ialah jujukan tertentu bagi nombor bulat (integer positif). Ia bermula dengan 0, diikuti dengan 1 tanpa syarat. Selebihnya nombor dibangunkan dari sana dengan menambah dua nombor sebelumnya yang terdekat.

Untuk mendapatkan n nombor Fibonacci pertama, terima 0 dan 1 sebagai dua yang pertama, kemudian untuk selebihnya, gunakan gelung untuk dengan pernyataan seperti:

yang menambah dua nombor terdahulu yang terdekat.

Untuk mendapatkan hanya satu nombor Fibonacci daripada indeks berasaskan sifar n, gunakan formula: