Buch Cover Buch Cover Buch Cover Buch Cover

Web-Code: - Webcode Help

Fibonacci (Rekursion)

Beim Versuch, eine Kaninchenpopulation vorauszusagen, benutzte Fibonaccieigentlich Leonardo da Pisa (in Pisa um 1180-1250); bedeutender Mathematiker des Mittelalters die nach ihm benannte Folge. Es stellte sich heraus, dass diese mathematische Folge eine sehr gute Näherung der Wirklichkeit war.

Die Fibonacci-Folge liest sich wie folgt: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... und bezeichnet die Anzahl der Kaninchenpaare in jedem Monat. Dabei ist jeder Eintrag die Summe der beiden Vorgänger (bitte nachprüfen). Schreiben Sie eine rekursive Funktion zum Berechnen des i-ten Eintrags in der Folge. Für i = 1 und i = 2 liefert die Funktion einfach 1. Ist jedoch i > 2, so liefert sie einfach die Summe der beiden Vorgänger.

Option: Schreiben Sie die Funktion auch iterativ und vergleichen Sie die Laufzeiten mittels dem Auslesen der Systemzeit.

1 Kommentare

Bitte melde dich an um einen Kommentar abzugeben

Kommentare (1)

gressly 13. Februar 2012 16:28   reply report
Selbstverständlich kann dies auch durch eine Iteration (Schleife) gefunden werden:
f(n) :
a := 1, b := 1
i := 2;
while(i < n) do
next := a+b
a = b
b = next
end while
return b

Ebenso gibt es eine geschlossene Formel:
Sei phi := goldener Schnitt := φ = 1/2*(1 + √5)
so ist
f(n) = runden((φ^n)/√5)

4 Lösung(en)

public class Fibonacci {
    public static void main(String[] args) {
        new Fibonacci().top();
    }

    private void top() {
        System.out.println(fib(40));
    }

    private int fib(int i) {
        if (i < 2) {
            return 1;
        }
        return fib(i - 2) + fib(i - 1);
    }
    
}// end of class Fibonacci
                
package ch.programmieraufgaben.rekursion.fibonacci;

public class FibonacciTest {
  public static void main(String[] args) {
    new FibonacciTest().top();
  }
  
  void top() {
      for(int i = 1; i < 20; i++) {
          fibonacciMethodenvergleich(i);
      }
      fibonacciMethodenvergleich(30);
      fibonacciMethodenvergleich(40);
      fibonacciMethodenvergleich(45);  
      fibonacciMethodenvergleich(50);
      fibonacciMethodenvergleich(100);
      fibonacciMethodenvergleich(1000);
  }
  
  void fibonacciMethodenvergleich(int i) {
      int maxRekursiv = 45; // rekursiv mit >50 dauert "ewig" ;-)
      long timeBefore, timeAfter;
      double rekursiv = 0.0;
      if(i <= maxRekursiv) {
        timeBefore = System.currentTimeMillis();
        rekursiv = fibonacciRekursiv(i);
        timeAfter = System.currentTimeMillis();
        ausgabe(i, "Rekursiv", rekursiv, timeBefore, timeAfter);
      }
      
      timeBefore = System.currentTimeMillis();
      double iterativ = fibonacciIterativ(i);
      timeAfter = System.currentTimeMillis();
      ausgabe(i, "Iterativ", iterativ, timeBefore, timeAfter);
      
      timeBefore = System.currentTimeMillis();
      double direkt = fibonacciDirekt(i);
      timeAfter = System.currentTimeMillis();
      ausgabe(i, "Direkt  ", direkt, timeBefore, timeAfter);
      
      if((i <= maxRekursiv) && 
          (((long) iterativ != (long) rekursiv) || 
           ((long) rekursiv != (long) direkt))) {
        System.out.println("Rechenfehler: ");
        System.out.println("   rekursiv = " + rekursiv);
        System.out.println("   iterativ = " + iterativ);
        System.out.println("   direkt   = " + direkt);
      }

  } // end method test()
  
  double fibonacciRekursiv(double i) {
    if(i <= 2) { return 1.0; }
    return fibonacciRekursiv(i-1) + fibonacciRekursiv(i-2);
  }
  
  double fibonacciIterativ(int i) {
    double resultat = 1;
    double letzt    = 1;
    double vorletzt = 1;
    double pos      = 3;
    while(pos <= i) {
      resultat = letzt + vorletzt;
      vorletzt = letzt;
      letzt = resultat;
      pos  = pos + 1;
    }
    return resultat;
  }  
  
  double phi      = 1.6180339887498948482045868343656381177203091798;
  double wurzel5  = 2.2360679774997896964091736687312762354406183596;
  double fibonacciDirekt(int i) {
     double result;
     result = Math.pow(phi, i) / wurzel5;
     if(result < Long.MAX_VALUE) {
         return runden(result);
     }
     return result;  
  }

  private long runden(double result) {
    return (long) (0.5 + result);
  }
  
  private void ausgabe(int in, String methode, double resultat, long timeBefore,
    long timeAfter) {
    System.out.println(methode + " (" +in + ". -> " +
                       (resultat > Long.MAX_VALUE ? resultat : ((long) resultat)) +
                       "  (zeit(ms): " +(timeAfter-timeBefore)+ ")");
  }
  
} // end of class FibonacciTest
                

Lösung von: Philipp Gressly Freimann (SANTIS Training AG)

def fib(i):
	if(i < 2):
		return 1
	return fib(i-2) + fib(i-1)
#~Ruben Sidon (09.12.2018)
                

Lösung von: Ruben Sidon (WRG Bendorf)

#include <stdio.h>

void main(){

int stelle;
int zahl;
int zahl1 = 0;
int zahl2 = 1;
printf("Fibonacci Stelle: ");
scanf("%d", &stelle);

for(int i; i < stelle; i++){
zahl = zahl1 + zahl2;
zahl1 = zahl2;
zahl2 = zahl;
}
printf("Die Zahl an der %d Stelle lautet: %d",stelle , zahl1);
}

                

Lösung von: Fynn Koch (keine)

Aktionen

Bewertung

Durchschnittliche Bewertung:

Eigene Bewertung:
Bitte zuerst anmelden

Meta

Zeit: 2
Schwierigkeit: k.A.
Webcode: xqh4-mv36
Autor: Philipp Gressly Freimann (SANTIS Training AG)

Download PDF

Download ZIP

Zu Aufgabenblatt hinzufügen