|
Program Python untuk Mencetak Deret Fibonacci
Pertanyaan tentang Deret Fibonacci adalah pertanyaan yang paling sering ditanyakan dalam wawancara Python. 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 dulu beberapa terminologi dasar. Apa itu Deret Fibonacci?Barisan Fibonacci adalah barisan bilangan yang suatu bilangan tertentu merupakan hasil penjumlahan 2 bilangan yang mendahuluinya. Dan penjumlahan 2 angka sebelumnya beberapa kali membentuk suatu deret yang kita sebut Deret Fibonacci. Deret Fibonacci diawali dengan dua angka yaitu 0 dan 1. Kemudian setiap angka berikutnya merupakan hasil penjumlahan dari dua angka sebelumnya. Misalnya, ambil 0 dan 1. Ini adalah dua angka pertama dalam barisan tersebut. Jika dijumlahkan, hasilnya adalah 1. Jadi barisannya dimulai dari 0, 1, 1,... Kemudian, untuk mencari angka berikutnya, tambahkan angka terakhir yang Anda miliki dan angka sebelumnya. Jadi 1+1=2. Jadi barisannya sejauh ini adalah 0, 1, 1, 2, ... Masuk akal? Kita dapat merepresentasikannya secara lebih matematis seperti 0, 1, (1) - [0 + 1]. Begitu pula dengan bilangan 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 deret berkelanjutan ini, setiap bilangan adalah bilangan Fibonacci. Secara matematis, Deret Fibonacci direpresentasikan dengan rumus berikut: F(n)=F(n-1) + F(n-2), dengan n > 1. Kita dapat menggunakan barisan ini untuk mencari bilangan Fibonacci ke-n. Deret menarik ini banyak diasosiasikan dengan ahli matematika Leonardo Pisano, yang juga dikenal sebagai Fibonacci. Dia berasal dari Republik Pisa, itulah sebabnya dia juga dikenal sebagai Leonardo dari Pisa. Leonardo dikenal sebagai salah satu ahli matematika paling berbakat di abad pertengahan. Cara Mencetak Deret Fibonacci dengan PythonAnda dapat menulis program komputer untuk mencetak deret Fibonacci dengan 2 cara berbeda: Secara berulang, dan Secara rekursif. Iterasi berarti mengulangi pekerjaan sampai kondisi yang ditentukan terpenuhi. Rekursi, di sisi lain, berarti melakukan satu tugas dan melanjutkan ke tugas berikutnya untuk menyelesaikan tugas yang tersisa. Berikut algoritma berulang 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 (panjangnya kurang dari panjang seri) Cetak pertama + kedua Perbarui variabel pertama dan kedua (yang pertama akan mengarah ke variabel kedua, dan variabel kedua akan mengarah ke variabel pertama + kedua) Kurangi variabel panjang dan ulangi dari langkah 3 Setelah loop berakhir, hentikan program Cara kerja algoritma iteratif:Anggap saja kita perlu mencetak deret Fibonacci dengan panjang 7. Maka alur algoritmanya akan seperti ini: Iterations Steps Explained OutputInitial First = 0, Second = 1 [0, 1] 1 Print (first + second) = [0+1] Now variable first will point to variable second. And second will point to the next Fibonacci number that we calculated above. [0, 1, 1] 2 Print (first + second) = [1+1] Now variable first will point to variable second. And second will point to the next Fibonacci number that we calculated above. [0, 1, 1, 2] 3 Print (first + second) = [1+2] Now variable first will point to variable second. And second will point to the next Fibonacci number that we calculated above. [0, 1, 1, 2, 3] 4 Print (first + second) = [2+3] Now variable first will point to variable second. And second will point to the next Fibonacci number that we calculatod above. [0, 1, 1, 2, 3, 5] 5 Print (first + second) = [3+5] Now variable first will point to variable second. And second will point to the next Fibonacci number that we calculated above. [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 Urutan 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 8Penjelasan Kode: Pada kode di atas, pertama-tama kita telah mendefinisikan fungsi yang akan mencetak deret Fibonacci. Ia menerima parameter panjangnya, dan fungsinya perlu mencetak deret Fibonacci. Selanjutnya kita buat 2 variabel yang berisi 2 nilai awal Fibonacci yaitu 0 dan 1. Kemudian kita mencetak 2 nilai pertama [0, 1] dan mengurangi panjangnya sebanyak 2, karena 2 nilai sudah dicetak. Kita akan menjalankan perulangan untuk sisa waktu yang tersisa, dan setiap kali mencetak nilai Fibonacci berikutnya dengan menambahkan 2 suku sebelumnya yang disimpan dalam variabel pertama dan kedua (yang awalnya kita buat untuk melacak 2 nilai sebelumnya). Perbarui nilai pertama dan kedua yang akan mengarah ke 2 nilai sebelumnya [pertama=kedua, dan kedua=sebelumnya pertama + kedua]. Perulangan akan berjalan hingga panjangnya menjadi 0, yang menyatakan bahwa panjang deret Fibonacci yang diperlukan telah dicetak. Kemudian kita memanggil fungsi yang ditentukan untuk mencetak Fibonacci dari fungsi utama dengan meneruskan argumen dengan panjang yang diperlukan untuk dicetak. Dan itu dia! Ada pendekatan lain untuk mencetak deret Fibonacci dengan menggunakan bantuan rekursi. Jadi, mari kita pahami pendekatan itu juga. Algoritma Rekursif untuk mencetak Deret Fibonacci:Terima nilai bilangan Fibonacci pertama dan kedua sebelumnya sebagai panjang yang akan dicetak. Periksa apakah panjangnya 0 lalu akhiri pemanggilan fungsi. Cetak nilai Fibonacci dengan menambahkan 2 nilai sebelumnya yang diterima pada parameter fungsi (pertama dan kedua). Memanggil fungsi secara rekursif untuk nilai pertama dan kedua yang diperbarui, serta nilai panjang yang dikurangi. Untuk pemanggilan fungsi rekursif ini, kita perlu meneruskan nilai awal Fibonacci, yaitu (0 dan 1), pada variabel pertama dan kedua. Untuk membantu Anda memahami algoritma ini dengan lebih baik, mari kita lihat implementasi algoritma Python. Kemudian kita akan melihat contohnya sehingga Anda dapat melihat cara kerja algoritma rekursif ini. 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: For Length 7 1 1 2 3 5 8 For Length 10 1 1 2 3 5 8 13 21 34Penjelasan kode: Pertama, kami membuat fungsi dan melakukan rekursi padanya. Dalam fungsi tersebut, kita menerima nilai dari 2 angka Fibonacci sebelumnya untuk menghitung angka Fibonacci saat ini. Dan kami memiliki panjang yang melacak casing dasar. Untuk kasus dasar rekursi, kami memeriksa apakah panjangnya mencapai 0. Jika ya, maka kami akan menghentikan panggilan rekursif. Dalam kasus lain, kami mencetak angka Fibonacci dengan menambahkan 2 angka Fibonacci sebelumnya. Dan kemudian kita memanggil fungsi tersebut secara rekursif untuk mencetak nilai Fibonacci berikutnya dengan memperbarui 2 nilai sebelumnya dan mengurangi panjangnya. Sekarang mari kita visualisasikan pemanggilan rekursif 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. Lalu meneruskan nilai tersebut 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 terbaru berikutnya.
Sekarang fungsi rekursif mencetak nilai (1 + 2) dan memanggil secara rekursif dengan nilai terbaru berikutnya.
Dan kemudian fungsi rekursif mencetak nilai (2 + 3) dan memanggil secara rekursif dengan nilai terbaru berikutnya.
Sekarang fungsi rekursif mencetak nilai (3 + 5) dan memanggil secara rekursif dengan nilai terbaru berikutnya.
Akhirnya, panggilan terakhir dilakukan. Dan panjangnya 0, sehingga akan menghentikan panggilan rekursif lagi dan seri tersebut dicetak di konsol. Analisis Kompleksitas WaktuUntuk Pendekatan IteratifDalam algoritma Iteratif, kita melakukan perulangan hingga panjangnya menjadi 0. Dalam perulangan, kita melakukan operasi waktu yang konstan untuk mencetak nilai dan memperbarui variabel. Jika kita menganggap panjangnya n, maka kompleksitas waktunya adalah O(n). Untuk Pendekatan RekursifDalam pendekatan rekursif, kita memanggil fungsi rekursif hingga beberapa kali panjang tertentu. Kami juga melakukan operasi pencetakan sederhana dan konstan. Jadi dalam hal ini juga jika kita menganggap panjangnya sebagai n angka, maka kompleksitas waktunya adalah O(n). Analisis Kompleksitas RuangUntuk Pendekatan IteratifDalam pendekatan berulang, kita tidak menggunakan memori ekstra untuk menerima dua variabel yang melacak dua bilangan Fibonacci sebelumnya dan konstanta pada bilangan berapa pun dalam panjang deret. Jadi kompleksitas ruang akan menjadi konstan O(1). Untuk Pendekatan RekursifDalam pendekatan rekursif, kita memanggil fungsi panjang berapa kali. Kita tahu bahwa rekursi secara internal menggunakan tumpukan panggilan. Jadi jika kita menganggapnya sebagai memori yang diambil oleh program, maka panggilan rekursif dilakukan beberapa kali. Maka kompleksitas ruangnya menjadi O(n). KesimpulanDeret Fibonacci adalah deret angka yang setiap angkanya merupakan penjumlahan dari dua angka sebelumnya. Deret Fibonacci tidak hanya ditemukan dalam matematika tetapi juga di seluruh alam - seperti pada kelopak bunga, daun atau duri kaktus, dan sebagainya. Ini juga merupakan pertanyaan wawancara yang sering ditanyakan - jadi ada baiknya mengetahui cara kerjanya. Saya mengambil inspirasi dari postingan ini dari InterviewBit. (责任编辑：) |
