Deret Fibonacci adalah serangkaian angka yang dinamai menurut matematikawan Italia, yang dikenal sebagai Fibonacci. Ini hanyalah rangkaian angka yang dimulai dari 0 dan 1 dan kemudian dilanjutkan dengan penambahan dua angka sebelumnya. Pada artikel ini, Anda akan mempelajari cara menulis program Python untuk mengimplementasikan deret Fibonacci menggunakan beberapa metode. Pointer di bawah ini akan dibahas
Mari kita mulai
Apa itu Deret Fibonacci?
Deret Fibonacci adalah deret angka yang dibentuk dengan penjumlahan dua angka sebelumnya dalam deret tersebut
Contoh Deret Fibonacci. 0,1,1,2,3,5
Dalam contoh di atas, 0 dan 1 adalah dua suku pertama dari deret tersebut. Kedua istilah ini dicetak langsung. Suku ketiga dihitung dengan menjumlahkan dua suku pertama. Dalam hal ini 0 dan 1. Jadi, kita dapatkan 0+1=1. Oleh karena itu 1 dicetak sebagai suku ketiga. Suku berikutnya dihasilkan dengan menggunakan suku kedua dan ketiga dan tidak menggunakan suku pertama. Hal ini dilakukan sampai jumlah istilah yang diinginkan atau diminta oleh pengguna. Dalam contoh di atas, kami telah menggunakan lima istilah
Selanjutnya, mari kita menulis program Python untuk mengimplementasikannya
Program Python untuk mengimplementasikan Deret Fibonacci
Menerapkan urutan Fibonacci dalam bahasa pemrograman Python adalah yang paling mudah. Sekarang ada beberapa cara untuk mengimplementasikannya, yaitu
- Menggunakan Lingkaran
- Menggunakan Rekursi
Mari kita lihat kedua kode tersebut satu per satu
Deret Fibonacci menggunakan Loop
Pengulangan di Python memungkinkan kita mengeksekusi sekelompok pernyataan beberapa kali. Mari kita menulis program python untuk mengimplementasikan Deret Fibonacci menggunakan loop
# Enter number of terms needed #0,1,1,2,3,5.... a=int(input("Enter the terms")) f=0 #first element of series s=1 #second element of series if a<=0: print("The requested series is ",f) else: print(f,s,end=" ") for x in range(2,a): next=f+s print(next,end=" ") f=s s=nextKeluaran. Masukkan suku 5 0 1 1 2 3
Cara lain untuk memprogram pembuatan deret Fibonacci adalah dengan menggunakan rekursi. Mari gali lebih dalam
Program Python untuk Menulis Deret Fibonacci Menggunakan Rekursi
Rekursi adalah teknik pemrograman Python dasar di mana suatu fungsi memanggil dirinya sendiri secara langsung atau tidak langsung. Fungsi yang sesuai disebut fungsi rekursif. Dengan menggunakan algoritma rekursif, masalah tertentu dapat diselesaikan dengan cukup mudah. Mari kita lihat cara menggunakan rekursi untuk mencetak angka 'n' pertama dari Deret Fibonacci dengan Python
Temukan Pelatihan Python kami di Kota/Negara Teratas
Kode Piton
def FibRecursion(n): if n <= 1: return n else: return(FibRecursion(n-1) + FibRecursion(n-2)) nterms = int(input("Enter the terms? ")) # take input from the user if nterms <= 0: # check if the number is valid print("Please enter a positive integer") else: print("Fibonacci sequence:") for i in range(nterms): print(FibRecursion(i))_Keluaran. Berapa banyak istilah. 5
0 1 1 2 3
Penjelasan. Dalam program Python di atas, kami menggunakan rekursi untuk menghasilkan deret Fibonacci. Fungsi FibRecursion dipanggil secara rekursif sampai kita mendapatkan hasilnya. Dalam fungsinya, pertama-tama kita periksa apakah angka n adalah nol atau satu. Jika ya, kami mengembalikan nilai n. Jika tidak, kita secara rekursif memanggil fibonacci dengan nilai n-1 dan n-2
Ini membawa kita ke akhir artikel 'Seri Fibonacci dalam Python' ini. Kita telah mempelajari cara mencetak angka Fibonacci ke-N secara terprogram menggunakan pernyataan loop atau rekursi
Jika Anda ingin mempelajari Python dan mendapatkan keahlian dalam analisis kuantitatif, penambangan data, dan penyajian data untuk melihat lebih dari sekadar angka dengan mengubah karier Anda menjadi Ilmuwan Data, lihat Pelatihan Python interaktif dan online langsung kami. Anda akan menggunakan perpustakaan seperti Pandas, Numpy, Matplotlib, Scipy, Scikit, Pyspark dan menguasai konsep-konsep seperti pembelajaran mesin Python, skrip, urutan, pengikisan web, dan analitik data besar yang memanfaatkan Apache Spark. Pelatihan dilengkapi dengan dukungan 24*7 untuk memandu Anda selama masa belajar
Ada pertanyaan untuk kami?
Berlari
# Write a program to print fibonacci series upto n terms in python num = 10 n1, n2 = 0, 1 print("Fibonacci Series:", n1, n2, end=" ") for i in range(2, num): n3 = n1 + n2 n1 = n2 n2 = n3 print(n3, end=" ") print()Pada artikel ini, saya akan menjelaskan pendekatan langkah demi langkah tentang cara mencetak deret Fibonacci menggunakan dua teknik berbeda, iterasi dan rekursi.
Sebelum kita mulai, mari kita pahami beberapa terminologi dasar
Apa itu Deret Fibonacci?
Deret Fibonacci adalah urutan angka di mana angka yang diberikan adalah hasil dari penjumlahan 2 angka yang datang sebelumnya. Dan penjumlahan 2 angka sebelumnya beberapa kali membentuk deret yang kita sebut Deret Fibonacci
Deret Fibonacci dimulai dengan dua angka, yaitu 0 dan 1. Kemudian setiap angka berikutnya terdiri dari menjumlahkan dua angka sebelumnya
Misalnya, ambil 0 dan 1. Mereka adalah dua angka pertama dalam urutan. Jika Anda menambahkan mereka bersama-sama, Anda mendapatkan 1. Jadi deretnya dimulai dari 0, 1, 1,
Kemudian, untuk menemukan angka selanjutnya, Anda menjumlahkan angka terakhir yang Anda miliki dengan angka sebelumnya. Jadi 1+1 = 2. Jadi urutannya sejauh ini adalah 0, 1, 1, 2,. Masuk akal?
Kita dapat merepresentasikannya secara lebih matematis seperti 0, 1, (1) - [0 + 1]. Demikian pula, angka Fibonacci selanjutnya adalah - 0, 1, 1, (2) - [1 + 1]. Dan seterusnya. Berikut diagram yang menunjukkan 10 angka Fibonacci pertama
Ini adalah contoh deret Fibonacci – 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. Dalam urutan berkelanjutan ini, setiap angka individu adalah angka Fibonacci
Secara matematis, Deret Fibonacci diwakili oleh rumus ini
F(n) = F(n-1) + F(n-2), di mana n > 1
Kita dapat menggunakan urutan ini untuk menemukan bilangan Fibonacci ke-n
Deret menarik ini secara luas diasosiasikan dengan ahli matematika Leonardo Pisano, juga dikenal sebagai Fibonacci. Dia berasal dari Republik Pisa, itulah sebabnya dia juga dikenal sebagai Leonardo dari Pisa
Leonardo dikenal sebagai salah satu matematikawan paling berbakat di abad pertengahan
Cara Mencetak Deret Fibonacci dengan Python
Anda dapat menulis program komputer untuk mencetak deret Fibonacci dengan 2 cara berbeda
- Iteratif, dan
- Secara rekursif
Iterasi berarti mengulang pekerjaan sampai kondisi yang ditentukan terpenuhi. Rekursi, di sisi lain, berarti melakukan satu tugas dan melanjutkan ke tugas berikutnya untuk melakukan tugas yang tersisa
Berikut adalah algoritma iteratif untuk mencetak deret Fibonacci
- Buat 2 variabel dan inisialisasi dengan 0 dan 1 (pertama = 0, kedua = 1)
- Buat variabel lain untuk melacak panjang deret Fibonacci yang akan dicetak (panjang)
- Loop (panjang kurang dari panjang seri)
- Cetak pertama + kedua
- Perbarui variabel pertama dan kedua (pertama akan mengarah ke yang kedua, dan yang kedua akan mengarah ke yang pertama + kedua)
- Kurangi variabel panjang dan ulangi dari langkah 3
- Setelah loop berakhir, hentikan program
Bagaimana algoritma iteratif bekerja
Pertimbangkan bahwa kita perlu mencetak deret Fibonacci dengan panjang 7. Maka alur algoritmanya akan seperti ini
Penjelasan Langkah-Langkah Iterasi OutputInitial First = 0, Second = 1[0, 1]1 Print (first + second) = [0+1] Sekarang variabel first akan mengarah ke variabel second. Dan yang kedua akan menunjuk ke angka Fibonacci berikutnya yang kita hitung di atas. [0, 1, 1]2Cetak (pertama + detik) = [1+1] Sekarang variabel pertama akan menunjuk ke variabel kedua. Dan yang kedua akan menunjuk ke angka Fibonacci berikutnya yang kita hitung di atas. [0, 1, 1, 2]3 Cetak (pertama + detik) = [1+2] Sekarang variabel pertama akan menunjuk ke variabel kedua. Dan yang kedua akan menunjuk ke angka Fibonacci berikutnya yang kita hitung di atas. [0, 1, 1, 2, 3]4Cetak (pertama + kedua) = [2+3] Sekarang variabel pertama akan menunjuk ke variabel kedua. Dan yang kedua akan menunjuk ke angka Fibonacci berikutnya yang kita hitung di atas. [0, 1, 1, 2, 3, 5]5Cetak (pertama + kedua) = [3+5] Sekarang variabel pertama akan menunjuk ke variabel kedua. Dan yang kedua akan menunjuk ke angka Fibonacci berikutnya yang kita hitung di atas. [0, 1, 1, 2, 3, 5, 8]Jadi, deret Fibonacci terakhir untuk panjang 7 adalah [0, 1, 1, 2, 3, 5, 8]
Kode Python Iteratif untuk mencetak Deret Fibonacci
def PrintFibonacci(length): #Initial variable for the base case. first = 0 second = 1 #Printing the initial Fibonacci number. print(first, second, end=" ") #decreasing the length by two because the first 2 Fibonacci numbers #already printed. length -= 2 #Loop until the length becomes 0. while length > 0: #Printing the next Fibonacci number. print(first + second, end=" ") #Updating the first and second variables for finding the next number. temp = second second = first + second first = temp #Decreasing the length that states the Fibonacci numbers to be #printed more. length -= 1 if __name__ == "__main__": print("Fibonacci Series - ") PrintFibonacci(7) passOutput untuk panjang 7
Fibonacci Series - 1 1 2 3 5 8_Penjelasan Kode
Pada kode di atas, pertama-tama kita telah mendefinisikan sebuah fungsi yang akan mencetak deret Fibonacci. Itu menerima parameter untuk panjangnya, dan fungsinya perlu mencetak deret Fibonacci
Selanjutnya kita buat 2 variabel yang berisi 2 nilai Fibonacci awal yaitu 0 dan 1
Kemudian kami mencetak 2 nilai pertama [0, 1] dan mengurangi panjangnya dengan 2, karena 2 nilai sudah dicetak
Kami akan menjalankan loop untuk waktu panjang yang tersisa, dan setiap kali mencetak nilai Fibonacci berikutnya dengan menambahkan 2 suku sebelumnya yang disimpan dalam variabel pertama dan kedua (yang kami buat awalnya untuk melacak 2 nilai sebelumnya)
Perbarui nilai pertama dan kedua yang akan mengarah ke 2 nilai sebelumnya [pertama = detik, dan kedua = sebelumnya pertama + kedua]
Loop akan berjalan hingga panjangnya menjadi 0, yang menyatakan bahwa panjang deret Fibonacci yang diperlukan dicetak
Kemudian kita memanggil fungsi yang ditentukan untuk mencetak Fibonacci dari fungsi utama dengan meneruskan argumen panjang yang diperlukan untuk dicetak. Dan begitulah
Ada pendekatan lain untuk mencetak deret Fibonacci menggunakan bantuan rekursi. Jadi mari kita pahami pendekatan itu juga
Algoritma Rekursif untuk mencetak Deret Fibonacci
- Terima nilai angka Fibonacci pertama dan kedua sebelumnya sebagai panjang yang akan dicetak
- Periksa apakah panjangnya 0 lalu hentikan pemanggilan fungsi
- Cetak nilai Fibonacci dengan menambahkan 2 nilai sebelumnya yang diterima di parameter fungsi (pertama dan kedua)
- Secara rekursif panggil fungsi untuk nilai yang diperbarui dari yang pertama dan kedua, serta nilai panjang yang dikurangi
Untuk pemanggilan fungsi rekursif ini, kita perlu melewatkan nilai awal Fibonacci, yaitu (0 dan 1), pada variabel pertama dan kedua
Untuk membantu Anda memahami algoritme ini dengan lebih baik, mari kita lihat implementasi algoritme Python. Kemudian kita akan melihat sebuah contoh sehingga Anda dapat melihat bagaimana algoritma rekursif ini bekerja
Kode Python Rekursif untuk Mencetak Deret Fibonacci
def PrintFibonacci(first, second, length): #Stop the printing and recursive calling if length reaches #the end. if(length == 0): return #Printng the next Fibonacci number. print(first + second, end=" ") #Recursively calling the function by updating the value and #decrementing the length. PrintFibonacci(second, first+second, length-1) if __name__ == "__main__": #Print initial 2 values. print(0,1,end=" ") #Calling the Function to print the remaining length #fibonacci series PrintFibonacci(0,1,7-2)Keluaran
Penjelasan kode
Pertama, kami membuat fungsi dan melakukan rekursi di atasnya. Dalam fungsi itu, kami menerima nilai dari 2 angka Fibonacci sebelumnya untuk menghitung angka Fibonacci saat ini. Dan kami memiliki panjang yang melacak kasing dasar
Untuk kasus dasar rekursi, kami memeriksa apakah panjangnya mencapai 0. Jika ya, maka kami akan mengakhiri panggilan rekursif
Dalam kasus lain, kami mencetak angka Fibonacci dengan menambahkan 2 angka Fibonacci sebelumnya
Dan kemudian kami secara rekursif memanggil fungsi untuk mencetak nilai Fibonacci berikutnya dengan memperbarui 2 nilai sebelumnya dan mengurangi panjangnya
Sekarang mari kita visualisasikan pemanggilan rekursif dari fungsi ini dengan bantuan pohon rekursi. Panjang yang ingin kita cetak adalah 7
Sebelum pemanggilan rekursif dilakukan, fungsi utama mencetak 2 nilai awal, 0 dan 1. Dan kemudian meneruskan nilai-nilai ini ke fungsi rekursif
Fungsi Rekursif mencetak nilai (0 + 1) dan memanggil secara rekursif dengan nilai yang diperbarui berikutnya
Kemudian fungsi rekursif mencetak nilai (1 + 1) dan memanggil secara rekursif dengan nilai yang diperbarui berikutnya
Sekarang fungsi rekursif mencetak nilai (1 + 2) dan memanggil secara rekursif dengan nilai yang diperbarui berikutnya
Dan kemudian fungsi rekursif mencetak nilai (2 + 3) dan memanggil secara rekursif dengan nilai yang diperbarui berikutnya
Sekarang fungsi rekursif mencetak nilai (3 + 5) dan memanggil secara rekursif dengan nilai yang diperbarui berikutnya
Akhirnya, panggilan terakhir dilakukan. Dan panjangnya 0, sehingga akan mengakhiri panggilan rekursif lagi dan rangkaiannya dicetak di konsol
Analisis Kompleksitas Waktu
Untuk Pendekatan Iteratif
Dalam algoritma Iteratif, kami mengulang hingga panjangnya menjadi 0. Dalam loop, kami melakukan operasi waktu konstan untuk mencetak nilai dan memperbarui variabel.
Jika kita menganggap panjang itu n, maka kompleksitas waktunya adalah O(n)
Untuk Pendekatan Rekursif
Dalam pendekatan rekursif, kami memanggil fungsi rekursif hingga panjang yang diberikan beberapa kali. Kami juga melakukan operasi pencetakan konstan yang sederhana
Jadi dalam hal ini juga jika kita menganggap panjangnya sebagai n angka, maka kompleksitas waktunya adalah O(n)
Analisis Kompleksitas Ruang
Untuk Pendekatan Iteratif
Dalam pendekatan iteratif kita belum mengambil memori ekstra untuk menerima dua variabel yang melacak dua angka Fibonacci sebelumnya dan konstanta ke sejumlah panjang deret. Jadi kompleksitas ruang akan konstan O(1)
Untuk Pendekatan Rekursif
Dalam pendekatan rekursif, kita memanggil fungsi panjang beberapa kali. Kami tahu bahwa rekursi secara internal menggunakan tumpukan panggilan
Jadi jika kita menganggap itu sebagai memori yang diambil oleh program, maka panggilan rekursif dilakukan beberapa kali lamanya. Maka kompleksitas ruang akan menjadi O(n)
Kesimpulan
Deret Fibonacci adalah deret angka yang setiap angkanya merupakan penjumlahan dari dua angka sebelumnya
Urutan Fibonacci ditemukan tidak hanya dalam matematika tetapi di seluruh alam - seperti di kelopak bunga, daun atau duri kaktus, dan seterusnya
Ini juga pertanyaan wawancara yang sering ditanyakan – jadi bagus untuk mengetahui cara kerjanya
Saya mengambil inspirasi dari posting ini dari InterviewBit
IKLAN
IKLAN
IKLAN
IKLAN
IKLAN
IKLAN
IKLAN
IKLAN
IKLAN
IKLAN
Baca lebih banyak posting
Jika artikel ini bermanfaat, tweetlah
Belajar kode secara gratis. Kurikulum open source freeCodeCamp telah membantu lebih dari 40.000 orang mendapatkan pekerjaan sebagai pengembang. Memulai