Deret Fibonacci di Python: Pelajari dan Jelajahi Teknik Pengodean

Deret Fibonacci adalah cara menyenangkan untuk terus berlatih Python. Dalam artikel ini, Anda akan belajar cara mengimplementasikan deret Fibonacci di Python menggunakan berbagai teknik Python, mulai dari menulis fungsi yang efisien dan menangani rekursi hingga menggunakan prinsip berorientasi objek untuk solusi yang lebih optimal. 

Setelah selesai, ikuti kursus Menulis Fungsi di Python kami untuk memperkuat konsep seperti ruang lingkup (scoping) dan penanganan error, atau coba kursus Pemrograman Berorientasi Objek Menengah di Python untuk mempelajari pewarisan dan kelas dasar. Sekarang, mari kita coba deret Fibonacci.

Jawaban Singkat

Deret Fibonacci dimulai dengan 0 dan 1, dengan setiap angka merupakan jumlah dari dua angka sebelumnya. Cara paling sederhana untuk menghasilkannya di Python adalah dengan loop:

n = 10
a, b = 0, 1

fibonacci_numbers = []

for _ in range(n):  
    fibonacci_numbers.append(str(a)) 
    a, b = b, a + b

print(' '.join(fibonacci_numbers))

# This prints the first 10 Fibonacci numbers
# 0 1 1 2 3 5 8 13 21 34Didukung oleh

Apa itu Deret Fibonacci?

Deret Fibonacci adalah konsep matematika yang muncul di banyak bidang sains dan alam. Ini adalah deretan angka di mana setiap angka merupakan jumlah dari dua angka sebelumnya, dimulai dengan 0 dan 1. Pola ini menjadi dasar untuk aplikasi di bidang seperti ilmu komputer dan keuangan. 

Dua aspek utama yang mendefinisikan deret Fibonacci: struktur rekursif deret dan kaitannya dengan rasio emas.

Sifat rekursif deret Fibonacci

Deret Fibonacci dimulai dengan 0 dan 1. Setiap angka baru adalah jumlah dari dua angka sebelumnya. Sebagai contoh:

0 + 1 = 1

1 + 1 = 2

1 + 2 = 3

2 + 3 = 5

3 + 5 = 8

5 + 8 = 13

Dan seterusnya. 

Secara matematis, kita menuliskannya sebagai F(n) = F(n-1) + F(n-2). Deret ini membangun dirinya dengan berulang kali menambahkan dua angka terakhir. Dua angka pertama, 0 dan 1, adalah titik awal atau kasus dasar. Tanpa ini, deret tidak akan bekerja.

Pola rekursif ini menjadi dasar bagi beberapa algoritma dalam ilmu komputer. Misalnya, rekursi dalam pemrograman bekerja pada deret ini saat menyelesaikan masalah seperti menghasilkan angka Fibonacci atau membagi tugas menjadi bagian-bagian yang lebih kecil dan mudah dikelola.

Kaitan dengan rasio emas 

Deret Fibonacci terkait erat dengan rasio emas yang merupakan bilangan irasional yang dilambangkan dengan φ (nilainya sekitar 1,618). Jika Anda membagi sebuah angka Fibonacci dengan angka sebelumnya, rasionya akan semakin mendekati φ. Misalnya:

5 ÷ 3 ≈ 1,666

8 ÷ 5 ≈ 1,6

13 ÷ 8 ≈ 1,625

Semakin jauh Anda melangkah, semakin mendekati 1,618. Ini bukan kebetulan — rasio tersebut muncul secara alami dalam deret Fibonacci karena cara angka-angkanya bertumbuh.

Euclid pertama kali mendeskripsikannya di Yunani kuno sebagai rasio ekstrem dan tengah. Sejak itu, rasio ini dikaitkan dengan pola di alam, seperti spiral pada cangkang dan bunga, serta dalam seni dan arsitektur.

Rasio emas dalam seni. Sumber

Aplikasi Praktis Deret Fibonacci

Deret Fibonacci muncul dengan cara yang mengejutkan di banyak bidang. Mari fokus pada dua penerapan paling menonjol: polanya di alam dan penggunaannya dalam ilmu komputer.

Fibonacci di alam

