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
11 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)
// NET 6.x | C# 10.x | VS-2022
Test(FibItr);
Test(FibRec);
static int FibRec(int n) => n > 1 ? FibRec(n - 1) + FibRec(n- 2) : n;
static int FibItr(int n) {
int t1 = 0, t2 = 1, m = 0;
for (int i = 1; i < n; i++) {
if (i == 1) return t1;
if (i == 2) return t2;
m = t1 + t2;
t1 = t2;
t2 = m;
}
return m;
}
static void Test(Fibo fibo, int n = 40) {
var sw = new System.Diagnostics.Stopwatch();
sw.Start();
for (int i = 0; i < n; i++) fibo(i);
sw.Stop();
Console.WriteLine($"{fibo.Method.Name}: {sw.Elapsed.Milliseconds} ms");
}
delegate int Fibo(int n);
Lösung von: Jens Kelm (@JKooP)
// C++ 17
#include <iostream>
#include <chrono>
#include <iomanip>
using hrc = std::chrono::high_resolution_clock;
using dur_t = std::chrono::duration<double, std::milli>;
typedef void(*ptr_func)(int);
int fib_rec(int n) { return n > 1 ? fib_rec(n - 1) + fib_rec(n - 2) : n; };
int fib_itr(int n) {
auto t1{ 0 }, t2{ 1 }, m{ 0 };
for (auto i{ 1 }; i < n; ++i) {
if (i == 1) return t1;
if (i == 2) return t2;
m = t1 + t2;
t1 = t2;
t2 = m;
}
return m;
}
auto get_duration(int n, ptr_func p) {
const auto t_begin{ hrc::now() };
for (auto i{ 0 }; i < n; ++i) p(i);
const auto t_end{ hrc::now() };
const dur_t t_result{ t_end - t_begin };
return t_result.count();
}
int main() {
constexpr auto num{ 40 };
std::cout << std::fixed << std::setprecision(10) << std::showpoint;
const auto f1{ get_duration(num, (ptr_func)fib_itr) };
std::cout << "Iteration: " << f1 << "ms\n";
const auto f2{ get_duration(num, (ptr_func)fib_rec) };
std::cout << "Rekursion: " << f2 << "ms\n";
}
Lösung von: Jens Kelm (@JKooP)
// C++23 | VS-2022
// Lambda; rekursiv
static constexpr auto fibonacci{ [](this auto self, const auto& n) {
if (n < 2) return n;
return self(n - 1) + self(n - 2); } };
Lösung von: Jens Kelm (@JKooP)
// C++14
// eine schnelle rekursive Variante
#include <iostream>
#include <map>
#include <array>
template<typename T>
static const auto fib_rec_fast(const T& n) {
static std::map<T, T>memo{};
T result{ 0 };
if (memo.find(n) != memo.end()) return memo[n];
result = n <= 2 ? 1 : fib_rec_fast(n - 1) + fib_rec_fast(n - 2);
memo.emplace(n, result);
return result;
}
int main() {
std::array<size_t, 5>nums{ 7,13,50,100,200 };
for(const auto& n : nums)
std::cout << n << ": " << fib_rec_fast(n) << "\n";
}
Lösung von: Jens Kelm (@JKooP)
// C++23 | msvc only
// eine schnelle rekursive Lambda-Variante
#include <iostream>
#include <map>
#include <print>
static constexpr auto fib_rec_fast_lambda{ [] <typename T>(this auto self, const T& n) {
static std::map<T, T>memo{};
if (memo.find(n) != memo.end()) return memo[n];
const T result{ n <= 2 ? 1 : self(n - 1) + self(n - 2) };
memo.emplace(n, result);
return result;
} };
int main() {
for (const size_t& n : { 7,13,50,100,200 })
std::print("{}: {}\n", n, fib_rec_fast_lambda(n));
}
Lösung von: Jens Kelm (@JKooP)
Aktionen
Neue Lösung hinzufügen
Bewertung
Durchschnittliche Bewertung:
Meta
| Zeit: | 2 |
| Schwierigkeit: | k.A. |
| Webcode: | xqh4-mv36 |
| Autor: | Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch) |
Kommentare (1)
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)