Tulis program untuk menghasilkan deret fibonacci dengan python

Question

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

Table of Contents Show

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=next

Keluaran. 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)
    pass

Output 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

For Length 7 
1 1 2 3 5 8

For Length 10
1 1 2 3 5 8 13 21 34

_

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

Sonya Jessica

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