Anda dapat melihat deret Fibonacci di seluruh alam. Lihat pada bunga — jumlah kelopaknya sering kali sesuai dengan angka Fibonacci. Misalnya, aster dapat memiliki 34, 55, atau 89 kelopak, dan lili sering memiliki 3, 5, atau 8. Pola ini membantu tanaman tumbuh dengan cara yang memaksimalkan sinar matahari dan curah hujan.

Spiral pada sisik pinus dan bunga matahari juga mengikuti angka Fibonacci. Susunan biji pada bunga matahari, misalnya, sesuai dengan deret ini. Menarik bagaimana sesuatu yang sesederhana menambahkan dua angka dapat menggambarkan begitu banyak dunia alami.

Fibonacci dalam ilmu komputer

Deret Fibonacci juga berperan penting dalam algoritma dan struktur data. Misalnya, angka Fibonacci digunakan dalam algoritma pencarian untuk memecah masalah menjadi bagian-bagian yang lebih kecil secara efisien. Deret ini bahkan melatarbelakangi Fibonacci heap, jenis struktur data yang digunakan untuk mempercepat operasi tertentu seperti mencari jalur terpendek dalam sebuah jaringan.

Berikut contoh sederhana cara Anda dapat menghasilkan deret Fibonacci di Python:

def fibonacci(n):
	if n <= 1:
		return n
	return fibonacci(n - 1) + fibonacci(n - 2)

# Example usage
fibonacci_numbers = []

for i in range(10):
	fibonacci_numbers.append(str(fibonacci(i)))

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34Didukung oleh

Fungsi rekursif ini menunjukkan bagaimana deret Fibonacci dibangun. Meskipun rekursi mudah dipahami, ada juga versi yang dioptimalkan, seperti pemrograman dinamis, untuk menghitung angka Fibonacci jauh lebih cepat.

Dalam kriptografi, angka Fibonacci dapat membantu menghasilkan kunci yang aman. Dan dalam kecerdasan buatan, angka-angka ini mengoptimalkan jaringan saraf untuk meningkatkan cara algoritma belajar dan beradaptasi. 

Contoh umum lainnya

Berikut beberapa contoh lain tentang bagaimana deret ini muncul dalam kehidupan sehari-hari dan bidang khusus:

• Dalam Seni: Deret Fibonacci telah digunakan oleh seniman dan arsitek selama berabad-abad. Struktur terkenal seperti Parthenon menampilkan proporsi ini karena secara alami enak dipandang.
• Dalam Musik: Komposer menggunakan angka Fibonacci untuk membuat ritme dan melodi. Misalnya, mereka mengaitkan not penuh dengan 1, not setengah dengan 2, dan not seperempat dengan 3 untuk menciptakan pola yang harmonis.
• Dalam Perdagangan: Trader saham menerapkan angka Fibonacci untuk menganalisis tren pasar. Mereka menggunakannya untuk memprediksi level harga potensial tempat saham mungkin berbalik arah, membantu memutuskan kapan membeli atau menjual.
• Dalam Fisika: Dalam fisika kuantum, pola Fibonacci telah diamati dalam interaksi dan perilaku partikel, mengungkapkan bagaimana deret ini muncul bahkan pada skala alam yang paling kecil.

Mengimplementasikan Deret Fibonacci di Python

Karena Python menyediakan beberapa cara untuk menghasilkan deret Fibonacci, saya membahas yang paling umum digunakan langkah demi langkah beserta contohnya.

Menggunakan metode iteratif

Metode iteratif adalah salah satu cara paling sederhana untuk menghasilkan deret Fibonacci. Metode ini menggunakan loop untuk menghitung setiap suku dalam deret, yang membuatnya lebih hemat memori daripada metode rekursif. Begini cara kerjanya:

Saya menetapkan dua variabel, a dan b, ke 0 dan 1. Ini mewakili dua angka pertama dalam deret. Lalu, saya menggunakan for loop untuk menghitung angka berikutnya. Saya memperbarui a agar menyimpan nilai b, dan b menjadi jumlah dari a dan b sebelumnya.

Berikut kode Python-nya:

n = 10
a, b = 0, 1

fibonacci_numbers = []

for _ in range(n):
    fibonacci_numbers.append(str(a))
    a, b = b, a + b

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34Didukung oleh

Jika Anda ingin menggunakan while loop alih-alih for loop, berikut cara menulis kodenya:

# Number of terms to print in the Fibonacci series
n = 10

# Initialize the first two terms
a, b = 0, 1
i = 0

fibonacci_numbers = []

