Teknik Elektro LinksThermostat, Panel Bel, Board Mikro, Driver Relay.

Belajar Python – Menghitung Deret Bilangan Fibonacci Tanpa Rekursi

Deret bilangan Fibonacci adalah deret bilangan yang mempunyai anggota sebagai berikut:

1, 1, 2 , 3, 5, 8, 13, 21, 34, 55, 89, ..., dst.

Bilangan pertama dan kedua dari deret bilangan Fibonacci adalah 1 dan 1. Bilangan Fibonacci ke-3 adalah hasil penjumlahan dari bilangan ke-1 dan bilangan ke-2. Bilangan ke-4 adalah hasil penjumlahan dari bilangan ke-2 dan bilangan ke-3. Bilangan ke-5 adalah hasil penjumlahan dari bilangan ke-3 dan bilangan ke-4. Dan seterusnya dan seterusnya.

Untuk deret bilangan Fibonacci modern ada yang dimulai dari 0 dan 1, sehingga deretnya adalah sebagai berikut:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ..., dst.

Secara matematis, rumus fungsi persamaan deret bilangan Fibonacci adalah:

F(n) = F(n-1) + F(n-2)

dengan bibit bilangan:

F(1) = 1 dan F(2) = 1

Atau untuk deret bilangan Fibonacci modern:

F(1) = 0 dan F(2) = 1

Fungsi Python Bilangan Fibonacci Rekursif

Deret bilangan Fibonacci sering digunakan sebagai contoh program fungsi rekursif, yakni fungsi yang mana di dalam fungsi tersebut terdapat pemanggilan fungsi itu sendiri. Berikut adalah fungsi bilangan Fibonacci dengan cara rekursif menggunakan bahasa Python.

def Fib(n):
   if n==1 or n==2:
       return 1
   return Fib(n-1) + Fib(n-2)

print Fib(6) # hasil = 8

Pada fungsi di atas, rekursi terjadi mulai dari bilangan Fibonacci ketiga dan seterusnya. Untuk bilangan Fibonacci ke-1 dan ke-2 tidak dihitung melainkan langsung diberikan nilai yakni 1. Pada perintah Fib(6) misalnya, maka yang terjadi adalah sebagai berikut:

Fib(6) = Fib(5) + Fib(4)
= (Fib(4)+Fib(3)) + (Fib(3) + Fib(2))
= ((Fib(3)+Fib(2))+(Fib(2) + Fib(1))) + ((Fib(2)+Fib(1))+1)
= (((Fib(2)+Fib(1))+1)+(1+1)) + ((1+1)+1)
= (((1+1)+1)+(1+1)) + ((1+1)+1)
= 5 + 3
= 8

Program dengan fungsi rekursif membutuhkan memori yang lebih banyak. Setiap kali fungsi dipanggil, memori stack akan berkurang. Nampak pada pemanggilan fungsi Fibonacci dengan parameter 6 (Fib(6)), tedapat sebanyak 12 kali pemanggilan fungsi Fibonacci yang terjadi secara rekursif. Bisa dibayangkan betapa banyaknya fungsi Fibonacci akan dipanggil untuk menghitung bilangan Fibonacci yang ke-50 misalnya. Apalagi bilangan Fibonacci yang ke-100.

Nah, pada tulisan ini saya akan memberikan sebuah contoh program deret bilangan Fibonacci menggunakan bahasa Python yang sedikit berbeda. Masih dalam rangka belajar Python, kita akan membuat sebuah class Fibonacci yang dapat menghitung bilangan Fibonacci dan juga deret bilangan Fibonacci. Contoh program ini tidak menggunakan fungsi rekursif tapi menggunakan perulangan dengan sedikit trik yang menarik.

Sebelum masuk kepada pembahasan program, seperti biasa, kita lihat dulu programnya secara keseluruhan.

Program Class Fibonacci (fibonacci.py)

class Fibonacci:
    def __init__(self):
        self.fibcount = 10
        self.firstfib = [1,1,2,3,5,8,13,21,34,55]
 
    def fib(self, n):
        if n<=self.fibcount:
            return self.firstfib[n-1]
        else:
            for i in range(self.fibcount, n):
                self.firstfib.append(self.firstfib[-2]+self.firstfib[-1])
            self.fibcount = n
            return self.firstfib[-1]
 
    def fiblist(self, n):
        if n<=self.fibcount:
            return self.firstfib[:n]
        else:
            self.fib(n)
            return self.firstfib

Penjelasan Program

Class Fibonacci memiliki variabel instance fibcount dan firstfib. Variabel firstfib adalah sebuah list yang berisi sepuluh bilangan pertama dari deret Fibonacci. Sedangkan variabel fibcount digunakan untuk menyimpan data jumlah anggota deret bilangan Fibonacci yang tersimpan pada firstfib.

self.firstfib = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Class Fibonacci dilengkapi dengan dua metode yakni fib dan fiblist. Metode fib berfungsi untuk menghitung bilangan Fibonacci ke-n dan metode fiblist berfungsi untuk menghasilkan deret bilangan Fibonacci dengan jumlah anggota tertentu. Metode ini mengembalikan data dengan tipe data LIST.

