Zahlen rekursiv zerlegen und Ziffern addieren

sashady

sashady

Mitglied
Hallo Leute,
ich soll bei einer Aufgabe Zahlen rekursiv zerlegen und die einzelnen Ziffern miteinander addiert ausgeben.
Leider weiß ich noch nicht ganz, wie Rekursionen genau funktionieren, außerdem hab ich gerade gelernt, wie man iterativ denkt, das
rekursive Denken fällt mir allerdings noch schwerer 😀
Könnt ihr mir Denkanstöße geben, wie ich die Aufgabe lösen kann?
 
Die Grund Idee ist die Quersumme zu bekommen

wenn du die Zahl 98765 hast

dann wären so die Aufrufe der Rekursion möglich

98765
9876
987
98
9

dann kommt die Abbruch Bedingung

und dann rechnest du das Vorherige Ergebnis + die Aktuelle Zahl % 10 und returnst das zur vorherigen methode
 
Rekursion ist immer etwas wie:
- Prüfung bin ich fertig? Wenn ja: Schluss machen
- Teilschritt machen und rekursiv Rest abarbeiten

Du hast also eine Zahl wie 123 und sollst die Ziffern getrennt mit + ausgeben: 1+2+3

Da wäre dann die erste Frage, ob Du einen Weg kennst, bei 123 entweder
a) die 1 und dann die 23 zu bekommen (mit jeweils einfachen Operationen, die auch bei mehr Ziffern funktionieren)
b) die 12 und die 3 zu bekommen (wieder mit einfachen Operationen und für beliebig viele Ziffern)
 
blimmelbla hat gesagt.:
Ja man darf sich kein Beispiel an dir nehmen, also einmal die Vorgaben nicht beachten, dann einmal doch. 🙄 Diese "Gradlinigkeit" kennt man doch sonst nur von Politikern...

Die Aufgabe an sich ist natürlich trivial und bedarf keiner weiteren Erklärung:
Java: 
    public static class Rec<T, R> {
        Function<T, R> f;
    }

    public static int digitSumIterative(long l) {
        return String.valueOf(l).chars().map(Character::getNumericValue).sum();
    }

    public static int digitSumRecursive(long l) {
        Rec<Long, Integer> sum = new Rec<>();
        sum.f = i -> i == 0 ? 0 : (int) (sum.f.apply(i / 10) + i % 10);
        return sum.f.apply(l);
    }

    public static void main(String[] args) {
        System.out.println(digitSumIterative(12304));
        System.out.println(digitSumRecursive(12304));
    }
Zum Vergrößern anklicken....
auch wenn deines richtig ist gedenke ich nicht dass das das ziel war des es so zu lösen.. ausserdem gehts einfacher 🙂
 
Gratuliere - Du hast diese schwere Aufgabe lösen können. Hätte ich Dir ja gar nicht zugetraut! Und vor allem wie toll Du es geschafft hast, es noch komplett unnötig zu verkomplizieren! Ja, auf so eine Idee muss man erst einmal kommen!

Und Du glaubst vermutlich auch tatsächlich, dass Du mit Deinen Beiträgen den Fragestellern hilfst, oder?
 
Joreyk hat gesagt.:
Die Grund Idee ist die Quersumme zu bekommen

wenn du die Zahl 98765 hast

dann wären so die Aufrufe der Rekursion möglich

98765
9876
987
98
9

dann kommt die Abbruch Bedingung

und dann rechnest du das Vorherige Ergebnis + die Aktuelle Zahl % 10 und returnst das zur vorherigen methode
Zum Vergrößern anklicken....
ich gedenke das ist der Ansatz den man verfolgen kann der auch für den anspruch passend ist ... bzw den von Kneitzel wo man es umgekehrt macht ist ja beides möglich
 