while i < n:
	fibonacci_numbers.append(str(a))
	# Update the terms
	a, b = b, a + b
	i += 1

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34Didukung oleh

Kedua metode sangat mudah dipahami, sehingga sempurna untuk pemula. 

Menggunakan metode rekursif

Metode rekursif adalah cara lain untuk menghasilkan angka Fibonacci. Metode ini tidak secepat metode iteratif untuk deret yang lebih besar, tetapi sangat baik untuk memahami logika di balik bagaimana deret terbentuk.

Sebagai contoh, saya membuat fungsi bernama fibonacci_recursive. Fungsi ini menerima angka n sebagai masukan. Jika n adalah 0 atau 1, fungsi akan mengembalikan n. Ini adalah kasus dasar yang memberi tahu rekursi kapan harus berhenti. Untuk angka lainnya, fungsi memanggil dirinya sendiri untuk menghitung dua angka sebelumnya dan menjumlahkannya.

Berikut kodenya:

def fibonacci_recursive(n):
	if n <= 1:
		return n
	else:
		return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

num_terms = 10
fibonacci_numbers = []
for i in range(num_terms):
	fibonacci_numbers.append(str(fibonacci_recursive(i)))

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34Didukung oleh

Metode ini bekerja dengan baik untuk deret kecil tetapi bisa menjadi lambat saat deret membesar karena menghitung ulang nilai yang sama berkali-kali.

Menggunakan metode rekursif yang dioptimalkan dengan caching

Untuk mengatasi ketidakefisienan rekursi biasa, saya sering menggunakan caching. lru_cache Python menyimpan nilai yang sebelumnya dihitung sehingga fungsi tidak perlu mengulang pekerjaan.

Berikut cara saya melakukannya:

from functools import lru_cache

@lru_cache(maxsize = None)
def fib_cache(n):
    if n == 0:
        return 0  
    elif n == 1:
        return 1
    else:
        return fib_cache(n-1) + fib_cache(n-2)

print(f"The Fibonacci Number is {fib_cache(10)}")

# The Fibonacci Number is 55Didukung oleh

Pendekatan ini menggabungkan kejelasan rekursi dengan efisiensi caching.

Cara yang Lebih Lanjut untuk Melakukan Deret Fibonacci di Python

Jika Anda mencari cara lain untuk menghitung angka Fibonacci, berikut beberapa teknik yang lebih maju:

Eksponensiasi matriks

Eksponensiasi matriks adalah salah satu cara paling efisien untuk menghitung angka Fibonacci untuk nilai n yang besar. Alih-alih menghitung ulang suku berulang kali, metode ini menggunakan perkalian matriks untuk mendapatkan hasil dalam waktu logaritmik.

Berikut cara saya mengimplementasikannya di Python:

import numpy as np

def fibonacci_matrix(n):
	def matrix_power(matrix, power):
		return np.linalg.matrix_power(matrix, power)
	if n == 0:
		return 0
	matrix = np.array([[1, 1], [1, 0]])
	result = matrix_power(matrix, n-1)
	return result[0][0]

fibonacci_numbers = []

for i in range(10):
	fibonacci_numbers.append(str(fibonacci_matrix(i)))

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34Didukung oleh

Dalam kode ini, jika n adalah 0, fungsi mengembalikan 0 sebagai kasus dasar. Untuk nilai lainnya, matriks dipangkatkan ke (n-1) menggunakan fungsi matrix_power dari numpy. Angka Fibonacci pada posisi n terdapat pada elemen kiri atas dari matriks hasil.

Rumus Binet

Rumus Binet menghitung langsung angka Fibonacci ke-n tanpa iterasi atau rekursi. Rumus ini didasarkan pada rasio emas, φ, dan menggunakan ekspresi matematis untuk menghitung hasil secara instan.

Rumusnya adalah:

Dengan ketentuan:

• φ = (1 + √5) / 2​​, rasio emas.
• 1 - φ adalah konjugat dari φ.

Berikut kode Python untuk rumus Binet:

import math

def fibonacci_binet(n):
    phi = (1 + math.sqrt(5)) / 2
    return round((phi ** n - (1 - phi) ** n) / math.sqrt(5))

# Find the 10th Fibonacci number
n = 10
result = fibonacci_binet(n)
print(f"The Fibonacci Number of {n}th term is {result}" )

# The Fibonacci Number of 10th term is 55Didukung oleh