Variabel firstfib pada penggunaanya dapat berkembang sesuai permintaan atau penggunaan. Pada awalnya variabel ini memang hanya didefinisikan dengan 10 bilangan pertama dari deret Fibonacci, tapi list ini akan berkembang sesuai dengan permintaan/penggunaan dalam program.

Contohnya begini. Ketika program meminta data bilangan Fibonacci ke-20, maka class ini akan melakukan perhitungan karena bilangan ke-20 belum ada dalam list firstfib (nilai 20 melebihi dari fibcount yang awalnya hanya bernilai 10). Class akan menghitung bilangan Fibonacci ke-11, 12, 13, 14, dst. sampai bilangan Fibonacci ke-20. Setelah melakukan perhitungan, variabel firstfib akan berisi 20 bilangan Fibonacci pertama dan fibcount akan diupdate menjadi 20. Dan satu contoh lagi, ketika diminta bilangan Fibonacci ke-50, maka akan dihitung bilangan Fibonacci ke-21 hingga bilangan Fibonacci ke-50. Selanjutnya variabel fibfirst akan berisi 50 bilangan pertama dari deret bilangan Fibonacci dan variabel fibcount akan berisi nilai 50.

Jika selanjutnya diminta bilangan Fibonacci ke-20, maka tidak akan dilakukan penghitungan, melainkan akan langsung diambilkan dari list karena bilangan ke-20 sudah ada dalam list firstfib (nilai 20 lebih kecil dari fibcount).

Untuk lebih jelasnya marilah kita simak kembali metode fib dan metode fiblist.

Metode fib

Untuk memudahkan pembacaan tulisan, berikut ini saya tulis kembali definisi metode fib dalam class Fibonacci.

    def fib(self, n):
        if n<=self.fibcount:
            return self.firstfib[n-1]
        else:
            for i in range(self.fibcount, n):
                self.firstfib.append(self.firstfib[-2]+self.firstfib[-1])
            self.fibcount = n
            return self.firstfib[-1]

Untuk bilangan Fibonacci ke-1 sampai dengan bilangan ke-n (dengan nilai n <= fibcount), metode ini tidak perlu melakukan perhitungan, tapi cukup mengambil datanya dari LIST firstfib.

            return self.firstfib[n-1]

Tapi jika yang diminta adalah bilangan Fibonacci ke-n dengan nilai n yang lebih besar dari fibcount, maka class akan melakukan perhitungan dan mengupdate list firstfib dan fibcount.

            for i in range(self.fibcount, n):
                self.firstfib.append(self.firstfib[-2]+self.firstfib[-1])
            self.fibcount = n
            return self.firstfib[-1]

Trik untuk mengembangkan list firstfib ada pada perintah berikut:

            for i in range(self.fibcount, n):
                self.firstfib.append(self.firstfib[-2]+self.firstfib[-1])

Untuk permintaan bilangan Fibonacci yang belum ada dalam list firstfib (n lebih besar dari fibcount), maka perintah append akan menambahkan bilangan Fibonacci selanjutnya pada list firstfib. Bilangan Fibonacci selanjutnya dihitung dengan menjumlahkan bilangan Fibonacci sebelumnya dan sebelumnya lagi (self.firstfib[-2]+self.firstfib[-1]).

Metode fiblist

    def fiblist(self, n):
        if n<=self.fibcount:
            return self.firstfib[:n]
        else:
            self.fib(n)
            return self.firstfib

Class Fibonacci juga menyediakan metode fiblist yang akan mengembalikan deret bilangan Fibonacci dengan tipe data list. Jika jumlah bilangan yang diminta tidak lebih besar dari fibcount, maka metode fiblist akan mengambil data deret dari list firstfib.

        if n<=self.fibcount:
            return self.firstfib[:n]

Akan tetapi jika jumlah bilangan yang diminta lebih besar dari fibcount, maka metode fiblist akan menghitung dulu dengan memanggil metode fib dan mengembalikan variabel firstfib yang telah diupdate.

            self.fib(n)
            return self.firstfib

Cara Penggunaan Class Fibonacci Dalam Program

Untuk menggunakan class Fibonacci yang ada dalam file fibonacci.py, kita perlu melakukan import terlebih dahulu sebagai berikut:

import fibonacci

Selanjutnya kita bisa mendeklarasikan instance dari class Fibonacci dengan cara:

F = fibonacci.Fibonacci()

Untuk menampilkan bilangan Fibonacci ke-34, kita bisa memanggil metode fib dengan cara:

n = F.fib(34)
print n

Untuk menampilkan 25 bilangan pertama deret bilangan Fibonacci, kita bisa memanggil metode fiblist dengan cara:

l = F.fiblist(25)
print l

Screenshot

fibonacci python

Nah, demikianlah Belajar Python kali ini. Semoga penjelasan program di atas cukup komprehensif dan dapat menambah wawasan kita semua. Class Fibonacci di atas dapat dikembangkan lagi dengan menambahkan metode sumof yang berfungsi untuk menghitung jumlah dari deret bilangan Fibonacci. Contoh: sumof(6) akan menghasilkan 20 yang merupakan hasil dari perhitungan 1+1+2+3+5+8 = 20.

Sampai berjumpa lagi pada seri Belajar Python selanjutnya. Selamat berkarya.

 

Add a Comment

Your email address will not be published. Required fields are marked *