Formel Problem

[alex2345]

Schreiben Sie eine Klasse Berechne mit der Methode int f(int k), die für k > 1 folgende Funktion f berechnet:
• f(1) = 0.
• Wenn k gerade, dann f(k) = f(k/2) + 1.
• Wenn k ungerade, dann f(k) = f(3k−1) + 1

public class Berechne
{
    public Berechne()
    {}

    int f(int k)
    {
        if(k == 1)
        {
            return 0;
        }
        if(k%2 == 0)
        {
            System.out.println(k);
            return f(k/2)+1;
        } else {
            System.out.println(k);
            return f(3*k-1)+1;
        }
    }
}

Meine Frage ist nur, da ich hier bei manchen Zahlen einen Stack Overflow bekomme, ob meine Implementierung richtig ist oder ob ich was falsch gemacht habe. Weiß für diese Angabe nämlich leider keine andere Lösung.

 

[Swoop]

 if(k == 1)

k soll doch größer als 1 sein?!
also eher if(k<1)
sonst würde er bei 0 oder -1 auch in den else-Zweig wechseln.

return f(k/2)+1;

f steht für die Methode ?! so wird das doch eine Endlosscheife?!

Grüße Swoop

Edit:

Ahhhh ... ich habs dein StackOverFlow kommt aus dem Grund weil du ja auf k == 1 prüfst. Wenn aber nie 1 raus kommt ist es eine endlosscheife ... Normal sollte es nciht mehr auftreten wenn du dein if zu seinem austauschst...

 

[AmunRa]

Nein das Problem liegt nicht am [c]if (k==1)[/c] sondern daran, das dieser Algorithmus nicht terminiert.
nehmen wir zuerst einmal die Zahl 4 laut Aufgabe:

gerade daher wird f(2) berechnnet und dann f(1) und wir landen bei deiner if-Bedingung. Nun
betrachten wir f(5) ist ungearde, daher wird f(14) berechnet, als naechstes wird f(7) berechnet (unerade) f(20) gerade f(10) gearde f(5) und wie du hier siehst kommt dann eine endlos schleife, daher hast du entweder die Angabe falsch abgeschreibenm oder die Angabe an sich ist falsch,

 

[alex2345]

Danke, hab mal nachgefragt. Bei manchen Zahlen terminiert das Programm wirklich nicht. Man sollte dann den StackOverflow abfangen. Habs dann so gemacht:

public class Berechne
{
    public Berechne()
    {}

    public int f(int k)
    {
        if(k == 1)
        {
            return 0;
        }
        if(k%2 == 0)
        {
            System.out.println(k);
            return f(k/2)+1;
        } else {
            System.out.println(k);
            return f(3*k-1)+1;
        }
    }
    
    public boolean checkF(int f, int n)
    {
        try
        {
            if(f(f) < n)
                return true;
        }
        catch (StackOverflowError t)
        {
            return false;
        }
        return false;
    }
}

 

[langhaar!]

Das ist doch keine Art und Weise...

Sauberer wäre es, eine Schranke vorzugeben.
Wenn z.B. das Programm nach 100 Rekursionen noch nicht terminiert, wird abgebrochen.
Oder merken, welche Zahlen berechnet wurden und bei einem doppelten Auftreten das Programm verlassen.
Evtl. sogar beides.

 

[alex2345]

Schön find ichs auch nicht aber war so gewollt. Hab noch folgenden Text bekommen:
Die Klasse Berechne soll weiters eine Methode
public boolean checkF(int k, int n)
enthalten, die für k > 1 true genau dann zurückliefert, wenn f(k) < n. Die Methode checkF(k,n)
soll auch dann false zurückliefern, wenn f(k) = +unendlich, d.h. wenn die Rekursion für f nicht
terminiert. Das ist möglich, da die Rekursion für f evt. keinen Fortschritt in Richtung Basisfall
macht.

 

[irgendjemand]

du weist schon das StackOverflow ein ERROR ist ... und keine exception

und soweit wie ich das error-handling in java verstanden habe soll man alles was von ERROR erbt sowieso nicht fangen ... sondern nur EXCEPTIONS