Dalam kode ini, fungsi fibonacci_binet(n) menghitung angka Fibonacci ke-n menggunakan rumus Binet. Di dalam fungsi, saya menghitung phi (rasio emas) sebagai (1 + math.sqrt(5)) / 2, menggunakan math.sqrt() untuk akar kuadrat dari 5. Rumus (phi ** n - (1 - phi) ** n) / math.sqrt(5) kemudian diterapkan untuk menemukan angka Fibonacci ke-n secara langsung. Lalu, saya menggunakan fungsi round() untuk menangani ketidakakuratan angka pecahan yang kecil.

Array

Anda juga dapat menggunakan array untuk menghasilkan dan menyimpan seluruh deret Fibonacci. Ini bermanfaat saat Anda membutuhkan beberapa suku sekaligus.

Berikut kodenya:

def fibonacci(n):
    if n <= 0:
        return "Incorrect Output"
    data = [0, 1]  # Initialize list with first two Fibonacci terms: 0 and 1
    if n > 2:
        for i in range(2, n):  # Start loop from the third term
            data.append(data[i-1] + data[i-2])  # Calculate next term as sum of previous two
    return data[n-1]  # Return the nth term

print(f"Fibonacci Number: {fibonacci(10)}")

# Fibonacci Number: 34Didukung oleh

Backtracking

Backtracking adalah opsi lain yang bisa saya gunakan, terutama saat ingin menggabungkan rekursi dengan memoization untuk kinerja yang lebih baik.

Berikut kodenya:

def fibonacci_backtracking(n, computed ={0: 0, 1: 1}):
    if n in computed:
        return computed[n]
    computed[n] = fibonacci_backtracking(n - 1) + fibonacci_backtracking(n - 2)
    return computed[n]

n = 10
result = fibonacci_backtracking(n)
print(f"The {n}th Fibonacci term is {result}")

# The 10th Fibonacci term is 55Didukung oleh

Kompleksitas Algoritma Fibonacci di Python

Kita telah melalui cukup banyak contoh! Sekarang mari kita lihat perbedaannya dalam hal kompleksitas waktu dan ruang. Seperti yang telah disebutkan, beberapa metode cepat tetapi menggunakan lebih banyak memori, sementara yang lain lebih lambat tetapi membutuhkan ruang lebih sedikit. Saya menyiapkan tabel ini untuk membandingkan efisiensi setiap pendekatan.

Pada tabel di atas, berikut arti masing-masing kompleksitas waktu dan ruang:

Kompleksitas waktu

• O(n): Algoritma melakukan iterasi melalui deret sekali dengan menjalankan jumlah operasi tetap untuk setiap elemen. Waktu yang dibutuhkan bertambah secara linear terhadap ukuran masukan n.

• O(1): Angka Fibonacci dihitung menggunakan jumlah operasi tetap tanpa iterasi atau rekursi.

• O(2ⁿ): Algoritma membuat dua pemanggilan rekursif untuk setiap masukan yang menyebabkan pertumbuhan eksponensial jumlah pemanggilan fungsi saat n meningkat.

• O(log n): Waktu jalan bertambah sebanding dengan logaritma dari ukuran masukan n.

Kompleksitas ruang

• O(n): Algoritma menggunakan memori yang bertambah langsung seiring jumlah masukan n. Di sini, setiap elemen membutuhkan ruang dalam jumlah tetap.

• O(1): Penggunaan memori tetap konstan terlepas dari ukuran masukan.

• O(2ⁿ): Menggunakan ruang secara eksponensial karena pembuatan state baru untuk setiap cabang.

• O(log n): Perkalian matriks perantara menggunakan memori logaritmik.

Penutup

Seperti yang Anda lihat, di Python, Anda dapat menghitung angka Fibonacci menggunakan banyak metode berbeda, dari loop sederhana hingga teknik lanjutan seperti eksponensiasi matriks dan rumus Binet. Setiap metode memiliki kelebihan dan komprominya masing-masing.

Saya harap Anda mempelajari sesuatu tentang deret Fibonacci sekaligus tentang pemrograman Python. Jika Anda ingin mengeksplorasi lebih jauh tentang Python dan topik terkait, lihat kursus Pengantar Python kami. Anda juga dapat mencoba seluruh jalur karier Pengembang Python kami dan mempelajari teknik pemrograman bahkan mulai mengembangkan paket Anda sendiri!