Deret Fibonacci di Java menggunakan Rekursi dan Perulangan

Apa yang dimaksud dengan Deret Fibonacci Java?

A Seri Fibonacci in Java Deret Fibonacci adalah serangkaian angka di mana angka berikutnya adalah jumlah dari dua angka sebelumnya. Dua angka pertama dalam deret Fibonacci adalah 0 dan 1. Angka Fibonacci banyak digunakan dalam studi komputasi pada algoritma yang menentukan faktor persekutuan terbesar (FPB) dari dua bilangan bulat.

The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Jika dinyatakan sebagai rumus, aturannya adalah F(n) = F(n-1) + F(n-2), dengan F(0) = 0 dan F(1) = 1. Tabel di bawah ini menunjukkan bagaimana delapan suku pertama dihasilkan.

Program Deret Fibonacci di Java menggunakan Untuk Loop

Versi iteratif hanya menyimpan dua nilai dalam memori pada setiap saat, itulah sebabnya ia berjalan dalam waktu linier dan ruang yang konstan.

//Using  For Loop
public class FibonacciExample {
	public static void main(String[] args)
	{
		// Set it to the number of elements you want in the Fibonacci Series
		 int maxNumber = 10;
		 int previousNumber = 0;
		 int nextNumber = 1;
	        System.out.print("Fibonacci Series of "+maxNumber+" numbers:");
	        for (int i = 1; i <= maxNumber; ++i)
	        {
	            System.out.print(previousNumber+" ");
	            /* On each iteration, we are assigning second number
	             * to the first number and assigning the sum of last two
	             * numbers to the second number
	             */


	            int sum = previousNumber + nextNumber;
	            previousNumber = nextNumber;
	            nextNumber = sum;
	        }
	}
}

Keluaran:

Fibonacci Series of 10 numbers:0 1 1 2 3 5 8 13 21 34

Logika Program:

• previousNumber diinisialisasi ke 0 dan nextNumber diinisialisasi ke 1.
• Perulangan Fibonacci berulang melalui maxNumber:
  • Tampilkan previousNumber.
  • Hitung jumlah dari previousNumber dan nextNumber.
  • Perbarui nilai baru untuk previousNumber dan nextNumber.

Program Deret Fibonacci di Java menggunakan While Loop

Anda juga dapat membuat Java Deret Fibonacci menggunakan while lingkaran dalam JavaPerhitungannya identik, dan hanya sintaks perulangan yang berubah.

//Using  While Loop
public class FibonacciWhileExample {
	public static void main(String[] args)
	{
		 int maxNumber = 10, previousNumber = 0, nextNumber = 1;
	        System.out.print("Fibonacci Series of "+maxNumber+" numbers:");

	        int i=1;
	        while(i <= maxNumber)
	        {
	            System.out.print(previousNumber+" ");
	            int sum = previousNumber + nextNumber;
	            previousNumber = nextNumber;
	            nextNumber = sum;
	            i++;
	        }

	}

}

Keluaran:

Fibonacci Series of 10 numbers:0 1 1 2 3 5 8 13 21 34

Satu-satunya perbedaan dalam logika program adalah penggunaan perulangan while untuk mencetak angka Fibonacci. Penghitung harus dideklarasikan sebelum perulangan dan ditambah di dalamnya, jika tidak, perulangan tidak akan pernah berakhir.

Deret Fibonacci Berdasarkan Input Pengguna

Menuliskan nilai hitungan secara langsung (hard-coding) memang mudah untuk demonstrasi, tetapi latihan sebenarnya biasanya membaca nilai dari keyboard. Kelas Scanner menangani hal itu dalam tiga baris kode, dan logika pembangkitan tetap tidak berubah.

//fibonacci series based on the user input
import java.util.Scanner;

public class FibonacciUserInput {

    public static void main(String[] args)
    {
        int maxNumber = 0;
        int previousNumber = 0;
        int nextNumber = 1;

        System.out.println("How many numbers you want in Fibonacci:");
        Scanner scanner = new Scanner(System.in);
        maxNumber = scanner.nextInt();
        System.out.print("Fibonacci Series of " + maxNumber + " numbers:");

        for (int i = 1; i <= maxNumber; ++i)
        {
            System.out.print(previousNumber + " ");
            /* On each iteration, we are assigning the second number
             * to the first number and assigning the sum of the last two
             * numbers to the second number
             */

            int sum = previousNumber + nextNumber;
            previousNumber = nextNumber;
            nextNumber = sum;
        }

        scanner.close();
    }
}

