Counter innerhalb einer Funktion



  • Guten Tag allerseits!

    Nun, mein erstes Semester neigt sich dem Ende zu und eine Aufgabe besteht darin, die Fibonacci-Zahlen per Rekursion zu berechnen, dazu soll noch ein Protokoll geführt werden, welches anzeigt wie oft die Fibonacci-Funktion einer bestimmten Zahl, sprich z.B. der 3. Aufruf von fib(5), und zusätzlich noch ein Counter mitgeführt werden soll, der anzeigt wie oft die Fibonacci Funktion INSGESAMT aufgerufen wurde.

    Die Berechnung der Fibonacci-Zahlen per Rekursion habe ich wie folgt gelöst:

    #include <iostream>
    #include <cstdlib>
    using namespace std;
    
    unsigned long fib(short zahl) {
    
        unsigned long x, y;
    
        if (zahl <= 1) {
            return (zahl);
        } else {
            x = fib(zahl - 1);
            y = fib(zahl - 2);
    
            return (x + y);
        }
    }
    
    int main() {
        short n;
        unsigned long ergebnis;
        cout << "\nBerechnung von Fibonacci-Zahlen mit einem Protokoll:\n";
        cout << "Eingabe: ";
        cin >> n;
        cout << "Protokoll:\n";
        ergebnis = fib(n);
        cout << '\n';
        cout << "\nFib(" << n << ")=" << ergebnis << endl;
    }
    

    Nun habe ich zunächst versucht einen globalen Counter mit einzubauen, welcher alle Aufrufe der Fibonacci-Funktion mitzählt, problematisch ist es in der Hinsicht, dass mir meine "Lösung" des Problems einen Counter mitzählt, er aber in dem Punkt nur die Rekursions-Tiefe zählt und ausgibt, das sieht wie folgt aus:

    #include <iostream>
    #include <cstdlib>
    using namespace std;
    int counter = 0;
    
    unsigned long fib(short xN, int counter) {
    
        unsigned long x, y;
    
        counter++;
    
        cout << counter << ". Aufruf insgesamt" << endl;
    
        if (xN <= 1) {
            return (xN);
        } else {
            x = fib(xN - 1, counter);
            y = fib(xN - 2, counter);
    
            return (x + y);
        }
    }
    
    int main() {
        short n;
        unsigned long ergebnis;
        cout << "\nBerechnung von Fibonacci-Zahlen mit einem Protokoll:\n";
        cout << "Eingabe: ";
        cin >> n;
        cout << "Protokoll:\n";
        ergebnis = fib(n, ::counter);
        cout << '\n';
        cout << "\nFib(" << n << ")=" << ergebnis << endl;
    }
    

    Das sieht dann nach der Programmausführung exakt so aus:

    Berechnung von Fibonacci-Zahlen mit einem Protokoll:
    Eingabe: 5
    Protokoll:
    1. Aufruf insgesamt
    2. Aufruf insgesamt
    3. Aufruf insgesamt
    4. Aufruf insgesamt
    5. Aufruf insgesamt
    5. Aufruf insgesamt
    4. Aufruf insgesamt
    3. Aufruf insgesamt
    4. Aufruf insgesamt
    4. Aufruf insgesamt
    2. Aufruf insgesamt
    3. Aufruf insgesamt
    4. Aufruf insgesamt
    4. Aufruf insgesamt
    3. Aufruf insgesamt

    Fib<5>=5
    Press [Enter] to close the terminal ...

    Nun, hab mir die Rekursivschleife auch mal aufs Papier gezeichnet und den Counter mitzählen lassen in den Einzelaufrufen, da wurde mir schon bewusst was genau da schief läuft, da der Counter nicht global zählt sondern in den einzelnen Rechenvorgängen mitzählt und somit immer soweit zählt, wie die Rekursionstiefe in den jeweiligen Rechenschritten ist.

    Kann mir irgendwer dafür eine Lösung anbieten oder mir eine Hilfestellung liefern, wie ich es schaffe einen globalen Counter mitlaufen zu lassen der jeden Aufruf der Funktion übergibt?

    Ich bedanke mich schonmals dafür!

    Mit freundlichen Grüßen,

    Soulwear



  • Wenn du eine globale Variable benutzen willst, lässt du den Parameter halt weg.



  • Okay, ich musste gerade über mich selbst lachen, habe den Fehler in meiner Denkweise auch direkt verstanden und jetzt klappt das auch so wie ich will mit dem allgemeinen Counter 😃 😃

    Problematisch wird für mich jetzt allerdings trotzdem der andere Counter, der die einzelnen Funktionsaufrufe mitzählen soll, heißt er soll mir folgendes mitzählen:

    Bei fib(5) werden wir folgende Funktionen aufgerufen:

    fib(0) - 3 Mal aufgerufen
    fib(1) - 5 Mal aufgerufen
    fib(2) - 3 Mal aufgerufen
    fib(3) - 1 Mal aufgerufen
    fib(5) - 1 Mal aufgerufen

    Das was ich nun mit Hilfe meiner Papierzeichnung mitgezählt habe sollen für mich nun aber Counter erledigen, nun stell ich mir aber die Frage, wie ich das machen soll? Muss ich eine Anzahl von Countern mitlaufen lassen die der Größe der eingegeben Zahl entsprechen? Oder gibt es eine elegantere Lösung?



  • Soulwear schrieb:

    Muss ich eine Anzahl von Countern mitlaufen lassen die der Größe der eingegeben Zahl entsprechen? Oder gibt es eine elegantere Lösung?

    Naja, du kriegst ja nunmal max. n+1 verschiedene Werte, dann musst auch n+1 Werte irgendwo speichern.
    Ein vector bietet sich an oder vielleicht ne HashMap(n->Anzahl).


Anmelden zum Antworten