Negafibonacci Folge berechnen

[SnowDragon]

Hallo, Ich muss die folgende Aufgabe lösen:
vervollständigen Sie die Methode solve() der Klasse Negafibonacci derart, dass sie für die als Parameter übergebene ganze Zahl n das n-te Glied der Folge zurückgibt.
Das ist meine Methode:

public static int solve(int n) {
        // Don't delete!! Tests will fail otherwise
        // Pass object r to other function calls of solve (e.g. for recursion). Do not create other instances of object r
        // Function solve(...) must be recursive, don't implement other recursive helper functions
        //r.check();

        // TODO
        if (n>=0){
           if(n == 0) {
                 return 0;
               } else if (n == 1) {
                 return 1;
               } else {
                  //System.out.println(solve(n-1) + solve(n-2));
                  return solve(n-1) + solve(n-2); //der rekursive Aufruf
               }}
        else{
            if(n == 0) {
                 return 0;
               } else if (n == -1) {
                 return 1;
               } else {
                   if (n%2==0){
                  //System.out.println(solve(n-1) + solve(n-2));
                  return solve(n+1) + solve(n+2);}
                   else{
                       return (solve(n+1) + solve(n+2)); //der rekursive Aufruf
                   }
               }}
        }

Die Methode funktioniert für alle Zahlen, außer negative gerade Zahlen. Bei n=-4 kommt z.B 3 raus statt -3. Das heißt, ich muss den ergebniswert bei negativen geraden Zahlen invertieren, aber wie?

 

[JStein52]

Ich weiss nicht ob es daran liegt aber du fragst oben ab:
if (n>=0) {
....
} else if (n==0) {
...
}
In den unteren Teil kommt er nie rein ! Also in dieses return 0;

Deine Formatierung macht einen ja krank ....

 

[SnowDragon]

doch, wenn n negativ ist

 

[JStein52]

wozu ist diese Unterscheidung gut wenn du eh das selbe machst :

                if (n % 2 == 0) {
                    //System.out.println(solve(n-1) + solve(n-2));
                    return solve(n + 1) + solve(n + 2);
                } else {
                    return (solve(n + 1) + solve(n + 2)); //der rekursive Aufruf
                }

 

[JStein52]

        else{
            if(n == 0) {
                 return 0;  <-------  hier wirst du nie hinkommen
               } else if (n == -1) {
                 return 1;
               } else {

 

[SnowDragon]

wozu ist diese Unterscheidung gut wenn du eh das selbe machst :

                if (n % 2 == 0) {
                    //System.out.println(solve(n-1) + solve(n-2));
                    return solve(n + 1) + solve(n + 2);   <-- hier muss ich was ändern, denke ich. Und zwar so, dass, falls n = -4 nicht wie momentan der fall 3 rauskommt, sondern -3, so wie die negafibonacci Folge definiert ist.
                } else {
                    return (solve(n + 1) + solve(n + 2)); //der rekursive Aufruf
                }

 

[JStein52]

Die Methode funktioniert für alle Zahlen, außer negative gerade Zahlen

Was heisst eigentlich funktioniert nicht ? Was sollte z.B. für n=-5 rauskommen ? Ich habe deinen Code mal bei mir eingebaut und wenn ich keinen Fehler gemacht habe kommt da 5 raus

 

[SnowDragon]

So sollte es eigentlich aussehen:
n=-8 -> -21 bei mir: 21
n=-7 -> 13
n=-6 -> -8 bei mir: 8
n=-5 -> 5
n=-4 -> -3 bei mir: 3
n=-3 -> 2
n=-2 -> -1 bei mir: 2
n=-1 -> 1
n=0 -> 0
n=1 -> 1
n=2 -> 1
n=3 -> 2
n=4 -> 3
n=5 -> 5
n=6 -> 8
n=7 -> 13
n=8 -> 21

 

[prise1993]

Also ich kann dir jetzt nicht sagen wo bei dir der Fehler liegt der Code ist ein bisschen verworren 😉
Das funktioniert:

private static int fiboRec(int n) {
        if (n == 0){
            return 0;
        }else if (n == 1){
            return n;
        }else if (n == -1){
            return n;
        } else if (n > 1){
            return fiboRec(n - 2) + fiboRec(n - 1);
        }else {
            return  fiboRec(n + 2) + fiboRec(n + 1);
        }
    }

Viel Spass damit

 

[SnowDragon]

schöner Code 🙂 ...aber leider funktioniert der nicht ganz. Für n=-7 kommt -13 raus, es sollte aber 13 sein 😉

 

[JStein52]

Viel Spass damit

Ist kein Spass, ich glaube nicht dass das funktioniert

 

[JStein52]

aber leider funktioniert der nicht ganz

Jep, jetzt kommen nur noch negative Zahlen raus.

 

[prise1993]

Warum alterniert die Folge hast du da eine definition?

 

[JStein52]

Hier z.B.

https://de.wikipedia.org/wiki/Fibonacci-Folge

 

[prise1993]

@JStein52 Danke! Hätt ich eigentlich selber gucken können

 private static int fiboRec(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return n;
        } else if (n < 0) {
            return (int)Math.pow(-1,n+1)*fiboRec(-n);
        }
        else {
            return fiboRec(n - 2) + fiboRec(n - 1);
        }
}

Jetzt machts das was es soll

 

[JStein52]

Hätt ich eigentlich selber gucken können

kein Thema. Die Lösung ist gut, die hatte ich auch schon im Kopf, nur noch keine gelegenheit zum Testen

 

[Xyz1]

Wieso nicht einfach so:

    public static int solve(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == +1) {
            return 1;
        }
        if (n < 0) {
            return (n % 2 == 0 ? -1 : +1) * solve(-n);
        }
        return solve(n - 1) + solve(n - 2);
    }

Spart ein read, ein if und das lästige .pow() ...

 

[JStein52]

Spart ein read, ein if und das lästige .pow() ...

Jaaa bis auf das read ? Was meinst du damit ?

 

[Xyz1]

return n;

Ich will ja nicht klugscheißen, aber das liest erst die Variable n und gibt sie dann zurück. Das andere gibt eine Konstante zurück.

 

[SnowDragon]

Vielen Dank an alle für die Hilfe 🙂 ...nur noch eine Frage, was macht denn dieses .pow() ?

 

[Flown]

was macht denn dieses .pow() ?

Es potenziert: base^exponent

 

[SnowDragon]

Achsooo, alles klar 😉

 

[Xyz1]

Ergänzung: .pow() alterniert auch immer, eigentlich nur das LSB prüfen ....

 

[mariane]

... die Fallunterscheidung kommt ganz ohne Rechnen aus. 🙂

... 
return ((n & 1) == 0 ? -solve(-n) : solve(-n));

 

[Xyz1]

... die Fallunterscheidung kommt ganz ohne Rechnen aus. 🙂

Ja, das meinte ich ja, mit LSB betrachten,
NUR, & 1 ist auch Rechnen ...

oder meintest du, & sei schneller als % ? Mikrooptimierung 🙂