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)

6 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 G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

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)

package ch.santis.programmierenlernen.kapitel11;

public class Aufgabe_11_2 {

	public static void main(String[] args) {

		new Aufgabe_11_2().top();
	}
	
	/*
	 * 92 is max. with long data type! (try 73, 78, 83, 87 and 92 (without Recursive1))
	 * 73 = 806515533049393
	 * 78 = 8944394323791464
	 * 83 = 99194853094755497
	 * 87 = 679891637638612258
	 * 92 = 7540113804746346429
	 * 93 = 12200160415121876738 (overextends long data type)
	 * 
	 * CPUIntel(R) Core(TM) i5-3470 CPU @ 3.20GHz
	 * 
	 * A result with 50:
	 * Start: 1584359357337 Fibo1: 12586269025 Nanoseconds: 43363882332 (= 43.36 Seconds!)
	 * Start: 1584359400701 Fibo2: 12586269025 Nanoseconds: 10905
	 * Start: 1584359400701 Fibo3: 12586269025 Nanoseconds: 7377
	 * End  : 1584359400701
	 */
	
	// Fibonacci
	private void top() {
		int monat = 50; //92 is max. with long data type! (try 73, 78, 83, 87 and 92 (without Recursive1))
		
		//Rekursive1 (really goddamn slow)
		System.out.print("Start: " + System.currentTimeMillis());
		long startTime = System.nanoTime();
		long whatever  = fibonacci1(monat);
		System.out.println(" Fibo1: " + whatever + " Nanoseconds: " + (System.nanoTime() - startTime));
		
		//Rekursive2 (Fast)
		int a = 1;
		int b = 0;
		System.out.print("Start: " + System.currentTimeMillis());
		long startTime2 = System.nanoTime();
		long whatever2 = fibonacci2(monat, a, b);
		System.out.println(" Fibo2: " + whatever2 + " Nanoseconds: " + (System.nanoTime() - startTime2));
		
		//Loop (Fast)
		System.out.print("Start: " + System.currentTimeMillis());
		long startTime3 = System.nanoTime();
		long whatever3 = fibonacci3(monat);
		System.out.println(" Fibo3: " + whatever3 + " Nanoseconds: " + (System.nanoTime() - startTime3));
		System.out.print("End  : " + System.currentTimeMillis());
	}

	//Rekursive1 (really goddamn slow)
	public long fibonacci1(int number) {
		if (number == 1 || number == 2) {
			return 1;
		}
		return fibonacci1(number - 1) + fibonacci1(number - 2);
	}
	
	//Rekursive2 (Fast)
	public long fibonacci2(int monat, long a, long b) {
		long c;
		if(monat > 1) {
			c = b;
			b = a;
			a = a + c;
			monat--;
			return fibonacci2(monat, a, b);
		}
		return a;
	}
	
	//Loop (Fast)
	public long fibonacci3(int number) {
		long a = 1;
		long b = 1;
		long c = 1;
		
		for(int i = 2; i < number; i++) {
			c = a + b;
			a = b;
			b = c;
		}
		return c;
	}

}

                

Lösung von: Jan Roth (Santis Training AG)

function nthFibonacci_rec(n) {
  if (n > 2) return nthFibonacci_rec(n - 2) + nthFibonacci_rec(n - 1);
  return 1;
}

function nthFibonacci_itr(n) {
  if (n == 1 || n == 2) return 1;
  let prevPrev = 1, prev = 1, cur;
  for (let i = 2; i < n; i++) {
      cur = prevPrev + prev;
      prevPrev = prev;
      prev = cur;
  }
  return cur;
}

// laufzeitttest
let i;

// iterativ zuerst. mit voller absicht.
console.time('iterativ');                       
for (i = 1; i < 50; i++) nthFibonacci_itr(i);   
console.timeEnd('iterativ');

console.time('rekursiv');
for (i = 1; i < 50; i++) nthFibonacci_rec(i);
console.timeEnd('rekursiv');                                 // lissalanda@gmx.at
                

Lösung von: Lisa Salander (Heidi-Klum-Gymnasium Bottrop)

Aktionen

Bewertung

Durchschnittliche Bewertung:

Eigene Bewertung:
Bitte zuerst anmelden

Meta

Zeit: 2
Schwierigkeit: k.A.
Webcode: xqh4-mv36
Autor: Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

Download PDF

Download ZIP

Zu Aufgabenblatt hinzufügen