Treppenproblem mit java?

Hi sagen wir ich habe eine Treppe mit 8 Stufen, ich soll dann alle möglichen Schritte angeben, wie ich die Treppen besteigen kann und zwar rekursiv...

Und jede Möglichkeit soll ich mit -1 oder -2 darstellen.

Sagen wir mal n=8 wäre die erste Möglihckeit, wenn ich jeweils eine Stufe steige:

-1-1-1-1-1-1-1-1

die zeite

-1-1-1-1-1-1-2

usw. also wenn ich eine Stufe immer steige mach ich -1 hin für eine Stufe wurde gestiegen und wenn ich zwei mache -2 und nun soll man alle Möglichkeiten darstellen, wie man die 8 stufen besteigen kann und das rekursiv ohne Schleifen. Wie soll das gehen, wenn ich der Methode nur n für die Anzahl der Stufen und einen leeren String übergebe?

Answer 1

[TechPech1984]

hier orientier dich an der lösung und erklärung

https://www.geeksforgeeks.org/count-ways-reach-nth-stair-using-step-1-2-3/

Comments

[jdqwio2]

Ja genau, das klappt bei mir nicht. Habe eine void Methode. Die empfängt einen String k und eine Zahl n, für die Anzahl der Treppen. Am Ende mache ich dann:

System.out.println(methodenname(n-1,"-1")+(n-2,"-2")) Und das geht dann bei mir nicht, weil es ein void sei, aber nach der Lösung müsste ich das ja so machen oder :(

[TechPech1984]

@jdqwio2

Void methoden geben nix zurück . ergo kann auch nix ausgegeben werden .

lern nochmal warum es void gibt und warum es andere typen gibt .

du rufst was auf und willst nix zurück haben , ja das geht natürlich nicht, weil System.out.... wil ja auch was ausgeben und wo es nix bekommt da kannste auch nicht erwarten das es kein fehler meldet .

[Destranix]

@jdqwio2

Du übergibst der Methode als String das, was sie printen soll (also das, was du bisher hast) und printest dann eine Zeile aus, wenn du einen Basisfall erreichst.

[jdqwio2]

@Destranix

Genau, aber wenn ich mache methodenname(n-1,"-1) dann drunter eine System.out.print((variablen_name_vom_string) vom String und dann drunter methodenname(n-2,"-2") und wieder System.put.print(variablen_name_vom_string)

bekomme ich auch was ausgegeben nur nicht passend ehrlich gesagt

[Destranix]

@jdqwio2

Wenn du einen Rekursionsaufruf machst, dann ist das kein Basisfall, sondern ein Rekursionsfall.

[TechPech1984]

@jdqwio2

poste den gesamten code , hier irgendwelche zeilen angeben bringt nichts. du scheinst ein generelles problem zu haben , mit java.

https://pastebin.com/

und dann den link posten .

[Destranix]

@jdqwio2

Zur Erklärung ein Beispiel:

public static int fac(int n){
    if(n < 2){
        return 1;//Basisfall
    }else{
        return fac(n - 1) + fac(n - 2);//Rekursionsfall
    }
}

[TechPech1984]

@Destranix

er hat ein komplettes beispiel bekommen das in allen gängigen sprachen verfügbar ist . warum er schwierigkeiten hat , liegt wohl an was anderem .

ich glaub eher ds er variablen und die kapselung nicht verstanden hat .

[Destranix]

@TechPech1984

Ich vermute ja er hat schlicht nicht dne passenden Basisfall. (Soetwas wie 0 statt 1 o.Ä.)

[TechPech1984]

@Destranix

wie gesagt, er hat void, gibt aber was zurück . aber er soll mal lernen hier vollständigen code zu posten .

ob das basis ist oder nciht ist so egal, das ist was für akademiker .

[jdqwio2]

@TechPech1984

https://pastebin.com/pVzQALf9

[jdqwio2]

@Destranix

Genau mit Return ist es ja auch in Ordnung, aber ohne finde ich es doch schwer

[Destranix]

@TechPech1984

Er schreib ja schon, dass da mit void nicht geht als er es erwähnte. Bzw. denke ich die Schwierigkeit besteht darin, zu sehen, dass es noch Lösungen ohne Rückgabewert gibt (was dann am falschem Basisfall liegen würde).

[Destranix]

@jdqwio2

Du musst:

1.) k irgendwo ausprinten (im Basisfall)

2.) k manipulieren, bevor du es an den nächsten Rekursionsaufruf wietergibst.

