Σειρά Fibonacci μέσα Java χρησιμοποιώντας Αναδρομή και Βρόχους

Τι περιλαμβάνει η σειρά Fibonacci Java?

A Σειρά Fibonacci in Java είναι μια σειρά αριθμών στην οποία ο επόμενος αριθμός είναι το άθροισμα των δύο προηγούμενων αριθμών. Οι δύο πρώτοι αριθμοί της σειράς Fibonacci είναι το 0 και το 1. Οι αριθμοί Fibonacci χρησιμοποιούνται σημαντικά στην υπολογιστική μελέτη χρόνου εκτέλεσης του αλγορίθμου που προσδιορίζει τον μέγιστο κοινό διαιρέτη δύο ακεραίων.

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

Εκφρασμένος ως τύπος, ο κανόνας είναι F(n) = F(n-1) + F(n-2), με F(0) = 0 και F(1) = 1. Ο παρακάτω πίνακας δείχνει πώς παράγονται οι πρώτοι οκτώ όροι.

Πρόγραμμα σειράς Fibonacci σε Java χρησιμοποιώντας το For Loop

Η επαναληπτική έκδοση διατηρεί μόνο δύο τιμές στη μνήμη ανά πάσα στιγμή, γι' αυτό και εκτελείται σε γραμμικό χρόνο και σταθερό χώρο.

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

Παραγωγή:

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

Λογική προγράμματος:

• Ο previousNumber αρχικοποιείται σε 0 και ο nextNumber αρχικοποιείται σε 1.
• Ο βρόχος Fibonacci for επαναλαμβάνεται μέσω maxNumber:
  • Εμφάνιση του προηγούμενου αριθμού.
  • Υπολογίστε το άθροισμα του προηγούμενου αριθμού και του επόμενου αριθμού.
  • Ενημερώστε τις νέες τιμές των previousNumber και nextNumber.

Πρόγραμμα σειράς Fibonacci σε Java χρησιμοποιώντας ενώ βρόχο

Μπορείτε επίσης να δημιουργήσετε ένα Java Σειρές Fibonacci χρησιμοποιώντας ένα while βρόχο μέσα JavaΗ αριθμητική είναι πανομοιότυπη και αλλάζει μόνο η σύνταξη του βρόχου.

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

	}

}

Παραγωγή:

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

Η μόνη διαφορά στη λογική του προγράμματος είναι η χρήση ενός βρόχου while για την εκτύπωση των αριθμών Fibonacci. Ο μετρητής πρέπει να δηλωθεί πριν από τον βρόχο και να αυξηθεί μέσα σε αυτόν, διαφορετικά ο βρόχος δεν τελειώνει ποτέ.

Σειρά Fibonacci με βάση την είσοδο του χρήστη

Η κωδικοποίηση του πλήθους όρων είναι βολική για επίδειξη, αλλά οι πραγματικές ασκήσεις συνήθως διαβάζουν την τιμή από το πληκτρολόγιο. Η κλάση Scanner το χειρίζεται αυτό σε τρεις γραμμές και η λογική δημιουργίας παραμένει ανέπαφη.

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

Δείγμα εκτέλεσης:

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

Λογική προγράμματος:
Η λογική είναι η ίδια με την προηγούμενη. Αντί να γίνεται hardcoding στον αριθμό των στοιχείων που θα εμφανίζονται στο Java Σειράς Fibonacci, ο χρήστης καλείται να εισάγει έναν αριθμό.

Σειρά Fibonacci με χρήση αναδρομής σε Java

Παρακάτω είναι ένα πρόγραμμα της σειράς Fibonacci Java χρησιμοποιώντας αναδρομή:

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

Παραγωγή:

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

Λογική προγράμματος:

Μια αναδρομική συνάρτηση είναι αυτή που έχει τη δυνατότητα να καλεί τον εαυτό της.

fibonacciRecursion():

1. The Java Η συνάρτηση αναδρομής Fibonacci δέχεται έναν αριθμό εισόδου. Ελέγχει για 0, 1 και 2 και επιστρέφει 0, 1, 1 αντίστοιχα, επειδή η ακολουθία Fibonacci στο Java ξεκινά με 0, 1, 1.
2. Όταν η είσοδος n είναι 3 ή μεγαλύτερη, η συνάρτηση καλεί τον εαυτό της αναδρομικά. Η κλήση γίνεται δύο φορές. tracΤο παρακάτω ακολουθεί την κλήση για μια είσοδο 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

Οι βασικές περιπτώσεις σταματούν την καθοδική πορεία. Επειδή οι 1 και 2 επιστρέφουν αμέσως, ο κλάδος για την fibonacciRecursion(2) δεν επεκτείνεται ποτέ περαιτέρω, κάτι που διατηρεί το tracπεπερασμένο.

Βελτιστοποιημένη σειρά Fibonacci χρησιμοποιώντας απομνημόνευση

Η απλή αναδρομή επαναϋπολογίζει τους ίδιους όρους πολλές φορές. Ο υπολογισμός του όρου 40 απαιτεί περισσότερες από 200 εκατομμύρια κλήσεις. Η αποθήκευση κάθε αποτελέσματος την πρώτη φορά που υπολογίζεται εξαλείφει εντελώς αυτή την επανάληψη.

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

Παραγωγή:

Term 50 is: 12586269025
Term 90 is: 2880067194370816120

Σύγκριση των μεθόδων Fibonacci σε Java

Και τα τέσσερα προγράμματα εκτυπώνουν την ίδια ακολουθία, επομένως η απόφαση εξαρτάται από το πόσοι όροι χρειάζονται.

Το ίδιο μοτίβο μετρητή και συσσωρευτή εμφανίζεται σε αρκετές σχετικές ασκήσεις. Συνεχίστε με το Java πρόγραμμα παλίνδρομου, Java πρόγραμμα για τον έλεγχο ενός πρώτου αριθμού, και το Πρόγραμμα για την εκτύπωση πρώτων αριθμών από το 1 έως το 100Για πρακτική που βασίζεται σε πίνακες, βλ. BubblΤαξινόμηση Java και Java συστοιχίες, και να εξετάσετε το για κάθε βρόχο στο Java για εναλλακτική σύνταξη βρόχου.

Συχνές Ερωτήσεις