Deret Fibonacci di Java

Deret Fibonacci adalah sebuah deret angka yang dimulai dengan dua angka pertama, yaitu 0 dan 1, dan setiap angka berikutnya merupakan jumlah dari dua angka sebelumnya. Secara matematis, deret Fibonacci didefinisikan sebagai:

$F(0)=0$ $F(1)=1$ F(n)=F(n−1)+F(n−2) untuk n>1F(n) = F(n-1) + F(n-2)  untuk n > 1 

Contoh deret Fibonacci pertama adalah: $,\dots$

Di Java, kita bisa membuat program untuk menghitung dan menampilkan deret Fibonacci dengan berbagai pendekatan: menggunakan rekursi, iterasi, atau bahkan menggunakan pendekatan matematika langsung.

1. Implementasi Deret Fibonacci dengan Iterasi

Pendekatan iteratif menggunakan perulangan untuk menghitung angka Fibonacci. Ini adalah cara yang efisien karena hanya membutuhkan memori untuk menyimpan dua angka sebelumnya.

public class FibonacciIterative {
    public static void main(String[] args) {
        int n = 10; // Jumlah elemen yang ingin ditampilkan
        System.out.println("Deret Fibonacci (Iteratif) hingga " + n + " elemen:");
        
        int a = 0, b = 1;
        
        // Menampilkan dua angka pertama
        System.out.print(a + " " + b + " ");
        
        // Menghitung dan menampilkan angka Fibonacci selanjutnya
        for (int i = 2; i < n; i++) {
            int next = a + b;
            System.out.print(next + " ");
            a = b;
            b = next;
        }
    }
}

Penjelasan:

• Kita memulai dengan dua angka pertama, yaitu a = 0 dan b = 1.
• Menggunakan loop untuk menghitung angka Fibonacci selanjutnya dan memperbarui nilai a dan b pada setiap iterasi.

Output:

Deret Fibonacci (Iteratif) hingga 10 elemen:
0 1 1 2 3 5 8 13 21 34

2. Implementasi Deret Fibonacci dengan Rekursi

Pendekatan rekursif melibatkan fungsi yang memanggil dirinya sendiri untuk menghitung angka Fibonacci. Meskipun pendekatan ini lebih sederhana, namun tidak efisien untuk angka yang besar karena memiliki kompleksitas waktu eksponensial.

public class FibonacciRecursive {
    public static void main(String[] args) {
        int n = 10; // Jumlah elemen yang ingin ditampilkan
        System.out.println("Deret Fibonacci (Rekursif) hingga " + n + " elemen:");
        
        for (int i = 0; i < n; i++) {
            System.out.print(fibonacci(i) + " ");
        }
    }
    
    // Fungsi rekursif untuk menghitung angka Fibonacci
    public static int fibonacci(int n) {
        if (n == 0) return 0; // Basis: F(0)
        if (n == 1) return 1; // Basis: F(1)
        return fibonacci(n - 1) + fibonacci(n - 2); // Rekursi: F(n) = F(n-1) + F(n-2)
    }
}

Penjelasan:

• Fungsi fibonacci(n) menghitung angka Fibonacci untuk nilai n dengan cara memanggil dirinya sendiri untuk menghitung angka sebelumnya.
• Kondisi dasar (base case) adalah ketika n = 0 atau n = 1.

Output:

Deret Fibonacci (Rekursif) hingga 10 elemen:
0 1 1 2 3 5 8 13 21 34

Catatan: Pendekatan rekursif ini kurang efisien untuk angka besar karena menghitung ulang angka Fibonacci yang sama berkali-kali.

3. Implementasi Deret Fibonacci dengan Memori Dinamis (Dynamic Programming)

Untuk menghindari perhitungan yang berulang pada pendekatan rekursif, kita bisa menggunakan teknik memori dinamis (dynamic programming). Teknik ini menyimpan hasil perhitungan Fibonacci yang sudah dilakukan dalam array atau struktur data lainnya.

public class FibonacciDynamic {
    public static void main(String[] args) {
        int n = 10; // Jumlah elemen yang ingin ditampilkan
        System.out.println("Deret Fibonacci (Memori Dinamis) hingga " + n + " elemen:");
        
        // Array untuk menyimpan hasil Fibonacci
        int[] fib = new int[n];
        
        // Menetapkan dua nilai pertama
        fib[0] = 0;
        fib[1] = 1;
        
        // Menghitung angka Fibonacci dengan memori dinamis
        for (int i = 2; i < n; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        
        // Menampilkan hasil Fibonacci
        for (int i = 0; i < n; i++) {
            System.out.print(fib[i] + " ");
        }
    }
}

Penjelasan:

• Kita menggunakan array fib[] untuk menyimpan hasil perhitungan Fibonacci.
• Setiap angka Fibonacci dihitung berdasarkan dua angka sebelumnya yang sudah disimpan di dalam array.

Output:

Deret Fibonacci (Memori Dinamis) hingga 10 elemen:
0 1 1 2 3 5 8 13 21 34

Keunggulan: Pendekatan ini jauh lebih efisien dibandingkan dengan rekursi murni karena tidak menghitung angka yang sama berulang kali.

4. Implementasi Deret Fibonacci dengan Optimasi Ruang (Space Optimization)

Jika kita ingin mengurangi penggunaan memori lebih lanjut, kita bisa mengoptimalkan ruang dengan hanya menyimpan dua angka Fibonacci terakhir yang dihitung, karena setiap angka hanya bergantung pada dua angka sebelumnya.

public class FibonacciOptimizedSpace {
    public static void main(String[] args) {
        int n = 10; // Jumlah elemen yang ingin ditampilkan
        System.out.println("Deret Fibonacci (Optimasi Ruang) hingga " + n + " elemen:");
        
        int a = 0, b = 1;
        
        // Menampilkan dua angka pertama
        System.out.print(a + " " + b + " ");
        
        // Menghitung dan menampilkan angka Fibonacci selanjutnya
        for (int i = 2; i < n; i++) {
            int next = a + b;
            System.out.print(next + " ");
            a = b;
            b = next;
        }
    }
}

Penjelasan:

• Alih-alih menggunakan array untuk menyimpan semua angka, kita hanya menyimpan dua angka terakhir (a dan b), yang sangat mengurangi penggunaan memori.

Output:

Deret Fibonacci (Optimasi Ruang) hingga 10 elemen:
0 1 1 2 3 5 8 13 21 34

Kesimpulan

Deret Fibonacci di Java bisa dihitung menggunakan beberapa pendekatan, masing-masing dengan kelebihan dan kekurangan:

• Iterasi: Efisien dalam hal waktu dan ruang, cocok untuk menghitung deret Fibonacci dalam jumlah besar.
• Rekursi: Menyederhanakan kode, tetapi tidak efisien untuk angka besar karena perhitungan yang berulang.
• Memori Dinamis (Dynamic Programming): Efisien dalam hal waktu, menghindari perhitungan berulang, tetapi menggunakan lebih banyak memori dibandingkan iterasi.
• Optimasi Ruang: Mengurangi penggunaan memori dengan hanya menyimpan dua angka terakhir, sangat efisien dalam hal ruang.

Pilihlah pendekatan yang paling sesuai dengan kebutuhan aplikasi Anda!

source: chatgpt