Seria Fibonacci în Java folosind recursivitatea și buclele
⚡ Rezumat inteligent
Seria Fibonacci în Java generează o secvență în care fiecare termen este egal cu suma celor doi termeni dinaintea sa. Acest articol prezintă bucla for, bucla while, programe cu introducere de date de către utilizator, programe recursive și programe memorizate. tracrecursivitatea și compară complexitatea temporală a fiecărei abordări.

În ce este seria Fibonacci Java?
A Seria Fibonacci in Java este o serie de numere în care următorul număr este suma celor două numere anterioare. Primele două numere ale seriei Fibonacci sunt 0 și 1. Numerele Fibonacci sunt utilizate în mod semnificativ în studiul computațional în timpul rulării algoritmului care determină cel mai mare divizor comun a două numere întregi.
The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
Exprimată ca formulă, regula este F(n) = F(n-1) + F(n-2), unde F(0) = 0 și F(1) = 1. Tabelul de mai jos arată cum se obțin primii opt termeni.
| Poziție (n) | Calcul | Valoare |
|---|---|---|
| 0 | Caz de baza | 0 |
| 1 | Caz de baza | 1 |
| 2 | 0 + 1 | 1 |
| 3 | 1 + 1 | 2 |
| 4 | 1 + 2 | 3 |
| 5 | 2 + 3 | 5 |
| 6 | 3 + 5 | 8 |
| 7 | 5 + 8 | 13 |
Programul Seria Fibonacci în Java folosind For Loop
Versiunea iterativă păstrează doar două valori în memorie în orice moment, motiv pentru care rulează în timp liniar și spațiu constant.
//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;
}
}
}
ieșire:
Fibonacci Series of 10 numbers:0 1 1 2 3 5 8 13 21 34
Logica programului:
- Numărulprecedent este inițializat la 0, iar NumărulSegmentar este inițializat la 1.
- Bucla Fibonacci for iterează prin
maxNumber:- Afișează numărul anterior.
- Calculați suma dintre numărulprecedent și numărulurmător.
- Actualizează noile valori ale numerelor precedentNumber și următorNumber.
Programul Seria Fibonacci în Java folosind While Loop
De asemenea, puteți genera un Java Seria Fibonacci folosind o while buclă înăuntru JavaAritmetica este identică și se schimbă doar sintaxa buclei.
//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++;
}
}
}
ieșire:
Fibonacci Series of 10 numbers:0 1 1 2 3 5 8 13 21 34
Singura diferență în logica programului este utilizarea unei bucle while pentru a afișa numerele Fibonacci. Contorul trebuie declarat înainte de buclă și incrementat în interiorul acesteia, altfel bucla nu se termină niciodată.
Seria Fibonacci bazată pe intrarea utilizatorului
Codarea hardcode a numărului de termeni este convenabilă pentru o demonstrație, dar exercițiile reale citesc de obicei valoarea de la tastatură. Clasa Scanner gestionează acest lucru în trei linii, iar logica de generare rămâne neschimbată.
//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(); } }
Executare eșantion:
How many numbers you want in Fibonacci: 7 Fibonacci Series of 7 numbers:0 1 1 2 3 5 8
Logica programului:
Logica este aceeași ca cea anterioară. În loc să setați codul fix al numărului de elemente care vor fi afișate în Java În seria Fibonacci, utilizatorul este rugat să introducă un număr.
Seria Fibonacci folosind recursiunea în Java
Mai jos este un program din seria Fibonacci în Java folosind recursiunea:
//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) +" ");
}
}
}
ieșire:
Fibonacci Series of 10 numbers: 0 1 1 2 3 5 8 13 21 34
Logica programului:
O funcție recursivă este una care are capacitatea de a se autodenomina.
FibonacciRecursiune():
- Java Funcția recursivă Fibonacci primește un număr de intrare. Verifică 0, 1 și 2 și returnează 0, 1, respectiv 1, deoarece secvența Fibonacci din Java începe cu 0, 1, 1.
- Când intrarea n este 3 sau mai mare, funcția se apelează recursiv. Apelul este efectuat de două ori. trace de mai jos urmează apelului pentru o intrare de 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
Cazurile de bază opresc coborârea. Deoarece 1 și 2 revin imediat, ramura pentru fibonacciRecursion(2) nu se extinde niciodată mai departe, ceea ce menține trace finit.
Seria Fibonacci optimizată folosind memorizarea
Recursivitatea simplă recalculează aceiași termeni de mai multe ori. Calculul termenului 40 necesită peste 200 de milioane de apeluri. Stocarea fiecărui rezultat la prima calculare elimină complet această duplicare.
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)); } }
ieșire:
Term 50 is: 12586269025 Term 90 is: 2880067194370816120
⚠️ Atenție: Al 47-lea termen Fibonacci este 2971215073, care depășește maximul int de 2147483647 și se transformă într-o valoare negativă. Declarați variabilele ca fiind lungi odată ce numărătoarea trece de 46 și treceți la BigInteger după termenul 92.
Compararea metodelor Fibonacci în Java
Toate cele patru programe tipăresc aceeași secvență, așadar decizia depinde de câți termeni sunt necesari.
| Metodă | Complexitatea timpului | Complexitatea spațială | Limită practică |
|---|---|---|---|
| Pentru buclă | O (n) | O (1) | Orice număr, în funcție de tipul numeric |
| În timp ce bucla | O (n) | O (1) | Orice număr, în funcție de tipul numeric |
| Recursivitate simplă | O(2ⁿ) | Stiva O(n) | În jur de 40 de termeni înainte să devină lent |
| Recursivitate cu memoizare | O (n) | O (n) | Orice număr, în funcție de tipul numeric |
Același model de numărător și acumulator apare în mai multe exerciții conexe. Continuați cu Java program palindrom, Java program pentru verificarea unui număr prim, Şi program pentru a afișa numere prime de la 1 la 100Pentru exerciții bazate pe matrice, consultați Bubble Sortare în Java și Java matriceși revizuiți pentru fiecare buclă din Java pentru sintaxa alternativă a buclei.
