Fibonacci-serien in Java med hjälp av rekursion och loopar
⚡ Smart sammanfattning
Fibonacci-serien in Java genererar en sekvens där varje term är lika med summan av de två föregående termerna. Den här artikeln presenterar for loop, while loop, användarinmatning, rekursiva och memo-baserade program, tracanalyserar rekursionen och jämför tidskomplexiteten för varje metod.
Vad är Fibonacci-serien i Java?
A Fibonacci-serien in Java är en talserie där nästa tal är summan av de två föregående talen. De två första talen i Fibonacciserien är 0 och 1. Fibonaccitalen används i stor utsträckning i den beräkningsmässiga körtidsstudien av algoritmen som bestämmer den största gemensamma delaren av två heltal.
The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
Uttryckt som en formel är regeln F(n) = F(n-1) + F(n-2), med F(0) = 0 och F(1) = 1. Tabellen nedan visar hur de första åtta termerna produceras.
| Position (n) | Beräkning | Värderar |
|---|---|---|
| 0 | Basfodral | 0 |
| 1 | Basfodral | 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 |
Fibonacci-seriens program i Java använder For Loop
Den iterativa versionen lagrar endast två värden i minnet åt gången, vilket är anledningen till att den körs i linjär tid och konstant rum.
//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;
}
}
}
Produktion:
Fibonacci Series of 10 numbers:0 1 1 2 3 5 8 13 21 34
Programlogik:
- föregåendeNummer initieras till 0 och nästaNummer initieras till 1.
- Fibonacci-for-loopen itererar igenom
maxNumber:- Visa föregående nummer.
- Beräkna summan av föregåendeNummer och nästaNummer.
- Uppdatera de nya värdena för previousNumber och nextNumber.
Fibonacci-seriens program i Java använder While Loop
Du kan också generera en Java Fibonacciserier med hjälp av en while slinga in JavaAritmetiken är identisk, och endast loopsyntaxen ändras.
//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++;
}
}
}
Produktion:
Fibonacci Series of 10 numbers:0 1 1 2 3 5 8 13 21 34
Den enda skillnaden i programlogiken är användningen av en while-loop för att skriva ut Fibonacci-talen. Räknaren måste deklareras före loopen och ökas inuti den, annars slutar loopen aldrig.
Fibonacci-serien baserad på användarinmatningen
Att hårdkoda termantalet är praktiskt för en demonstration, men verkliga övningar läser vanligtvis värdet från tangentbordet. Klassen Scanner hanterar det på tre rader, och genereringslogiken förblir orörd.
//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(); } }
Provkörning:
How many numbers you want in Fibonacci: 7 Fibonacci Series of 7 numbers:0 1 1 2 3 5 8
Programlogik:
Logiken är densamma som tidigare. Istället för att hårdkoda antalet element som ska visas i Java Fibonacciserien, användaren ombeds att ange ett tal.
Fibonacci-serien använder rekursion i Java
Nedan finns ett program i Fibonacci-serien Java använder rekursion:
//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) +" ");
}
}
}
Produktion:
Fibonacci Series of 10 numbers: 0 1 1 2 3 5 8 13 21 34
Programlogik:
En rekursiv funktion är en som har förmågan att anropa sig själv.
fibonacciRecursion():
- Ocuco-landskapet Java Fibonacci-rekursionsfunktionen tar ett inmatningstal. Den kontrollerar 0, 1 och 2 och returnerar 0, 1 respektive 1, eftersom Fibonacci-sekvensen i Java börjar med 0, 1, 1.
- När inmatningen n är 3 eller större anropar funktionen sig själv rekursivt. Anropet görs två gånger. trace nedan följer uppmaningen för inmatning av 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
Basfallen stoppar nedstigningen. Eftersom 1 och 2 båda återvänder omedelbart, expanderar grenen för fibonacciRecursion(2) aldrig ytterligare, vilket är det som håller trace ändlig.
Optimerade Fibonacci-serier med hjälp av memoisering
Enkel rekursion beräknar samma termer om många gånger. Beräkning av term 40 kräver mer än 200 miljoner anrop. Att lagra varje resultat första gången det beräknas tar bort den dubbleringen helt.
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)); } }
Produktion:
Term 50 is: 12586269025 Term 90 is: 2880067194370816120
⚠️ Varning: Den 47:e Fibonaccitermen är 2971215073, vilket överstiger det maximala int-värdet på 2147483647 och radbryts till ett negativt värde. Deklarera variablerna lika länge när antalet passerar 46, och byt till BigInteger efter term 92.
Jämförelse av Fibonacci-metoder i Java
Alla fyra programmen skriver ut samma sekvens, så beslutet vilar på hur många termer som behövs.
| Metod | Tidskomplexitet | Rymdkomplexitet | Praktisk gräns |
|---|---|---|---|
| För slinga | O (n) | O (1) | Valfritt antal, beroende på den numeriska typen |
| Medan slinga | O (n) | O (1) | Valfritt antal, beroende på den numeriska typen |
| Enkel rekursion | O(2ⁿ) | O(n)-stack | Runt 40 termer innan det blir långsamt |
| Rekursion med memoisering | O (n) | O (n) | Valfritt antal, beroende på den numeriska typen |
Samma räknar- och ackumulatormönster förekommer i flera relaterade övningar. Fortsätt med Java palindromprogram, den Java program för att kontrollera ett primtal, Och den program för att skriva ut primtal från 1 till 100För arraybaserad övning, se Bubble Sortera i Java och Java arrayeroch granska för varje slinga i Java för alternativ loopsyntax.

