Bilangan Fibonacci dalam Bahasa Python

Angka Fibonacci adalah urutan tertentu di mana nilai pertama dideklarasikan sebelumnya sebagai 0 dan nilai kedua dideklarasikan sebelumnya sebagai 1. Sisa angka dihasilkan dari dua angka ini dengan menambahkan dua angka sebelumnya. Semua angka Fibonacci adalah bilangan bulat positif, dimulai dari 0. Dua belas angka Fibonacci pertama dan cara mendapatkannya adalah sebagai 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 ekspresi penjumlahan, angka-angka Fibonacci ini dapat dimasukkan ke dalam tabel sebagai berikut:

Baris pertama memiliki angka Fibonacci. Baris kedua memiliki indeks berbasis nol, dengan asumsi bahwa angka Fibonacci berada dalam array.

Bilangan Fibonacci dapat dihasilkan dalam waktu O(n) dan dalam waktu O(1). Dalam ekspresi kompleksitas waktu ini, n berarti n operasi utama, dan 1 berarti 1 operasi utama. Dengan O(n), n angka Fibonacci dihasilkan, mulai dari 0. Dengan O(1), satu angka Fibonacci dihasilkan dari indeks yang sesuai. Itulah mengapa dibutuhkan hanya satu operasi utama, bukan n operasi utama.

Tujuan artikel ini adalah untuk menjelaskan cara menghasilkan angka Fibonacci, dengan cara apa pun, menggunakan Python.

Rumus untuk Bilangan Fibonacci

Definisi formal dari bilangan Fibonacci adalah:

dimana F _n adalah angka Fibonacci pada indeks n

Memproduksi Bilangan Fibonacci dalam Waktu O(n)

Jika n adalah 1, maka hanya 0 yang akan dicetak sebagai angka Fibonacci. Jika n adalah 2, maka 0 dan 1 akan dicetak sebagai angka Fibonacci, dalam urutan itu. Jika n adalah 3, maka 0, 1, dan 1 akan dicetak sebagai bilangan Fibonacci dalam urutan tersebut. Jika n adalah 4, maka 0, 1, 1, dan 2 akan dicetak sebagai bilangan Fibonacci dalam urutan tersebut. Jika n adalah 5, maka 0, 1, 1, 2, dan 3 akan dicetak sebagai bilangan Fibonacci, dalam urutan tersebut. Jika n adalah 6, maka 0, 1, 1, 2, 3, dan 5 akan dicetak sebagai angka Fibonacci, dalam urutan itu – dan seterusnya.

Fungsi Python untuk menghasilkan n bilangan Fibonacci pertama adalah:

Ini dimulai dengan membuat sebuah array dari n elemen, semua diinisialisasi ke nol. Array ini akan menampung angka Fibonacci. Angka Fibonacci pertama, 0, sudah ada di sana. Angka Fibonacci kedua, 1, ditetapkan oleh pernyataan berikutnya (dalam fungsi). Lalu ada for-loop, yang dimulai dari indeks 2 sampai tepat sebelum n. Ini memiliki pernyataan:

Ini menambahkan dua angka sebelumnya.

Kode untuk memanggil fungsi dan mencetak dua belas angka Fibonacci pertama dapat berupa:

N = 12
A = fibonacci(N)
untuk saya dalam rentang (N):
cetak (A[i], akhir='')
mencetak()

Outputnya adalah:

Menghasilkan Satu Angka Fibonacci dalam Waktu Konstan

Ada rumus matematika yang menghubungkan indeks berbasis nol dengan angka Fibonacci yang sesuai. Rumusnya adalah:

Perhatikan bahwa di ruas kanan persamaan, bukan akar kuadrat dari 5 yang dipangkatkan n; itu adalah ekspresi dalam tanda kurung yang dipangkatkan n. Ada dua ekspresi seperti itu.

Jika n adalah 0, Fibn akan menjadi 0. Jika n adalah 1, Fib _n akan menjadi 1. Jika n adalah 2, Fib _n akan menjadi 1. Jika n adalah 3, Fib _n akan menjadi 2. Jika n adalah 4, Fib _n akan menjadi 3 - dan seterusnya. Pembaca dapat memverifikasi rumus ini secara matematis dengan mengganti nilai yang berbeda untuk n dan mengevaluasi. n adalah indeks berbasis nol dalam rumus ini.

Kode Python untuk rumus ini adalah:

impor matematika

Modul matematika telah diimpor. Ini memiliki fungsi akar kuadrat. Operator, ** digunakan untuk daya. Fungsi fibNo() mengimplementasikan rumus secara langsung. Panggilan dan pencetakan yang cocok untuk fungsi fibNo() adalah:

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

Outputnya adalah:

Dimungkinkan untuk menghapus angka desimal yang tidak perlu dari jawaban. Namun, itu adalah diskusi untuk beberapa waktu lain.

Jika angka Fibonacci yang berbeda diperlukan untuk n indeks yang berbeda, fungsi fibNo() harus dipanggil sekali untuk masing-masing n indeks untuk mengembalikan angka Fibonacci terkait yang berbeda. Program berikut melakukan ini untuk indeks berbasis nol, 7 hingga 9 (inklusif):

impor matematika

Outputnya adalah:

Perhatikan cara for-loop dikodekan dengan Python. Indeks pertama adalah 7. Indeks berikutnya adalah 8, dan indeks terakhir adalah 9. 10 dalam argumen rentang adalah 9 + 1. Nilai di posisi 10 harus menjadi indeks berbasis nol terakhir ditambah 1. Yang pertama argumen, 7, adalah indeks berbasis nol awal.

Kesimpulan

Bilangan Fibonacci adalah barisan bilangan bulat tertentu (bilangan bulat positif). Itu dimulai dengan 0, diikuti oleh 1 tanpa syarat. Sisa angka dikembangkan dari sana dengan menambahkan dua angka sebelumnya.

Untuk mendapatkan n bilangan Fibonacci pertama, terima 0 dan 1 sebagai dua yang pertama, kemudian untuk sisanya, gunakan for-loop dengan pernyataan seperti:

yang menambahkan dua angka sebelumnya.

Untuk mendapatkan hanya satu angka Fibonacci dari indeks berbasis nol n, gunakan rumus: