Rekursion Fibonacci



  • int zaehler1=1;
    int zaehler2=1;
    int fib(int zahl) {
         cout <<zaehler1<<". "<< "Aufruf von fib( "<< zahl << ") - ";
         cout<<zaehler2<<". Aufruf insgesamt"<<endl;
         zaehler2++;
        if (zahl == 0) { 
            return 0;
        }
    
        if (zahl == 1) { 
            return 1;
        } else {
            return fib(zahl - 1) + fib(zahl - 2);
        }
    
    }
    

    Hier meine rekursive Funktion zum berechnen der Fibonacci zahlen. Das zählen wie oft die funktion aufgerufen wurde habe ich ohne Probleme geschafft, nur wie schaffe ich es jetzt zu zählen wie oft z.B. fib(5) oder fib(2) aufgerufen wurde?


  • Mod

    Brauchst du nicht zu zählen, geht analytisch. F\_n = F\_{k-1}F_{n-k} + F_{k}F_{n-k+1} \implies F\_n = F\_4F_{n-5} + F\_5F\_{n-4}, i.e. fib(5) sollte Fn4F_{n-4} mal aufgerufen werden (für n5n\geq5, versteht sich). Letzteres kannst du dann mit einer effizienten Implementierung berechnen.

    Falls du obiges nachweisen möchtest, kannst du eine Map verwenden (folgendes funktioniert nicht für k=0k=0):

    #include <iostream>
    #include <map>
    
    using call_counter = std::map<int, int>;
    
    int fib(unsigned zahl, call_counter& c) {
    	c[zahl]++;
    	if (zahl < 2)
    		return zahl;
    
    	return fib(zahl - 1, c) + fib(zahl - 2, c);
    }
    
    int main() {
    	call_counter m;
    	fib(9, m);
    	std::cout << m[5];
    }
    


  • Was muss ich nun in meinen code schreiben komme nicht ganz dahinter was du meinst ich brauche in meiner ausgabe folgendes:

    1. Aufruf von fib(5) - 1. Aufruf insgesamt
    1. Aufruf von fib(4) - 2. Aufruf insgesamt
    1. Aufruf von fib(3) - 3. Aufruf insgesamt
    1. Aufruf von fib(2) - 4. Aufruf insgesamt
    1. Aufruf von fib(1) - 5. Aufruf insgesamt
    1. Aufruf von fib(0) - 6. Aufruf insgesamt
    2. Aufruf von fib(1) - 7. Aufruf insgesamt
    2. Aufruf von fib(2) - 8. Aufruf insgesamt
    3. Aufruf von fib(1) - 9. Aufruf insgesamt
    2. Aufruf von fib(0) - 10. Aufruf insgesamt
    2. Aufruf von fib(3) - 11. Aufruf insgesamt
    3. Aufruf von fib(2) - 12. Aufruf insgesamt
    4. Aufruf von fib(1) - 13. Aufruf insgesamt
    3. Aufruf von fib(0) - 14. Aufruf insgesamt
    5. Aufruf von fib(1) - 15. Aufruf insgesamt
    

    die erste spalte brauche ich


  • Mod

    Lapa1503 schrieb:

    die erste spalte brauche ich

    😕 Lass den Rest einfach weg?


  • Mod

    SeppJ schrieb:

    Lapa1503 schrieb:

    die erste spalte brauche ich

    😕 Lass den Rest einfach weg?

    Er kann diese Ausgabe noch nicht erzeugen, sondern möchte.


Anmelden zum Antworten