Joreyk hat gesagt.:
ich gedenke das ist der Ansatz den man verfolgen kann der auch für den anspruch passend ist ... bzw den von Kneitzel wo man es umgekehrt macht ist ja beides möglich
Zum Vergrößern anklicken....
Ich habe zwei Möglichkeiten aufgezeigt ... welche besser ist, muss der TE entscheiden. (wobei ich ja die Frage aufgestellt habe, wie man da einfach was abspalten kann. Die Ziffer vorne wird deutlich komplexer als die hintere, daher bin ich sicher, dass er auch, wenn er meinem Post folgen sollte, auf Deine Lösung kommen dürfte.

blimmelbla hat gesagt.:
Wenn man nach kneitzel geht, dann ist nur sein Blabla richtig...
Zum Vergrößern anklicken....
Wenn Du nichts konstruktives beizutragen hast, dann halt doch einfach die Klappe ... Oder ist das einfach nur wieder "Tobias hat seine Tage und will wieder einen neuen Account erstellen?"
 
Joreyk hat gesagt.:
auch wenn deines richtig ist
Zum Vergrößern anklicken....
Hier ist die Frage, was man als richtig bezeichnet. Mein Anspruch ist ein anderer und daher wäre es in meinen Augen nicht richtig und in einem Code Review würde ich es ablehnen:
- Bezeichner - das ist trivial aber wäre schon ausreichend.
- Wozu die Rect Klasse? Die wird nur an einer Stelle genutzt und da wäre ein Function<...,..> ausreichend.
- Aber wozu braucht man die? Zumal da in jedem Durchlauf die entsprechende Instanz erzeugt wird.
- Und dann sieht man nur, dass er die eigentliche Methode in eine Function<...> steckt, um diese dann aufzurufen.

Also unter dem Strich nichts als ein manuelles Obfuscating. Also ganz offensichtlich in keiner Weise etwas, das dem TE helfen soll.

Und die Logik ist dann auch interessant: Es ist einfach nur trivial, so dass man nicht drüber reden muss (ja, böser TE - warum macht er es nicht einfach ... wie kann man sowas auch nicht sofort verstehen!) und dann baut man so etwas komplexes?

Ich kann das nicht wirklich nachvollziehen. Ich finde es ärgerlich, denn der TE ist mit einem legitimen Anliegen gekommen und dann kommt da jemand, der offensichtlich nicht helfen will.

Das aber einfach nur als eine kleine Erläuterung meiner Sicht darauf. Denn vielleicht ist es für Dich interessant. Aber das Thema Clean Code und so hatten wir ja auch schon in anderen Threads. Aber ich hoffe, dass so eine Bewertung dennoch für Dich interessant ist.
 
kneitzel hat gesagt.:
Hier ist die Frage, was man als richtig bezeichnet. Mein Anspruch ist ein anderer und daher wäre es in meinen Augen nicht richtig und in einem Code Review würde ich es ablehnen:
- Bezeichner - das ist trivial aber wäre schon ausreichend.
- Wozu die Rect Klasse? Die wird nur an einer Stelle genutzt und da wäre ein Function<...,..> ausreichend.
- Aber wozu braucht man die? Zumal da in jedem Durchlauf die entsprechende Instanz erzeugt wird.
- Und dann sieht man nur, dass er die eigentliche Methode in eine Function<...> steckt, um diese dann aufzurufen.

Also unter dem Strich nichts als ein manuelles Obfuscating. Also ganz offensichtlich in keiner Weise etwas, das dem TE helfen soll.

Und die Logik ist dann auch interessant: Es ist einfach nur trivial, so dass man nicht drüber reden muss (ja, böser TE - warum macht er es nicht einfach ... wie kann man sowas auch nicht sofort verstehen!) und dann baut man so etwas komplexes?

Ich kann das nicht wirklich nachvollziehen. Ich finde es ärgerlich, denn der TE ist mit einem legitimen Anliegen gekommen und dann kommt da jemand, der offensichtlich nicht helfen will.

Das aber einfach nur als eine kleine Erläuterung meiner Sicht darauf. Denn vielleicht ist es für Dich interessant. Aber das Thema Clean Code und so hatten wir ja auch schon in anderen Threads. Aber ich hoffe, dass so eine Bewertung dennoch für Dich interessant ist.
Zum Vergrößern anklicken....
ja so eine Bewertung ist immer interessant

mit "richtig" meinte ich dass das ergebnis richtig raus kommt...



ich finde die Beurteilung über "guten Code" gut von Linus Torvalds

er hat ein Beispiel von einer Liste gezeigt und einmal wurde ein Problem mit einem If else gelöst
und einmal wurde es gelöst in einer Zeile Code wo nur der Pointer geändert wurde

beides war richtig nur das mit dem Pointer ändern ist kürzer und einfacher zu verstehen
weil man beim If erstmal überlegen muss ab wann die bedingung richtig ist und dann muss man noch verstehen was in den 2 Fällen gemacht wird

beim pointer ändern gibt es keine Zwei Fälle es passiert immer das gleiche


und für mich ist das halt auch wichtig dass code nicht über komplex ist, tut ja dann im Köpfchen weh wenn man sich da erstmal ein paar stunden rein denken muss 😀


Auch wenn das jetzt vom Thema abgekommen ist hilft es dem TE in Zukunft beim Lernen diese Beurteilungen der Lösungen zu sehen
 
Joreyk hat gesagt.:
beides war richtig nur das mit dem Pointer ändern ist kürzer und einfacher zu verstehen
weil man beim If erstmal überlegen muss ab wann die bedingung richtig ist und dann muss man noch verstehen was in den 2 Fällen gemacht wird
Zum Vergrößern anklicken....
Lustiges Beispiel. In einer Methode mit sprechendem Namen ginge das auch. Zumal ich zu bezweifeln Wage, dass es nebst Linus Torvalds viele Leute gibt die Pointer ändern besser verstehen als if/else
 
Ja, wobei ich das genaue Beispiel nicht kenne, daher ist so ein Urteil nicht möglich.

Aber im Java Umfeld haben wir hier ja auch jetzt eine schöne Vorlage. Da juckt es mir in den Fingern, da ein Codevorschlag zu unterbreiten, wie es auch aussehen könnte. Aber der TE soll ja die Chance behalten, dieses Problem selbst zu lösen. Das halte ich derzeit noch für wichtiger.
 
danke für die bisherigen antworten, ich konnte leider erst jetzt antworten!
mithilfe der % und / denkanstöße sieht mein ansatz bis jetzt so aus:

Java: 
private static int calcCrossSum(int number) {
        if (number == 0) {
            return 0;
        }

        return number % 10 + calcCrossSum(number / 10);
}

die ausgabe ist jedoch 'null'
fehlt mir noch irgendwas?
 
sashady hat gesagt.:
danke für die bisherigen antworten, ich konnte leider erst jetzt antworten!
mithilfe der % und / denkanstöße sieht mein ansatz bis jetzt so aus:

Java: 
private static int calcCrossSum(int number) {
        if (number == 0) {
            return 0;
        }

        return number % 10 + calcCrossSum(number / 10);
}

die ausgabe ist jedoch 'null'
fehlt mir noch irgendwas?
Zum Vergrößern anklicken....
int kann nicht den wert null haben du printlst das falsche aus 🙂
 
Danke für das schnelle Feedback!
Das ist die zugehörige Main-Methode. In der Konsole wird dann null ausgegeben (ausgeschrieben).

Java: 
public static void main(String[] args) {
        System.out.println(calcCrossSum(102));
   
}

Desweiteren kommt in der Konsole folgende Exception:
"Exception in thread "main" java.lang.NullPointerException"
 
Da bitte einmal prüfen, was du wie ausführst. Ich vermute, dass du etwas anderes ausführst und nicht diese main. Wie @Mart ausgeführt hat, kann da nicht null bei raus kommen, da ein int nie null sein kann.
 
Mart hat gesagt.:
kann es sein dass du die falsche methode ausführst bzw die falsche main ausführst ?
Zum Vergrößern anklicken....
Ich habe in der Klasse lediglich die eine main.
Ich habe den Fehler scheinbar gefunden. Es sind in der main noch weitere print-Ausgaben für andere Methoden, die scheinbar den Wert null ausgegeben haben. Wenn ich die auskommentiere, funktioniert die Berechnung einwandfrei.
Danke für die vielen Antworten und hilfreichen Links!
 
Joreyk hat gesagt.:
ausserdem war es nur als biespiel gedacht dass manche lösungen einfacher sind obwohl man 2 mal drüber nachdenken muss..dafür zahlt es sich beim lesen im nachhinein aus
Zum Vergrößern anklicken....
Da jetzt dem TE geholfen ist, möchte ich kurz nochmal einhaken. MMn widerspricht sich das. Wenn ich 2x darüber nachdenken muss, hilft mir das beim Lesen nicht. Ich muss dann jedes Mal 2x darüber nachdenken und mein Team auch.

Oftmals gibt es vermeintlich bessere Lösungen, welche sich dann im nachhinein als schlecht verständlich rausstellen. Um das rauszufinden gibt es Code Reviews.
Ich habe oft die Erfahrung gemacht, dass besonders "kluge" Lösungen nicht von allen Verstanden werden.
 
Mart hat gesagt.:
du könntest deinen Code noch schicker machen mit einem Ternären operator aber das muss nicht sein
Zum Vergrößern anklicken....
Nunja, das ist Ansichtssache.

Ich würde genau die gezeigte Variante bevorzugen. Sauberer Aufbau der Rekursion mit klar erkenntlicher Abbruchbedingung und dann der klare, rekursive Aufruf. Da sieht man alles was wichtig ist auf einem Blick.
 
sashady hat gesagt.:
Java: 
public static void main(String[] args) {
System.out.println(calcCrossSum(102));

}
Desweiteren kommt in der Konsole folgende Exception:
"Exception in thread "main" java.lang.NullPointerException"
Zum Vergrößern anklicken....
Wenn Du Deiner Methode calcCrossSum den Modifizierer static gibst, wird die NullPointerException verschwinden.

Das liegt daran, dass eine nicht statische Methode auf einer Instanz der Klasse aufgerufen werden muss.

Alternativ kannst Du eine Instanz Erzeugen und Verwenden:

[CODE lang="java" title="Aufruf nicht-statische Methode"]public class DeineKlasse{
public static void main(String[] args) {
DeineKlasse deineInstanz = new DeineKlasse();

System.out.println(deineInstanz.calcCrossSum(102));
}

}[/CODE]
 
Wenn man versucht, eine nicht statische Methode aus einer statischen Methode aufzurufen, dann würde sich der Code auch nicht übersetzen lassen. Eine Exception zur Laufzeit (Wie eine NullPointerException) kann dadurch also nicht ausgelöst werden.

Des Weiteren wurde hier auch berichtet, dass "null" ausgegeben wurde. Es lag also keine NPE vor.
 
Der Wert null ist bei mir rausgekommen, weil ich in einer anderen, noch leeren Methode nur ein "return null;" drinnenstehen hatte. In der main standen aber Aufrufe für diese Methode, die dann den Wert null zurückbekommen haben. Ich habe einfach nicht darauf geachtet die Methodenaufrufe in main vorerst auszukommentieren.
 
Wie funktionieren Rekursionen bei Strings? Wenn ich zum Beispiel bei einem String ein Zeichen suchen soll und dieses dann doppelt an der Position ausgegeben werden soll?
Zum Beispiel:
String a = "Coca Cola"
das 'o' soll doppelt wiedergegeben werden, also --> "Cooca Coola"

Ist wahrscheinlich ein dummes Beispiel, ich hoffe ihr versteht, was ich meine 😀
 
Nehmen wir mal "Coca". Der String ist nicht leer, also kann ich ihn in zwei Teile teilen: den letzten Buchstaben und alles, was davor kommt, das wir mal als Präfix bezeichnen. Der letzte Buchstabe wäre "a" und der Präfix "Coc".

Die Verdopplung eines Zeichens z in einem String ist die Konkatenation des Ergebnisses der Verdopplung des Zeichens z im Präfix (hier hast Du Deine Rekursion) mit dem letzten Buchstaben, wobei dieser verdoppelt wird, falls es sich um das Zeichen z handelt. Die Verdopplung des Zeichens z in einem leeren String ist der leere String.

Umsetzung in Code - mal ganz ausführlich.

Für "Verdopplung eines Zeichens z in einem String" können wir sofort eine Methodensignatur angeben:
Java: 
// liefert einen String, bei dem das zeichen im text verdoppelt wurde
String verdopple(String text, char zeichen)

Wir wissen, dass das Ergebnis ein leerer String ist, wenn text leer ist. Das ist die Abbruchbedingung der Rekursion.
Java: 
public String verdopple(String text, char zeichen) {
    if (text.isEmpty()) {
        return "";
    }

Im anderen Fall brauchen wir den Präfix und das letzte Zeichen, denn das Ergebnis ist in jedem Fall zumindest verdopple(prefix, zeichen) + letes Zeichen.

Java: 
public String verdopple(String text, char zeichen) {
    if (text.isEmpty()) {
        return "";
    }
    int letzterIndex = text.length() - 1;
    String prefix = text.substring(0, letzterIndex);
    char letztesZeichen = text.charAt(letzterIndex);
    String ergebnis = verdopple(prefix, zeichen) + letztesZeichen;
}

Zum Schluss müssen wir das letzteZeichen nochmals dranhängen, also verdoppeln, wenn es das gesuchte ist:
Java: 
public String verdopple(String text, char zeichen) {
    if (text.isEmpty()) {
        return "";
    }
    int letzterIndex = text.length() - 1;
    String prefix = text.substring(0, letzterIndex);
    char letztesZeichen = text.charAt(letzterIndex);
    String ergebnis = verdopple(prefix, zeichen) + letztesZeichen;
    if (letztesZeichen == zeichen) {
        ergebnis += letztesZeichen;
    }
    return ergebnis;
}
Das wars auch schon.
 
Danke für deinen Lösungsvorschlag und die gute Erklärung.
Ich habe das sogar gestern selbst lösen können mit folgendem Code:

Java: 
    private static String duplicateSpacesInString(String text) {
        if (text.isEmpty()) {   // abbruchbedinung
            return "";
        }
        if (text.charAt(0) == ' ') {
            return String.valueOf(text.charAt(0)) + text.charAt(0) + duplicateSpacesInString(text.substring(1));
        } else {
            return text.charAt(0) + duplicateSpacesInString(text.substring(1));

        }
    }
   
    public static void main(String[] args) {
    System.out.println(duplicateSpacesInString("Das ist ein Programm"));
      }


Wie findest du die Lösung? Ist es sinnvoll gelöst? 😀
In meiner Aufgabe sollten die Leerzeichen verdoppelt werden, das macht aber ja keinen Unterschied.
 
Ach, das war auch eine Aufgabe... ich dachte, Du wolltest das nur interessehalber wissen, sonst hätte ich Dir keine Lösung gezeigt... aber, wenn Du es eh schon gelöst hattest, dann bin ich schon beruhigt 🙂

Zur Lösung: das ist natürlich der gleiche Ansatz, Du gehst halt von vorne nach hinten (Du hast ein erstes Zeichen und einen Suffix), das spielt aber keine Rolle. Eines würde ich allerdings noch machen. Du kannst den Teil text.charAt(0) + duplicateSpacesInString(text.substring(1)) vor die if-Abfrage ziehen und in einer Variablen speichern, dann hast Du diesen Teil nur einmal im Code und Du sparst Dir auch das valueOf.

Noch eine kleine Anmerkung: sonderlich effizient sind die beiden Ansätze nicht, weil in jeder Iteration neue Objekte erzeugt werden. Das ist hier aber egal, weil es um das Prinzip der Rekursion geht. Außerdem ist bei einer Rekursion in Java sowieso die Frage, ob da Effizienz noch ins Gewicht fällt. Will man es etwas effizienter haben, würde man z. B. einen StringBuilder als weiteren Parameter übergeben, der gefüllt wird; die Methode gibt dann nichts zurück.
 
Ich habe witzigerweise die Lösung selbst gefunden, ca. 30 min nachdem ich die Frage gestellt habe. 🙂
Es hätte mich aber so und so interessiert, da ich noch nicht ganz weiß, wie man Strings genau bearbeiten kann 😀

Okay, ich werde mir das noch ansehen und das noch abändern! Danke für den Tipp!

Ja bei diesen Beispielen geht es ja rein nur darum, dass man versteht wie Rekursionen funktionieren. Dass diese oft nicht sonderlich effizient sind, habe ich schon öfters gehört.
Von StringBuildern habe ich noch nichts gehört, liegt aber vermutlich daran, dass ich im ersten Semester bin und wir bei den absoluten Basics noch sind.
 
Dass rekursive Ansätze in Java nicht sonderlich effizient sind, liegt einfach daran, dass jedesmal ein Methodenaufruf stattfindet. Die sind relativ teuer, weil dabei ein neuer Stackframe eingerichtet werden muss. Aus dem Grund gibt es bei einer Endlosrekursion auch den berühmten Stapelüberlauf (stack overflow), der in Java mit einem StackOverflowError zum Abbruch des Programms führt.

Prinzipiell können Compiler endrekursive Funktionen (das sind solche, bei denen der rekursive Aufruf ganz am Ende stattfindet) automatisch in einen iterativen Ansatz überführen. Diese Optimierung wird von Java jedoch nicht vorgesehen.

Ein StringBuilder ist im Prinzip nichts anderes als ein String, der geändert werden kann (Strings sind in Java unveränderlich).

Java: 
    private static void duplicateSpacesInString(String text, StringBuilder b) {
        if (text.isEmpty()) {   // abbruchbedinung
            return;
        }
        b.append(text.charAt(0) == ' ' ? "  " : text.charAt(0));
        duplicateSpacesInString(text.substring(1), b);
    }
Aufruf:
Java: 
StringBuilder b = new StringBuilder();
duplicatesSpaceInString("Das ist ein Programm", b);
duplicatesSpaceInString("Das ist ein Programm", b); // fügt es ein weiteres Mal an b an
System.out.println(b);
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Arabische Ziffern in römische Ziffern
Antworten: 1
Wie eine Int Zahl in die einzelnen Ziffern zerlegen?
Antworten: 6
Zahl in Ziffern zerlegen
Antworten: 9
Fibo Zahlen:iterativ,rekursiv Anzahl der Additionen zählen
Antworten: 2
Pseudocode: rekursiv/nicht-rekursiv
Antworten: 1

Zurück
Oben