Rekursion "Merge" Methode

[SnowDragon]

Hallo zusammen,
Ich muss die folgende Aufgabe lösen, aber ich weiß nicht genau wie ich anfangen soll... Kann mir jemand einen Tipp geben?

Ergänzen sie die Methode merge(). Diese rekursive Methode verschmilzt jeweils benachbarte gleiche Zahlen im übergebe- nen Zahlenarray ns, wobei die Verschmelzung mittels Multiplikation erfolgt. Beispielsweise wird aus der Zahlenfolge ns = 1, 2, 5, 5, 4 das Ergebnis ”1 2 25 4”. Die Methode startet im Array an der übergebenen Position i und arbeitet sich aufsteigend bis zum Ende des Arrays durch. Die Rückgabe soll als Zeichenkette erfolgen, worin die einzelnen Zahlen mit jeweils einem Leer- zeichen getrennt sind. Stehen im Array ab dem Index i keine Zahlen mehr zur Verfügung, gibt die Methode eine leere Zeichenkette zurück, liegt nur eine Zahl vor, wird nur diese zurückgegeben. Eine Verschmelzung kann somit erst dann erfolgen, wenn mindestens noch zwei Zahlen zur Verfü- gung stehen. Das Ergebniss bereits verschmolzene Zahlen soll in keine weitere Verschmelzung mit Zahlen eingehen, die dem Ergebniss gleichen, z.B. wird ns = 2, 2, 4, 6, 8 zu ”4 4 6 8”. Allerdings werden sämtliche aufeinanderfolgende gleiche Zahlen sehrwohl miteinander verschmol- zen,z.B.wirdns = 5, 5, 5, 6zu”125 6”oderns = 2, 2, 2, 8zu”8 8”.

 

[sascha-sphw]

TIPP 1: Es wird mindestens eine Schleife darin vorkommen.

 

[Flown]

@sascha-sphw in Rekursionen gibt es keine Schleife.

@TO was hast du bis jetzt versucht?

 

[sascha-sphw]

@sascha-sphw in Rekursionen gibt es keine Schleife.

Das ist so nicht ganz korrekt. In Rekursionen kann es durchaus schleifen geben. Aber bei dieser Aufgabe hast Du recht, hier kommt man ohne aus. (My Bad.)

 

[SnowDragon]

Das Problem ist, dass ich nicht weiß, wie genau ich anfangen soll. Die "Merge" Methode soll sich selbst aufrufen, aber mit welchem Parameter, und wie bekomme ich das hin, dass in jeder "Rekursionsstufe" 2 weitere Zahlen miteinander verschmelzen?

 

[sascha-sphw]

Die Methode startet im Array an der übergebenen Position i und arbeitet sich aufsteigend bis zum Ende des Arrays durch

Das hier wäre zum Beispiel mal ein Anfang... "... startet im Array ...", "... übergebenen Position ..." damit hast Du doch schon mal 2 Parameter.

 

[SnowDragon]

Also... das ist jetzt mal mein erster Versuch, der leider nicht funktioniert:

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

        // TODO
        String erg = null;
        if (i >= ns.length){
            return erg;
        }
       
        if (ns[i] == ns[i+1]){
            erg = Integer.toString(ns[i] * 2) ;
            i = i+2;
        }
        else {erg = Integer.toString(ns[i]);
        i++;
        }
       
            System.out.println(erg);
        return erg + " " + merge(ns, i, r);
    }

 

[Flown]

Kannst du mal die ganze Klasse posten und auch die Klasse Merge und überhaupt auch die ganze Aufgabenstellung und alle Materialien.

 

[SnowDragon]

public abstract class Merge {

    // Don't delete!! Tests will fail otherwise
    public Merge() {
    }

    /**
     * @param ns Integer array being merged
     * @param i Start index
     * @param r Only for test purposes. Ignore it!
     * @return String containing merged output
     */
    public static String merge(int[] ns, int i, Merge r) {
        // Don't delete!! Tests will fail otherwise
        // Pass object r to other function calls of merge (e.g. for recursion). Do not create other instances of object r
        // Function merge(...) must be recursive, don't implement other recursive helper functions
        r.check();

        // TODO Hier drunter muss ich meinen Code einfügen...
        String erg = null;
        if (i >= ns.length){
            return erg;
        }
       
        if (ns[i] == ns[i+1]){
            erg = Integer.toString(ns[i] * 2) ;
            i = i+2;
        }
        else {erg = Integer.toString(ns[i]);
        i++;
        }
       
            System.out.println(erg);
        return erg + " " + merge(ns, i, r);
    }

    // Don't delete!! Tests will fail otherwise
    public abstract void check();
}

