Fibonacci Folge

[JavaStud20]

Hallo,

ich muss eine Aufgabe machen bei der ich die Fibonacci-Folge rekursiv berechne und dabei die Aufrufe von Fi unter der Verwendung vom Array h mitzähle. die rekursive Berechnung funktioniert nur das mit dem mitzählen bekomme ich nicht hin.

 public static BigInteger fiboRekursiv(int number, int[] h) { //??
        if(number == 0)
            return 0;
        if(number == 1)
            return 1;
        
        BigInteger erg = fiboRekursiv(number-1, h) + fiboRekursiv(number-2, h);
        return erg;
        }
    
    private static void haeufigkeitAusgeben(String[] s, int[] h) {
        BarChartUtil.show("Häufigkeit", "n", "Häufigkeit", Arrays.asList(s), toList(h));
    }
    
    public static void main(String[] args) {
        int[] h //??
        fiboRekursiv(N, h);
        String[] label = new String[h.length];
        for(int i = 0; i < label.length; i++) {
            label[i] = "" + i;
        }
        haeufigkeitAusgeben(label, h);
    }
}

 

[berndoa]

irgendwie... kapiere ich gerade nicht ganz was du machen willst. ne fibonaccizahl berechnen ist klar.
aber was meinst du da nun genau mit dem Array, willst du bspw wenn du eine fibonaccizahl wie 5 bestimmen lässt von deiner methode, mitzählen wo oft die funktion aufgerufen wurde?

 

[JavaStud20]

Ja genau.

irgendwie... kapiere ich gerade nicht ganz was du machen willst. ne fibonaccizahl berechnen ist klar.
aber was meinst du da nun genau mit dem Array, willst du bspw wenn du eine fibonaccizahl wie 5 bestimmen lässt von deiner methode, mitzählen wo oft die funktion aufgerufen wurde?

 

[berndoa]

was ich michg erade generell frage , nur so zur vorgehensweise:
du wirfst da ne zahl, bspw. 5 rein.
dann soll dir da die 5. fibonaccizahl berechnet werden sowie angegeben werden wie viele funktionsaufrufe hierfür nötg sind?

 

[kneitzel]

Also vermutlich willst Du mitzählen, wie oft für jede einzelne Zahl fiboRekursiv aufgerufen wurde.

Da muss man sich erst einmal überlegen, was denn da aufgerufen wird. Wenn Du fiboRekursiv von 3 aufrufst, was für Aufrufe bekommst Du dann?
Für 3 -> 2 und 1 -> 1 und 0. Also 0...3 muss das Array unterstützen. Das wäre also eine Länge von n+1.

Und dann kannst Du direkt am Start der Methode das nte Element um 1 hoch zählen.

 

[kneitzel]

was ich michg erade generell frage , nur so zur vorgehensweise:
du wirfst da ne zahl, bspw. 5 rein.
dann soll dir da die 5. fibonaccizahl berechnet werden sowie angegeben werden wie viele funktionsaufrufe hierfür nötg sind?

Ja, spiel es doch einmal durch. Oder schreib einfach mal in der Methode etwas raus, also ein einfaches
System.out.println("Aufruf mit " + number);
direkt als erste Anweisung in der Methode. Das sollte dann das Verständnis bringen.

 

[JavaStud20]

In der Aufgabenstellung steht, dass die Fibonacci-Folge rekursiv berechnet werden soll und die Anzahl der Aufrufe ohne Caching verfolgt werden soll. Also glaube ich mal ja

 

[berndoa]

Ja, spiel es doch einmal durch. Oder schreib einfach mal in der Methode etwas raus, also ein einfaches
System.out.println("Aufruf mit " + number);
direkt als erste Anweisung in der Methode. Das sollte dann das Verständnis bringen.

womit ich eher gerade hadere, ist folgendes:
wenn er die fibonaccizahl bestimmen will, wirfst er bspw. i=3 rein, will also die 3. fibonaccizahl.
und rauskommen sollen im endeffekt 2 werte, nämlich die gesuchte fibonacci zahl UND wie viele funktionsaufrufe nötig waren.
da bekanntermassen java als rückgabetyp aber nur eine sache zulässt, müsste man vermutlich mit einem array oder so arbeiten.

ich gehe ja mal nicht davon aus dass die aufgabe damit zu lösen ist dass man sich mathematisch einfach eine explizite formel für die nötige rekursionstiefe herleitet, sondern da shcon rekursiv "mitgezählt" werden soll oder so

 

[kneitzel]

Nein, der zweite Parameter (h) ist das Array, das die Aufrufe speichern soll. Da das Array ein Referenz-Typ ist, kannst Du die Inhalte verändern und es ist auch außerhalb des Arrays sichtbar. Du kannst nur kein neues Array zuweisen.

Somit ist der Part bereits in dem Code enthalten.

 

[JavaStud20]

