Leg deze eenvoudige code uit:
public int fibonacci(int n) {
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
Ik ben in de war met de laatste regel, vooral omdat als n = 5 bijvoorbeeld, dan fibonacci(4) + fibonacci(3) zou worden aangeroepen enzovoort, maar ik begrijp niet hoe dit algoritme de waarde bij index berekent 5 volgens deze methode. Graag uitgebreid uitleggen!
Antwoord 1, autoriteit 100%
In de fibonacci-reeks is elk item de som van de vorige twee. Dus je hebt een recursief algoritme geschreven.
Dus,
fibonacci(5) = fibonacci(4) + fibonacci(3)
fibonacci(3) = fibonacci(2) + fibonacci(1)
fibonacci(4) = fibonacci(3) + fibonacci(2)
fibonacci(2) = fibonacci(1) + fibonacci(0)
Nu ken je fibonacci(1)==1 and fibonacci(0) == 0al. U kunt dus later de andere waarden berekenen.
Nu,
fibonacci(2) = 1+0 = 1
fibonacci(3) = 1+1 = 2
fibonacci(4) = 2+1 = 3
fibonacci(5) = 3+2 = 5
En uit de fibonacci-reeks 0,1,1,2,3,5,8,13,21....kunnen we zien dat voor 5th elementde fibonacci-reeks retourneert 5.
Kijk hier voor Recursie-zelfstudie.
Antwoord 2, autoriteit 31%
Er zijn twee problemen met uw code:
- Het resultaat wordt opgeslagen in int die alleen de eerste 48 fibonacci-getallen aankan, daarna is het gehele min-bit en het resultaat verkeerd.
- Maar u kunt nooit fibonacci(50) uitvoeren.
De code
fibonacci(n - 1) + fibonacci(n - 2)
is heel verkeerd.
Het probleem is dat het fibonacci niet 50 keer aanroept, maar veel meer.
Eerst roept het fibonacci(49)+fibonacci(48),
volgende fibonacci(48)+fibonacci(47) en fibonacci(47)+fibonacci(46)
Elke keer werd het fibonacci(n) erger, dus de complexiteit is exponentieel.
De benadering van niet-recursieve code:
double fibbonaci(int n){
double prev=0d, next=1d, result=0d;
for (int i = 0; i < n; i++) {
result=prev+next;
prev=next;
next=result;
}
return result;
}
Antwoord 3, autoriteit 24%
In pseudo-code, waarbij n = 5, gebeurt het volgende:
fibonacci(4) + fibonnacci(3)
Dit valt uiteen in:
(fibonacci(3) + fibonnacci(2)) + (fibonacci(2) + fibonnacci(1))
Dit valt uiteen in:
(((fibonacci(2) + fibonnacci(1)) + ((fibonacci(1) + fibonnacci(0))) + (((fibonacci(1) + fibonnacci(0)) + 1))
Dit valt uiteen in:
((((fibonacci(1) + fibonnacci(0)) + 1) + ((1 + 0)) + ((1 + 0) + 1))
Dit valt uiteen in:
((((1 + 0) + 1) + ((1 + 0)) + ((1 + 0) + 1))
Dit resulteert in: 5
Aangezien de fibonnacci-reeks 1 1 2 3 5 8 …is, is het 5e element 5. U kunt dezelfde methode gebruiken om de andere iteraties te achterhalen.
Antwoord 4, autoriteit 8%
U kunt uw functie ook als volgt vereenvoudigen:
public int fibonacci(int n) {
if (n < 2) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
Antwoord 5, autoriteit 7%
Recursie kan soms moeilijk te begrijpen zijn. Evalueer het gewoon op een stuk papier voor een klein aantal:
fib(4)
-> fib(3) + fib(2)
-> fib(2) + fib(1) + fib(1) + fib(0)
-> fib(1) + fib(0) + fib(1) + fib(1) + fib(0)
-> 1 + 0 + 1 + 1 + 0
-> 3
Ik weet niet zeker hoe Java dit evalueert, maar het resultaat zal hetzelfde zijn.
Antwoord 6, autoriteit 5%
F(n)
/ \
F(n-1) F(n-2)
/ \ / \
F(n-2) F(n-3) F(n-3) F(n-4)
/ \
F(n-3) F(n-4)
Belangrijk om op te merken is dat dit algoritme exponentieel is omdat het het resultaat van eerder berekende getallen niet opslaat. bv F(n-3) wordt 3 keer aangeroepen.
Raadpleeg voor meer details het algoritme van dasgupta hoofdstuk 0.2
Antwoord 7, autoriteit 5%
De meeste antwoorden zijn goed en leggen uit hoe de recursie in fibonacci werkt.
Hier is een analyse van de drie technieken die ook recursie omvat:
- For Loop
- Recursie
- Memo’s
Hier is mijn code om ze alle drie te testen:
public class Fibonnaci {
// Output = 0 1 1 2 3 5 8 13
static int fibMemo[];
public static void main(String args[]) {
int num = 20;
System.out.println("By For Loop");
Long startTimeForLoop = System.nanoTime();
// returns the fib series
int fibSeries[] = fib(num);
for (int i = 0; i < fibSeries.length; i++) {
System.out.print(" " + fibSeries[i] + " ");
}
Long stopTimeForLoop = System.nanoTime();
System.out.println("");
System.out.println("For Loop Time:" + (stopTimeForLoop - startTimeForLoop));
System.out.println("By Using Recursion");
Long startTimeRecursion = System.nanoTime();
// uses recursion
int fibSeriesRec[] = fibByRec(num);
for (int i = 0; i < fibSeriesRec.length; i++) {
System.out.print(" " + fibSeriesRec[i] + " ");
}
Long stopTimeRecursion = System.nanoTime();
System.out.println("");
System.out.println("Recursion Time:" + (stopTimeRecursion -startTimeRecursion));
System.out.println("By Using Memoization Technique");
Long startTimeMemo = System.nanoTime();
// uses memoization
fibMemo = new int[num];
fibByRecMemo(num-1);
for (int i = 0; i < fibMemo.length; i++) {
System.out.print(" " + fibMemo[i] + " ");
}
Long stopTimeMemo = System.nanoTime();
System.out.println("");
System.out.println("Memoization Time:" + (stopTimeMemo - startTimeMemo));
}
//fib by memoization
public static int fibByRecMemo(int num){
if(num == 0){
fibMemo[0] = 0;
return 0;
}
if(num ==1 || num ==2){
fibMemo[num] = 1;
return 1;
}
if(fibMemo[num] == 0){
fibMemo[num] = fibByRecMemo(num-1) + fibByRecMemo(num -2);
return fibMemo[num];
}else{
return fibMemo[num];
}
}
public static int[] fibByRec(int num) {
int fib[] = new int[num];
for (int i = 0; i < num; i++) {
fib[i] = fibRec(i);
}
return fib;
}
public static int fibRec(int num) {
if (num == 0) {
return 0;
} else if (num == 1 || num == 2) {
return 1;
} else {
return fibRec(num - 1) + fibRec(num - 2);
}
}
public static int[] fib(int num) {
int fibSum[] = new int[num];
for (int i = 0; i < num; i++) {
if (i == 0) {
fibSum[i] = i;
continue;
}
if (i == 1 || i == 2) {
fibSum[i] = 1;
continue;
}
fibSum[i] = fibSum[i - 1] + fibSum[i - 2];
}
return fibSum;
}
}
Dit zijn de resultaten:
By For Loop
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
For Loop Time:347688
By Using Recursion
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Recursion Time:767004
By Using Memoization Technique
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Memoization Time:327031
Daarom kunnen we zien dat memo’s de beste tijdgewijsen voor lusovereenkomsten nauw zijn.
Maar recursie duurt het langst en misschien moet je het in het echte leven vermijden. Als u recursie gebruikt, zorg er dan voor dat u de oplossing optimaliseert.
Antwoord 8, autoriteit 4%
Dit is de beste video die ik heb gevonden die recursie en de Fibonacci-reeks in Java volledig verklaart.
http://www.youtube.com/watch?v=dsmBRUCzS7k
Dit is zijn code voor de reeks en zijn uitleg is beter dan ik ooit zou kunnen doen om het uit te typen.
public static void main(String[] args)
{
int index = 0;
while (true)
{
System.out.println(fibonacci(index));
index++;
}
}
public static long fibonacci (int i)
{
if (i == 0) return 0;
if (i<= 2) return 1;
long fibTerm = fibonacci(i - 1) + fibonacci(i - 2);
return fibTerm;
}
Antwoord 9, autoriteit 3%
Voor een recursieve fibonacci-oplossing is het belangrijk om de uitvoer van kleinere fibonacci-getallen op te slaan, terwijl de waarde van een groter getal wordt opgehaald. Dit wordt “Memoiseren” genoemd.
Hier is een code die de kleinere fibonacci-waarden onthoudt, terwijl een groter fibonacci-getal wordt opgehaald. Deze code is efficiënt en doet niet meerdere verzoeken van dezelfde functie.
import java.util.HashMap;
public class Fibonacci {
private HashMap<Integer, Integer> map;
public Fibonacci() {
map = new HashMap<>();
}
public int findFibonacciValue(int number) {
if (number == 0 || number == 1) {
return number;
}
else if (map.containsKey(number)) {
return map.get(number);
}
else {
int fibonacciValue = findFibonacciValue(number - 2) + findFibonacciValue(number - 1);
map.put(number, fibonacciValue);
return fibonacciValue;
}
}
}
Antwoord 10, autoriteit 2%
in de fibonacci-reeks zijn de eerste twee items 0 en 1, elk ander item is de som van de twee voorgaande items. dat wil zeggen:
0 1 1 2 3 5 8…
dus het 5e item is de som van het 4e en het 3e item.
Antwoord 11, autoriteit 2%
Michael Goodrich et al. bieden een heel slim algoritme in gegevensstructuren en algoritmen in Java, voor het recursief oplossen van fibonacci in lineaire tijd door een array van [fib(n), fib(n-1)] terug te geven.
public static long[] fibGood(int n) {
if (n < = 1) {
long[] answer = {n,0};
return answer;
} else {
long[] tmp = fibGood(n-1);
long[] answer = {tmp[0] + tmp[1], tmp[0]};
return answer;
}
}
Dit levert fib(n) = fibGood(n)[0] op.
Antwoord 12, autoriteit 2%
Hier is O(1) oplossing:
private static long fibonacci(int n) {
double pha = pow(1 + sqrt(5), n);
double phb = pow(1 - sqrt(5), n);
double div = pow(2, n) * sqrt(5);
return (long) ((pha - phb) / div);
}
Binet’s Fibonacci-getalformulegebruikt voor bovenstaande implementatie.
Voor grote invoer kan longworden vervangen door BigDecimal.
Antwoord 13, autoriteit 2%
Een Fibbonacci-reeks is er een die het resultaat van een getal optelt wanneer het wordt toegevoegd aan het vorige resultaat, beginnend met 1.
so.. 1 + 1 = 2
2 + 3 = 5
3 + 5 = 8
5 + 8 = 13
8 + 13 = 21
Zodra we begrijpen wat Fibbonacci is, kunnen we beginnen met het ontleden van de code.
public int fibonacci(int n) {
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
De eerste if-instructie controleert op een basisgeval, waar de lus kan uitbreken. Het else if-statement hieronder doet hetzelfde, maar het zou zo kunnen worden herschreven…
public int fibonacci(int n) {
if(n < 2)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
Nu er een basisgeval is vastgesteld, moeten we de call-stack begrijpen. Je eerste call naar “fibonacci” zal de laatste zijn die op de stack (volgorde van calls) wordt opgelost, aangezien ze worden opgelost in de omgekeerde volgorde van waarin ze waren genaamd. De laatst aangeroepen methode wordt eerst opgelost, dan de laatste die daarvoor wordt aangeroepen enzovoort…
Dus alle oproepen worden eerst gedaan voordat er iets met die resultaten wordt “berekend”. Bij een input van 8 verwachten we een output van 21 (zie bovenstaande tabel).
fibonacci(n – 1) blijft aangeroepen totdat het het basisgeval bereikt, dan wordt fibonacci(n – 2) aangeroepen totdat het het basisgeval bereikt. Wanneer de stapel het resultaat in omgekeerde volgorde begint op te tellen, zal het resultaat zo zijn…
1 + 1 = 1 ---- last call of the stack (hits a base case).
2 + 1 = 3 ---- Next level of the stack (resolving backwards).
2 + 3 = 5 ---- Next level of the stack (continuing to resolve).
Ze blijven bubbelen (achteruit oplossen) totdat de juiste som wordt teruggegeven aan de eerste call in de stapel en zo krijg je je antwoord.
Dat gezegd hebbende, is dit algoritme zeer inefficiënt omdat het hetzelfde resultaat berekent voor elke branche die de code in splitst. Een veel betere aanpak is een “bottom-up” wanneer er geen memoisatie (caching) of recursie (diepe oproepstack) vereist is.
Zoals …
static int BottomUpFib(int current)
{
if (current < 2) return current;
int fib = 1;
int last = 1;
for (int i = 2; i < current; i++)
{
int temp = fib;
fib += last;
last = temp;
}
return fib;
}
14
De meeste oplossingen die hier worden aangeboden, worden in O (2 ^ n) complexiteit uitgevoerd. Het herberekenen van identieke knooppunten in recursieve boom is inefficiënt en verspilt CPU-cycli.
We kunnen memoisatie gebruiken om de Fibonacci-functie uit te voeren in O (N) -tijd
public static int fibonacci(int n) {
return fibonacci(n, new int[n + 1]);
}
public static int fibonacci(int i, int[] memo) {
if (i == 0 || i == 1) {
return i;
}
if (memo[i] == 0) {
memo[i] = fibonacci(i - 1, memo) + fibonacci(i - 2, memo);
}
return memo[i];
}
Als we de bottom-up dynamische programmeerroute volgen, is onder de code eenvoudig genoeg om Fibonacci te berekenen:
public static int fibonacci1(int n) {
if (n == 0) {
return n;
} else if (n == 1) {
return n;
}
final int[] memo = new int[n];
memo[0] = 0;
memo[1] = 1;
for (int i = 2; i < n; i++) {
memo[i] = memo[i - 1] + memo[i - 2];
}
return memo[n - 1] + memo[n - 2];
}
15
Waarom dit antwoord anders is
elk ander antwoord:
- prints in plaats van retourneren
- Maakt 2 recursieve oproepen per iteratie
- negeert de vraag met behulp van lussen
(terzijde: geen van deze is eigenlijk efficiënt; gebruik Binet’s formule om rechtstreeks de N TH Term)
te berekenen
Tail Recursieve FIB
Hier is een recursieve aanpak die een dubbele recursieve oproep vermijdt door zowel het vorige antwoord als de een daarvoor door te geven.
private static final int FIB_0 = 0;
private static final int FIB_1 = 1;
private int calcFibonacci(final int target) {
if (target == 0) { return FIB_0; }
if (target == 1) { return FIB_1; }
return calcFibonacci(target, 1, FIB_1, FIB_0);
}
private int calcFibonacci(final int target, final int previous, final int fibPrevious, final int fibPreviousMinusOne) {
final int current = previous + 1;
final int fibCurrent = fibPrevious + fibPreviousMinusOne;
// If you want, print here / memoize for future calls
if (target == current) { return fibCurrent; }
return calcFibonacci(target, current, fibCurrent, fibPrevious);
}
16
Het is een basisreeks die weergeeft of een uitvoer van
1 1 2 3 5 8
Het is een sequentie die de som van het vorige nummer het huidige nummer vervolgens wordt weergegeven.
Probeer Link onder Java Recursieve Fibonacci Sequence Tutorial te bekijken
public static long getFibonacci(int number){
if(number<=1) return number;
else return getFibonacci(number-1) + getFibonacci(number-2);
}
Klik hier Bekijk Java Recursieve Fibonacci Sequence Tutorial voor lepelvoeding
17
Ik denk dat dit een eenvoudige manier is:
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int number = input.nextInt();
long a = 0;
long b = 1;
for(int i = 1; i<number;i++){
long c = a +b;
a=b;
b=c;
System.out.println(c);
}
}
}
18
RANRAG (geaccepteerd) antwoord zal prima werken, maar dat is geen geoptimaliseerde oplossing tot en tenzij het wordt opgeslagen zoals uitgelegd in Anil Antwoord.
Voor recursief Overweeg onderbenadering, methode Oproepen van TestFibonaccizijn minimaal
public class TestFibonacci {
public static void main(String[] args) {
int n = 10;
if (n == 1) {
System.out.println(1);
} else if (n == 2) {
System.out.println(1);
System.out.println(1);
} else {
System.out.println(1);
System.out.println(1);
int currentNo = 3;
calFibRec(n, 1, 1, currentNo);
}
}
public static void calFibRec(int n, int secondLast, int last,
int currentNo) {
if (currentNo <= n) {
int sum = secondLast + last;
System.out.println(sum);
calFibRec(n, last, sum, ++currentNo);
}
}
}
19
public class febo
{
public static void main(String...a)
{
int x[]=new int[15];
x[0]=0;
x[1]=1;
for(int i=2;i<x.length;i++)
{
x[i]=x[i-1]+x[i-2];
}
for(int i=0;i<x.length;i++)
{
System.out.println(x[i]);
}
}
}
Antwoord 20
Door een interne ConcurrentHashMap te gebruiken die theoretisch mogelijk zou kunnen zijn
deze recursieve implementatie om correct te werken in een multithreaded
omgeving, heb ik een fib-functie geïmplementeerd die zowel BigInteger
en recursie. Het duurt ongeveer 53 ms om de eerste 100 fib-nummers te berekenen.
private final Map<BigInteger,BigInteger> cacheBig
= new ConcurrentHashMap<>();
public BigInteger fibRecursiveBigCache(BigInteger n) {
BigInteger a = cacheBig.computeIfAbsent(n, this::fibBigCache);
return a;
}
public BigInteger fibBigCache(BigInteger n) {
if ( n.compareTo(BigInteger.ONE ) <= 0 ){
return n;
} else if (cacheBig.containsKey(n)){
return cacheBig.get(n);
} else {
return
fibBigCache(n.subtract(BigInteger.ONE))
.add(fibBigCache(n.subtract(TWO)));
}
}
De testcode is:
@Test
public void testFibRecursiveBigIntegerCache() {
long start = System.currentTimeMillis();
FibonacciSeries fib = new FibonacciSeries();
IntStream.rangeClosed(0,100).forEach(p -&R {
BigInteger n = BigInteger.valueOf(p);
n = fib.fibRecursiveBigCache(n);
System.out.println(String.format("fib of %d is %d", p,n));
});
long end = System.currentTimeMillis();
System.out.println("elapsed:" +
(end - start) + "," +
((end - start)/1000));
}
en uitvoer van de test is: . . . . . fib van 93 is 12200160415121876738 FIB van 94 is 19740274219868223167 FIB van 95 is 31940434634990099905 FIB van 96 is 51680708854858323072 FIB van 97 is 83621143489848422977 FIB van 98 is 135301852344706746049 FIB van 99 is 218922995834555169026 FIB van 100 is 354224848179261915075 Verstreken: 58,0
21
Hier is een één regel FeBonacci recursief:
public long fib( long n ) {
return n <= 0 ? 0 : n == 1 ? 1 : fib( n - 1 ) + fib( n - 2 );
}
22
Gewoon om aan te vullen, als u meerdere cijfers wilt berekenen, moet u Biginteger gebruiken.
een iteratief voorbeeld.
import java.math.BigInteger;
class Fibonacci{
public static void main(String args[]){
int n=10000;
BigInteger[] vec = new BigInteger[n];
vec[0]=BigInteger.ZERO;
vec[1]=BigInteger.ONE;
// calculating
for(int i = 2 ; i<n ; i++){
vec[i]=vec[i-1].add(vec[i-2]);
}
// printing
for(int i = vec.length-1 ; i>=0 ; i--){
System.out.println(vec[i]);
System.out.println("");
}
}
}
23
http://en.wikipedia.org/wiki/fibonacci_number in meer details
public class Fibonacci {
public static long fib(int n) {
if (n <= 1) return n;
else return fib(n-1) + fib(n-2);
}
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
for (int i = 1; i <= N; i++)
System.out.println(i + ": " + fib(i));
}
}
Maak het zo eenvoudig als dat nodig is, niet nodig om te gebruiken tijdens de lus en andere lus
24
public class FibonacciSeries {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
for (int i = 0; i <= N; i++) {
int result = fibonacciSeries(i);
System.out.println(result);
}
scanner.close();
}
private static int fibonacciSeries(int n) {
if (n < 0) {
return 1;
} else if (n > 0) {
return fibonacciSeries(n - 1) + fibonacciSeries(n - 2);
}
return 0;
}
}
25
Een fibbonacci-sequentie is er een die het resultaat van een getal bedraagt
Dan hebben we toegevoegd aan het vorige resultaat, we moeten van 1 zijn begonnen.
Ik probeerde een oplossing te vinden op basis van algoritme, dus ik bouw de recursieve code, merkte dat ik het vorige nummer bewaar en ik heb de positie veranderd. Ik zoek de fibbonacci-sequentie van 1 tot 15.
public static void main(String args[]) {
numbers(1,1,15);
}
public static int numbers(int a, int temp, int target)
{
if(target <= a)
{
return a;
}
System.out.print(a + " ");
a = temp + a;
return numbers(temp,a,target);
}
Antwoord 26
Probeer dit
private static int fibonacci(int n){
if(n <= 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
Antwoord 27
public static long fib(int n) {
long population = 0;
if ((n == 0) || (n == 1)) // base cases
{
return n;
} else // recursion step
{
population+=fib(n - 1) + fib(n - 2);
}
return population;
}
Antwoord 28
Eenvoudige Fibonacci
public static void main(String[]args){
int i = 0;
int u = 1;
while(i<100){
System.out.println(i);
i = u+i;
System.out.println(u);
u = u+i;
}
}
}
Antwoord 29
@chro is perfect, maar hij/zij toont niet de juiste manier om dit recursief te doen. Hier is de oplossing:
class Fib {
static int count;
public static void main(String[] args) {
log(fibWrong(20)); // 6765
log("Count: " + count); // 21891
count = 0;
log(fibRight(20)); // 6765
log("Count: " + count); // 19
}
static long fibRight(long n) {
return calcFib(n-2, 1, 1);
}
static long fibWrong(long n) {
count++;
if (n == 0 || n == 1) {
return n;
} else if (n < 0) {
log("Overflow!");
System.exit(1);
return n;
} else {
return fibWrong(n-1) + fibWrong(n-2);
}
}
static long calcFib(long nth, long prev, long next) {
count++;
if (nth-- == 0)
return next;
if (prev+next < 0) {
log("Overflow with " + (nth+1)
+ " combinations remaining");
System.exit(1);
}
return calcFib(nth, next, prev+next);
}
static void log(Object o) {
System.out.println(o);
}
}