Zudem kannst du k nicht in den if-Statements vergleichen (und wenn überhaupt, dnan mittels der "equals"-Methode von String).
Bzw. kann dub schon machen, aber es ist besser, wenn du hier Dynamische programmierung anwendest und durch richtige gestaltung des Codes bewirkst, dass das du nur "treppenanzahl" vergleichen musst zur Entscheidung, ob du in einem Basisfall bist oder nicht.

[jdqwio2]

@Destranix

Ach ich Idiot. Da wo überall Treppenanzahl ist steht, muss normalerweise k hin, habe das beim abschreiben verpeilt, weil ich meinen Code nicht kopieren konnte

[Destranix]

@jdqwio2

Warum kannst du den Code nicht kopieren?
Ist aber auch egal, die üblichen Fällke greifen ja auch.

Schau, dass du deinen Code so ummodelst, dass im Rekursionsfall nichts ausgegeben wird, dafür aber ein String übergeben wird, der k entspricht, nur manipuliert (sprich noch mit "-1" oder "-2" hinten angehängt).

[jdqwio2]

@Destranix

ah okay danke

[jdqwio2]

@Destranix

aber klappt irgendwie auch nicht

[jdqwio2]

@TechPech1984

Hab das jetzt richtig gepostet habe da k mit treppenzahl in sysout vertauscht

[Destranix]

@jdqwio2

Wie sieht dein Code denn jetzt aus? (Schau mal, dass du den kopieren kannst irgendwie, ist ja doof, wenn du den jedes Mal abtippen musst.)

[jdqwio2]

@Destranix

Hab den jetzt hier: https://pastebin.com/pVzQALf9

[Destranix]

@jdqwio2

1.) Hast du da noch Fehler drinnen (zwei if-Anweisungen machen keinen Sinn)

2.) Hast du das, was ich dir zusätzlich noch erklärte nur halb umgesetzt. Da musst du schon etwas denken, dmait das funktioniert.

Weißt du denn, was Rekursionsfall und Basisfall sind?

[jdqwio2]

@Destranix

also dachte ja

[Destranix]

@jdqwio2

Wenn du If-Verzweigungen hast, dann entstehen dabei mehrere Fälle. Solche Fälle, in denen ein weiterer Rekursionsaufruf folgt nennt man "Rekursionsfall". Solche, die die Rekursion beenden (indem sie "return" aufrufen o.Ä.) nennt man "Basisfall".

[jdqwio2]

@Destranix

danke

[jdqwio2]

@Destranix

Aber immernoch das gleiche Problem

[Destranix]

@jdqwio2

Wieder dieselbe Frage. Wie sieht der Code jetzt aus?

[jdqwio2]

@Destranix

Der untere Teil, hat sich nur verändert, also das else

treppen(treppenanzahl-1,k+"-1");

String a=s;

System.out.println(" ");

treppen(treppenanzahl-2,k+"-2");

  System.out.println(" ");

System.out.println(a);

Ich bekomme jetzt alle möglichkeiten raus, aber auch irgendetwas dazwischen.

[Destranix]

@jdqwio2

Wenn du dir die prints an der Stelle sparst, dann solltest du eigentlich schon fast die gewünschte Lösung haben (bzw. brauchst du denke ich noch einen basisfall für "treppenanzahl == 0" in dem du nur "k" ausgibst.

[jdqwio2]

@Destranix

Das habe ich gemacht beim Basisfall, aber bekomme trotzdem noch andere Ausgaben dazu

[Destranix]

@jdqwio2

Wie gesagt, die printlns im Rekursionsfall sind zu viel.

[jdqwio2]

@Destranix

treppen(treppenanzahl-1,k+"-1");

String a=s;

System.out.println(" ");

treppen(treppenanzahl-2,k+"-2");

  System.out.print(a);

Jetzt habe ich aber paar zu lange Zeilen

[Destranix]

@jdqwio2

Du hast ja auch nur ein println entfernt. Ich meine:

treppen(treppenanzahl-1,k+"-1");
treppen(treppenanzahl-2,k+"-2");

[jdqwio2]

@Destranix

ICH HABS DANKE DIR!!! MUSSTE EINFACH ALLE ENTFERNEN

[Destranix]

@jdqwio2

String a=k;

System.out.println(k);

Auch das noch weg.

[jdqwio2]

@Destranix

Danke dir, habs :)