Laden Sie sich die Datei Merge.java (das ist die klasse oben, ohne den Codeabschnitt unter "TODO", ich soll nur die Methode merge verändern) herunter und ergänzen Sie die darin enthaltene Methode merge(). Diese rekursive Methode verschmilzt jeweils benachbarte gleiche Zahlen im übergebe- nen Zahlenarray ns, wobei die Verschmelzung mittels Multiplikation erfolgt. Beispielsweise wird aus der Zahlenfolge ns = 1, 2, 5, 5, 4 das Ergebnis ”1 2 25 4”. Die Methode startet im Array an der übergebenen Position i und arbeitet sich aufsteigend bis zum Ende des Arrays durch. Die Rückgabe soll als Zeichenkette erfolgen, worin die einzelnen Zahlen mit jeweils einem Leer- zeichen getrennt sind. Stehen im Array ab dem Index i keine Zahlen mehr zur Verfügung, gibt die Methode eine leere Zeichenkette zurück, liegt nur eine Zahl vor, wird nur diese zurückgegeben. Eine Verschmelzung kann somit erst dann erfolgen, wenn mindestens noch zwei Zahlen zur Verfü- gung stehen. Das Ergebniss bereits verschmolzene Zahlen soll in keine weitere Verschmelzung mit Zahlen eingehen, die dem Ergebniss gleichen, z.B. wird ns = 2, 2, 4, 6, 8 zu ”4 4 6 8”. Allerdings werden sämtliche aufeinanderfolgende gleiche Zahlen sehrwohl miteinander verschmolzen,z.B.wird ns = 5, 5, 5, 6 zu ”125 6” oder ns = 2, 2, 2, 8 zu ”8 8”.

 

[Flown]

Nachdem du ja schon eine rekursive Methode hast, kannst du ja darin eine Schleife benutzen. Zähl doch einfach wieviele aufeinanderfolgende Elemente vorkommen und dann rechnest du mit Math.pow die Zahl aus - oder händisch mit einer Schleife.

 

[SnowDragon]

Hm, ich krieg ich das nicht hin, es funktioniert einfach nicht. Kannst du mir das bitte etwas genauer erklären?

 

[Flown]

Zeig doch mal her was du bisher hast.

 

[SnowDragon]

Die Methode, so wie sie oben steht:

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

        // TODO Hier drunter muss ich meinen Code einfügen...
        String erg = null;
        if (i >= ns.length){
            return erg;
        }
      
        if (ns[i] == ns[i+1]){
            erg = Integer.toString(ns[i] * 2) ;
            i = i+2;
        }
        else {erg = Integer.toString(ns[i]);
        i++;
        }
      
            System.out.println(erg);
        return erg + " " + merge(ns, i, r);
    }

Ich bin mir aber nicht sicher, ob ich damit auf dem richtigen Weg bin. Stimmen die Werte bei "return"? Und "erg" wird bei mir auch mit jedem rekursionsaufruf neu initialisiert, ich weiß nicht, ob das so richtig ist...

 

[Flown]

Dein if(ns[i] == ns[i+1]) muss noch etwas ausgebaut werden oder nicht? So kannst du ja nur benachbarte Zahlen prüfen. Hier solltest du eine Schleife einbauen.[/i]

 

[SnowDragon]

ok, danke. Ist das alles, was ich ändern muss?

 

[Flown]

Schau her: Wir sind nicht hier, um deine Aufgaben zu lösen, dass solltest du schon selbst erledigen. Darum sage ich dir:
Probiers doch aus! Bei weiteren Problemen melde dich wieder.

 

[SnowDragon]

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

        // TODO
        String erg = null;
        if (i >= ns.length){
            System.out.println(erg);
            return erg;
        }

        int z = 0;
        int erg2 = ns[i];
        int erg3 = ns[i];
        if (i < (ns.length-1)){
        for (int j = 1; j < (ns.length); j++){
            if (ns[i] == ns[i+j]){
                erg2 = erg2 * erg3;
                z++;
            }
            else{
                break;
            }
            }
       
        i = i+z+1;
        erg = Integer.toString(erg2) ;
            System.out.println(erg);
        return erg + " " + merge(ns, i);}
        else{
            erg = Integer.toString(ns[i]);
            i++;
            return erg + " " + merge(ns, i);
        }
    }

mittlerweile funktioniert die Methode, aber bei return gibt sie mir null zurück anstatt dem Ergebnis als String... Wie kann ich das beheben?

 

[Flown]

Also bei mir wird hier kein null-String zurückgegeben. Da es bei mir jetzt funktioniert geb ich dir mal meine Lösung:

public class Test {
  public static void main(String... args) {
    System.out.println(merge(new int[] { 1, 23, 3, 3, 4, 4, 4, 4, 4, 4, 5 }, 0));
  }
  
  public static String merge(int[] ns, int i) {
    if (ns == null || i >= ns.length) {
      return "";
    }
    int power = 1;
    int next = i;
    do {
      power *= ns[i];
      next++;
    } while (next < ns.length && ns[i] == ns[next]);
    return power + " " + merge(ns, next);
  }
}

 

[SnowDragon]

Wow, dein Ansatz wirkt viel eleganter. Bei mir wird nun doch der richtige String zurückgegeben, habe da nur was falsch ausgegeben. Ich saß jetzt stundenlang an diesem eigentlich simplen Problem...

 

[Flown]

Naja wir unterscheiden uns wahrscheinlich in ca. ~15 Jahren Software Entwicklung Erfahrung.

Nur die Erfahrung kann dir helfen, solche "leichten" Problemstellungen leichter zu abstrahieren und "klein/elegant" herunter zu progammieren.