Fibonacci seeria Java Rekursiooni ja tsüklite kasutamine

Milles on Fibonacci seeria Java?

A Fibonacci seeria in Java on arvujada, milles järgmine arv on kahe eelmise arvu summa. Fibonacci rea kaks esimest arvu on 0 ja 1. Fibonacci numbreid kasutatakse oluliselt kahe täisarvu suurima ühisjagaja määramise algoritmi arvutuslikus uurimises.

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

Valemina väljendatuna on reegel F(n) = F(n-1) + F(n-2), kus F(0) = 0 ja F(1) = 1. Allolev tabel näitab, kuidas esimesed kaheksa liiget tekivad.

Fibonacci seeria programm sisse Java kasutades For Loopi

Iteratiivne versioon hoiab mälus igal ajahetkel ainult kahte väärtust, mistõttu see töötab lineaarses ajas ja konstantses ruumis.

//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;
	        }
	}
}

Väljund:

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

Programmi loogika:

• eelmineNumber initsialiseeritakse väärtusele 0 ja järgmineNumber initsialiseeritakse väärtusele 1.
• Fibonacci tsükkel itereerub läbi maxNumber:
  • Kuva eelmine arv.
  • Arvuta eelmiseNumber ja järgmiseNumber summa.
  • Värskenda eelmise numbri ja järgmise numbri uusi väärtusi.

Fibonacci seeria programm sisse Java kasutades While Loop

Samuti saate genereerida Java Fibonacci seeria, mis kasutab a while silmus sisse JavaAritmeetika on identne, muutub ainult tsükli süntaks.

//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++;
	        }

	}

}

Väljund:

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

Programmi loogika ainus erinevus seisneb selles, et Fibonacci arvude väljatrükkimiseks kasutatakse while-tsüklit. Loendur tuleb deklareerida enne tsüklit ja selle sees väärtust suurendada, vastasel juhul tsükkel ei lõpe kunagi.

Fibonacci seeria, mis põhineb kasutaja sisendil

Demonstratsiooni jaoks on mugav termini „count“ kõvakodeerida, aga tegelikes harjutustes loetakse selle väärtus tavaliselt klaviatuurilt. Skanneri klass käsitleb seda kolmes reas ja genereerimisloogika jääb puutumata.

//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();
    }
}

Proovijooks:

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

Programmi loogika:
Loogika on sama mis varem. Selle asemel, et kõvakodeerida kuvatavate elementide arvu Java Fibonacci jada puhul palutakse kasutajal sisestada arv.

Fibonacci seeria rekursiooni abil Java

Allpool on Fibonacci seeria programm Java rekursiooni kasutamine:

//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) +" ");
		}
	}
}

Väljund:

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

Programmi loogika:

Rekursiivne funktsioon on funktsioon, mis suudab ennast ise välja kutsuda.

fibonacciRecursion():

1. . Java Fibonacci rekursioonifunktsioon võtab sisendiks numbri. See kontrollib väärtusi 0, 1 ja 2 ning tagastab vastavalt 0, 1 ja 1, kuna Fibonacci jada Java algab 0, 1, 1.
2. Kui sisend n on 3 või suurem, kutsub funktsioon ennast rekursiivselt. Kutse tehakse kaks korda. tracAllpool olev e järgneb üleskutsele sisestada 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

Baasjuhud peatavad laskumise. Kuna nii 1 kui ka 2 naasevad kohe, siis FibonacciRecursion(2) haru ei laiene enam kunagi, mis hoiabki trace lõplik.

Optimeeritud Fibonacci seeria, kasutades memoiseerimist

Lihtrekursioon arvutab samu termineid mitu korda ümber. Termini 40 arvutamiseks on vaja rohkem kui 200 miljonit päringut. Iga tulemuse salvestamine esimesel arvutamisel kõrvaldab selle dubleerimise täielikult.

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));
    }
}

Väljund:

Term 50 is: 12586269025
Term 90 is: 2880067194370816120

Fibonacci meetodite võrdlus Java

Kõik neli programmi prindivad sama jada, seega sõltub otsus sellest, mitu terminit on vaja.

Sama loenduri ja akumulaatori muster esineb mitmes omavahel seotud harjutuses. Jätkake järgmisega: Java palindroomi programm, Java programm algarvu kontrollimiseksJa Programm algarvude 1-st 100-ni printimiseksMassiivipõhise harjutamise kohta vaata BubblSorteeri Java ja Java massiividja vaadake üle iga tsükli kohta Java alternatiivse tsükli süntaksi jaoks.

KKK