Contoh Eksekusi:

How many numbers you want in Fibonacci:
7
Fibonacci Series of 7 numbers:0 1 1 2 3 5 8

Logika Program:
Logikanya sama seperti sebelumnya. Alih-alih menentukan secara langsung jumlah elemen yang akan ditampilkan di Java Pada deret Fibonacci, pengguna diminta untuk memasukkan sebuah angka.

Deret Fibonacci Menggunakan Rekursi di Java

Di bawah ini adalah program deret Fibonacci Java menggunakan rekursi:

//Using Recursion
public class FibonacciCalc{
	public static int fibonacciRecursion(int n){
	if(n == 0){
		return 0;
	}
	if(n == 1 || n == 2){
			return 1;
		}
	return fibonacciRecursion(n-2) + fibonacciRecursion(n-1);
	}
    public static void main(String args[]) {
	int maxNumber = 10;
	System.out.print("Fibonacci Series of "+maxNumber+" numbers: ");
	for(int i = 0; i < maxNumber; i++){
			System.out.print(fibonacciRecursion(i) +" ");
		}
	}
}

Keluaran:

Fibonacci Series of 10 numbers: 0 1 1 2 3 5 8 13 21 34

Logika Program:

Fungsi rekursif adalah fungsi yang mempunyai kemampuan untuk memanggil dirinya sendiri.

fibonacciRekursi():

1. The Java Fungsi rekursi Fibonacci menerima sebuah angka masukan. Fungsi ini memeriksa apakah angka tersebut adalah 0, 1, dan 2, lalu mengembalikan 0, 1, dan 1 secara berurutan, karena deret Fibonacci dalam Java dimulai dengan 0, 1, 1.
2. Ketika input n adalah 3 atau lebih besar, fungsi tersebut memanggil dirinya sendiri secara rekursif. Panggilan dilakukan dua kali. trace di bawah ini mengikuti permintaan input sebesar 4.

fibonacciRecursion(4)
    = fibonacciRecursion(2) + fibonacciRecursion(3)

    fibonacciRecursion(2) = 1                    // base case, no further calls
    fibonacciRecursion(3) = fibonacciRecursion(1) + fibonacciRecursion(2)
                          = 1 + 1
                          = 2

    Result: 1 + 2 = 3

Kasus dasar menghentikan penurunan. Karena 1 dan 2 keduanya langsung kembali, cabang untuk fibonacciRecursion(2) tidak pernah berkembang lebih jauh, yang merupakan alasan mengapa tracterbatas.

Deret Fibonacci yang Dioptimalkan Menggunakan Memoisasi

Rekursi biasa menghitung ulang suku yang sama berkali-kali. Menghitung suku ke-40 membutuhkan lebih dari 200 juta panggilan. Menyimpan setiap hasil pada saat pertama kali dihitung akan menghilangkan duplikasi tersebut sepenuhnya.

public class FibonacciMemo {

    static long[] cache;

    public static long fib(int n) {
        if (n <= 1) {
            return n;
        }
        // return the stored value when it exists
        if (cache[n] != 0) {
            return cache[n];
        }
        cache[n] = fib(n - 1) + fib(n - 2);
        return cache[n];
    }

    public static void main(String[] args) {
        int maxNumber = 90;
        cache = new long[maxNumber + 1];

        System.out.println("Term 50 is: " + fib(50));
        System.out.println("Term 90 is: " + fib(90));
    }
}

Keluaran:

Term 50 is: 12586269025
Term 90 is: 2880067194370816120

Perbandingan Metode Fibonacci dalam Java

Keempat program tersebut mencetak urutan yang sama, jadi keputusannya bergantung pada berapa banyak suku yang dibutuhkan.

Pola penghitung dan akumulator yang sama muncul dalam beberapa latihan terkait. Lanjutkan dengan Java program palindrom, yang Java Program untuk memeriksa bilangan prima, Dan Program untuk mencetak bilangan prima dari 1 hingga 100.Untuk latihan berbasis array, lihat Bubble Urutkan di Java ke Java array, dan meninjau kembali untuk setiap perulangan di Java untuk sintaks perulangan alternatif.

Pertanyaan Umum Demo Slot