Szereg Fibonacciego w Java korzystanie z rekurencji i pętli

Na czym polega ciąg Fibonacciego Java?

A Seria Fibonacciego in Java Ciąg Fibonacciego to ciąg liczb, w którym kolejna liczba jest sumą dwóch poprzednich. Pierwsze dwie liczby ciągu Fibonacciego to 0 i 1. Liczby Fibonacciego są szeroko wykorzystywane w badaniach nad algorytmem obliczającym największy wspólny dzielnik dwóch liczb całkowitych.

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

Wyrażona jako wzór reguła ma postać F(n) = F(n-1) + F(n-2), gdzie F(0) = 0, a F(1) = 1. Poniższa tabela pokazuje, jak powstaje pierwszych osiem wyrazów.

Program szeregu Fibonacciego w Java za pomocą pętli For

Wersja iteracyjna przechowuje w pamięci tylko dwie wartości w danym momencie, dlatego też działa w liniowym czasie i stałej przestrzeni.

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

Wyjście:

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

Logika programu:

• previousNumber jest inicjowany wartością 0, a nextNumber jest inicjowany wartością 1.
• Pętla Fibonacciego iteruje przez maxNumber:
  • Wyświetl poprzedniNumer.
  • Oblicz sumę previousNumber i nextNumber.
  • Zaktualizuj nowe wartości previousNumber i nextNumber.

Program szeregu Fibonacciego w Java za pomocą pętli While

Możesz również wygenerować Java Ciąg Fibonacciego za pomocą while pętla w Java. Arytmetyka jest identyczna, zmienia się jedynie składnia pętli.

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

	}

}

Wyjście:

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

Jedyną różnicą w logice programu jest użycie pętli while do wydrukowania liczb Fibonacciego. Licznik musi zostać zadeklarowany przed pętlą i inkrementowany w jej obrębie, w przeciwnym razie pętla nigdy się nie zakończy.

Szereg Fibonacciego na podstawie danych wejściowych użytkownika

Zakodowanie liczby terminów na stałe jest wygodne w demonstracji, ale w rzeczywistych ćwiczeniach wartość jest zazwyczaj odczytywana z klawiatury. Klasa Scanner obsługuje to w trzech linijkach, a logika generowania pozostaje nienaruszona.

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

Przykładowy przebieg:

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

Logika programu:
Logika jest taka sama jak wcześniej. Zamiast na stałe kodować liczbę elementów do wyświetlenia w Java Ciąg Fibonacciego, użytkownik proszony jest o wprowadzenie liczby.

Szereg Fibonacciego wykorzystujący rekurencję w Java

Poniżej znajduje się program ciągu Fibonacciego w formacie Java używając rekurencji:

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

Wyjście:

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

Logika programu:

Funkcja rekurencyjna to taka, która może wywołać samą siebie.

fibonacciRecursion():

1. Java Funkcja rekurencji Fibonacciego przyjmuje liczbę wejściową. Sprawdza, czy jest ona równa 0, 1 i 2, i zwraca odpowiednio 0, 1, 1, ponieważ ciąg Fibonacciego w Java zaczyna się od 0, 1, 1.
2. Gdy wartość wejściowa n jest równa 3 lub większa, funkcja wywołuje samą siebie rekurencyjnie. Wywołanie jest wykonywane dwukrotnie. tracPoniżej następuje prośba o podanie wartości wejściowej 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

Przypadki bazowe zatrzymują spadek. Ponieważ zarówno 1, jak i 2 zwracają się natychmiast, gałąź dla rekurencji Fibonacci(2) nigdy nie rozszerza się dalej, co powoduje, że trace skończony.

Zoptymalizowany ciąg Fibonacciego z wykorzystaniem memoizacji

Zwykła rekurencja wielokrotnie przelicza te same wyrazy. Obliczenie wyrazu 40 wymaga ponad 200 milionów wywołań. Zapisanie każdego wyniku przy pierwszym obliczeniu całkowicie eliminuje duplikację.

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

Wyjście:

Term 50 is: 12586269025
Term 90 is: 2880067194370816120

Porównanie metod Fibonacciego w Java

Wszystkie cztery programy drukują tę samą sekwencję, więc decyzja zależy od tego, ile wyrazów jest potrzebnych.

Ten sam wzór licznika i akumulatora pojawia się w kilku powiązanych ćwiczeniach. Kontynuuj z Java program palindromowyThe Java program do sprawdzania liczby pierwszeji program do drukowania liczb pierwszych od 1 do 100. Aby zapoznać się z ćwiczeniami opartymi na tablicach, zobacz Bubble Sortuj w Java oraz Java tablicei przejrzyj dla każdej pętli w Java dla alternatywnej składni pętli.

FAQ