Und wie soll ich jetzt weiter verfahren? Stehe echt auf dem Schlauch 😅😅

 

[kneitzel]

int[] h //??

Hier musst Du ein Array mit der richtigen Größe erstellen. (ein Hinweis habe ich ja in meiner ersten Antwort gegeben).

 public static BigInteger fiboRekursiv(int number, int[] h) {
    
     //??
    
     if(number == 0)

Ich habe den Kommentar noch verschoben - da musst du dann etwas mit dem Array h machen.

Wenn man h[i] als Anzahl der Aufrufe mit number = i interpretiert: Was ist dann anzupassen?

 

[berndoa]

Nein, der zweite Parameter (h) ist das Array, das die Aufrufe speichern soll. Da das Array ein Referenz-Typ ist, kannst Du die Inhalte verändern und es ist auch außerhalb des Arrays sichtbar. Du kannst nur kein neues Array zuweisen.

Somit ist der Part bereits in dem Code enthalten.

okay, ich steig hier geistig aus. mir will einfach nicht einleuchten wozu das array da sein soll bzw. was hier gewollt ist

 

[JavaStud20]

for(int i = 0; i <= number; i++) {
    h[i] ++;
}

??

 

[kneitzel]

Der Name h ist natürlich extrem schlecht vorgegeben worden. Ein name wie counter oder so wäre deutlich besser ....

Schau Dir einfach einmal folgendes Beispiel an:

public static void f(int x, int[] results) {
    results[x] ++;
}

public static void main(String[] args) {
    int[] results = new int[1];
    System.out.println(results[0]);   
    f(0, results);
    System.out.println(results[0]);   
}

Ich hoffe, dass ich da jetzt im Forum kein Tippfehler drin habe ... aber es sollte deutlich werden, was passiert:
- ein int Array wird erzeugt (Größe 1 reicht hier)
- Das erste Element wird ausgegeben. (0)
- Nun wird f aufgerufen um das erste Element zu verändern
- Das erste Element wird erneut ausgegeben....

 

[kneitzel]

for(int i = 0; i <= number; i++)

??

Wenn der Code ein Ansatz sein sollte für die notwendige Ergänzung in fiboRekursiv, dann ist der Ansatz schon falsch. Es wird keinerlei Schleife benötigt.

 

[JavaStud20]

Oh ok. Außerdem steht der Fehler: Type mismatch: cannot convert from int to BigInteger. Wie kann ich diesen beheben?

Wenn der Code ein Ansatz sein sollte für die notwendige Ergänzung in fiboRekursiv, dann ist der Ansatz schon falsch. Es wird keinerlei Schleife benötigt.

 

[JavaStud20]

Wenn ich h[ i ]++; in die Methode schreiben, muss ich dann nicht noch i initialisieren?

 

[berndoa]

Der Name h ist natürlich extrem schlecht vorgegeben worden. Ein name wie counter oder so wäre deutlich besser ....

Schau Dir einfach einmal folgendes Beispiel an:

public static void f(int x, int[] results) {
    results[x] ++;
}

public static void main(String[] args) {
    int[] results = new int[1];
    System.out.println(results[0]);  
    f(0, results);
    System.out.println(results[0]);  
}

Ich hoffe, dass ich da jetzt im Forum kein Tippfehler drin habe ... aber es sollte deutlich werden, was passiert:
- ein int Array wird erzeugt (Größe 1 reicht hier)
- Das erste Element wird ausgegeben. (0)
- Nun wird f aufgerufen um das erste Element zu verändern
- Das erste Element wird erneut ausgegeben....

yo, du erhöhst das x'te element um eins. und nu?

 

[kneitzel]

Wenn fiboRekursiv(5, h) aufgerufen wird: Welches Element von h soll denn dann um 1 erhöht werden?
Das auf fiboRekursiv(number, h) übertragen: Welches Element soll um 1 erhöht werden?

Oh ok. Außerdem steht der Fehler: Type mismatch: cannot convert from int to BigInteger. Wie kann ich diesen beheben?

Das ist ein Fehler vom vorgegebenen Code. fiboRekrusiv gibt ein BigInteger zurück und daher gehen gewisse Dinge nicht:
- return 0; bzw. return 1; Hier muss statt einem int ein BigInteger zurück gegeben werden. Also BigInteger.ZERO z.B. oder man nutzt BigInteger.valueOf(...)
- Die Addition geht auch nicht. Operator Overloading hat Java nicht, daher muss hier die add Methode verwendet werden.

 

[kneitzel]

yo, du erhöhst das x'te element um eins. und nu?

Genau, und das ist dann auch außerhalb der Methode sichtbar.

Und nichts anderes wollen wir doch bei fiboRekursiv auch nicht machen. Wir wollen das Element "number" um ein erhöhen, damit wir dann am Ende des rekursiven Laufes wissen, wie oft eine spezifische Zahl als Number aufgerufen wurde.