Throwable wurde bewusst in Exception und Error unterteilt

Exception sind fehler die im normalen programmfluss auftreten können ... in der regel kann hier aber die ausführung fortgesetzt werden *natürlich auf den fehler entsprechend reagieren*

Error sind fehler welche einen nicht plan-mäßigen ausnahmezustand der gesamten VM beschrieben ... und dienen dazu die VM bei solch "schweren fehlern" bewusst aussteigen zulassen ..

einen ERROR catchen ist SEHR schlechtes design ... wenn euch euer lehrer das beibringt ... aua ... das tut weh ...

also ist an sich der algorythmus nicht ganz durchdacht da er so wie er ist zu StackOverflow führen kann ... wogegen man auf eben des algorythmus eine lösung suchen sollte ... und sicht nicht auf die fehler-behandlung einer programmier-sprache verlassen

 

[alex2345]

Das mit dem StackOverflow ist hier wohl gewollt. Ich selber habe das Fach nicht. Kriege nur die Beispiele von einem Tutor und versuche selber ein bisschen rumzuprogrammieren. Könnte nur versuchen dem Tutor mal zu sagen dass der das dem Professor mitteilt, weil ich glaube nicht dass der auf einen hören wird, der gar nicht bei ihm im Kurs ist.

 

[langhaar!]

Das mit dem StackOverflow ist hier wohl gewollt.

Wie kommst du darauf? In der Aufgabe steht doch, du sollst abfangen, ob die Rekursion terminiert.
Das bedeutet nicht, dass du einen Fehler erzeugst und ignorierst!

Wie du abfragen kannst, ob die Rekursion terminiert (ohne StackOverflow) hatte ich dir doch schon gesagt.

 

[alex2345]

Ja stimmt. War keine schöne Lösung. Hab jetzt die Werte in einer ArrayList abgespeichert und verglichen ob sie schon einmal aufgerufen wurden.

import java.util.*;

public class Berechne
{
    private ArrayList<Integer> liste = new ArrayList<Integer>();
    private int counter = 0;
    
    public Berechne()
    {}

    public int f(int k)
    {
        if(!liste.contains(k))
            liste.add(k);
        if(liste.contains(k))
            return -1;
        if(k == 1)
        {
            return 0;
        }
        if(k%2 == 0)
        {
            return f(k/2)+1;
        } else {
            return f(3*k-1)+1;
        }
    }
    
    public boolean checkF(int k, int n)
    {
        if(f(k) >= 0 && f(k) <= n)
            return true;
        return false;
    }
}

 

[Marcinek]

Ich sehe keine Verbesserung, wenn das klappt, dann doch eher durch zufall ^^

Auf diese Art und Weise verfälscht du doch das Ergebnis, weill alle Methoden im Fehlerfall dann mit -1 rechnen, statt 0.

Ich kann mich nun nicht genuau an die Formel erinnern, aber wir hatten eine ähnliche zu begin des Studiums und das komische daran war, dass sie immer terminierte. Für alle natürlichen Zahlen.

 

[bobbsen]

        if(!liste.contains(k))
            liste.add(k);
        if(liste.contains(k))
            return -1;

gibt die Funktion so nicht immer -1 zurück? ;-)

ich würds mal mit ein bisschen else versuchen

PS: abgesehen davon muss die List eher in die Funktion, nicht in die Klasse, sonst würd f(x) nicht gehen, selbst wenn f(x) davor funktioniert hat (wenn die List nicht geleert wird).

Und in eine Liste hinzufügen, wenn du sie danach eh wegschmeisst, macht auch keinen Sinn

 

[alex2345]

Ok, das mit dem -1 war blödsinn. Else brauch ich hier ja eh nicht da ich nur eine Anweisung beim if habe. Wenn ich die ArrayList in die Funktion gebe wird sie mir bei jedem Aufruf wieder leer erstellt. Dann hab ich doch erst wieder keine Werte die ich verwenden kann. Und als Parameter kann ich sie auch nicht übergeben, da in der Angabe explizit gefordert ist wie die Methode aussehen soll.