Programmieren lernen

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)