Fibonacci-sarja sisään Java rekursioiden ja silmukoiden käyttö

Mitä Fibonacci-sarja sisältää Java?

A Fibonacci-sarja in Java on lukusarja, jossa seuraava luku on kahden edellisen luvun summa. Fibonaccin sarjan kaksi ensimmäistä lukua ovat 0 ja 1. Fibonaccin lukuja käytetään merkittävästi kahden kokonaisluvun suurimman yhteisen jakajan määrittävän algoritmin laskennallisessa ajonaikaisessa tutkimuksessa.

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

Kaavana ilmaistuna sääntö on F(n) = F(n-1) + F(n-2), missä F(0) = 0 ja F(1) = 1. Alla oleva taulukko näyttää, miten kahdeksan ensimmäistä termiä tuotetaan.

Fibonacci-sarjan ohjelma sisään Java käyttämällä For Loopia

Iteratiivinen versio pitää muistissa vain kaksi arvoa kerrallaan, minkä vuoksi se toimii lineaarisessa ajassa ja vakioavaruudessa.

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

lähtö:

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

Ohjelman logiikka:

• edellinenNumber alustetaan arvoon 0 ja seuraavaNumber alustetaan arvoon 1.
• Fibonaccin for-silmukka iteroi läpi maxNumber:
  • Näytä edellinenluku.
  • Laske edellisenNumberin ja seuraavanNumberin summa.
  • Päivitä previousNumber- ja nextNumber-kohteiden uudet arvot.

Fibonacci-sarjan ohjelma sisään Java käyttäen While Loopia

Voit myös luoda Java Fibonaccin sarja käyttäen a while silmukka sisään JavaAritmetiikka on identtinen, ja vain silmukan syntaksi muuttuu.

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

	}

}

lähtö:

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

Ohjelmalogiikan ainoa ero on while-silmukan käyttö Fibonaccin lukujen tulostamiseen. Laskuri on määriteltävä ennen silmukkaa ja sen sisällä on kasvatettava arvoa, muuten silmukka ei koskaan pääty.

Fibonacci-sarja, joka perustuu käyttäjän syötteeseen

Termin count kovakoodaus on kätevää demonstraatiota varten, mutta oikeissa harjoituksissa arvo luetaan yleensä näppäimistöltä. Scanner-luokka käsittelee sen kolmella rivillä, ja generointilogiikka pysyy koskemattomana.

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

Näyteajo:

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

Ohjelman logiikka:
Logiikka on sama kuin aiemmin. Sen sijaan, että näytettävien elementtien määrä olisi kiinteästi koodattu Java Fibonaccin sarjassa käyttäjää pyydetään syöttämään luku.

Fibonacci-sarja, jossa käytetään rekursiota Java

Alla on Fibonacci-sarjan ohjelma Java käyttämällä rekursiota:

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

lähtö:

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

Ohjelman logiikka:

Rekursiivinen funktio on sellainen, joka pystyy kutsumaan itseään.

fibonacciRecursion():

1. Java Fibonaccin rekursiofunktio ottaa syötteenä luvun. Se tarkistaa, ovatko ne 0, 1 ja 2, ja palauttaa arvon 0, 1 ja 1 vastaavasti, koska Fibonaccin lukujono Java alkaa numeroilla 0, 1, 1.
2. Kun syöte n on 3 tai suurempi, funktio kutsuu itseään rekursiivisesti. Kutsu tehdään kahdesti. tracAlla oleva e seuraa 4:n syöttökehotusta.

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

Perustapaukset pysäyttävät laskeutumisen. Koska sekä 1 että 2 palaavat välittömästi, FibonacciRecursion(2):n haara ei koskaan laajene pidemmälle, mikä pitää trace äärellinen.

Optimoitu Fibonaccin sarja muistioimalla

Pelkkä rekursio laskee samat termit uudelleen monta kertaa. Termin 40 laskeminen vaatii yli 200 miljoonaa kutsua. Kunkin tuloksen tallentaminen ensimmäisellä laskemiskerralla poistaa tämän päällekkäisyyden kokonaan.

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

lähtö:

Term 50 is: 12586269025
Term 90 is: 2880067194370816120

Fibonaccin menetelmien vertailu Java

Kaikki neljä ohjelmaa tulostavat saman sekvenssin, joten päätös riippuu siitä, kuinka monta termiä tarvitaan.

Sama laskuri- ja akkumulaattorikuvio esiintyy useissa toisiinsa liittyvissä harjoituksissa. Jatka Java palindromiohjelma, The Java ohjelma alkuluvun tarkistamiseksi, ja ohjelma alkulukujen tulostamiseen 1:stä 100:aanKatso taulukkoon perustuvaa harjoittelua varten BubblLajittele Java ja Java taulukotja tarkista jokaiselle silmukalle Java vaihtoehtoista silmukkasyntaksia varten.

UKK