Zeilen und Spaltenweise einlesen und als Bruch darstellen(Zweidimensionales Array)

[Sekiro24]

Mit dem C++ Code konnte ich leider nichts anfangen. Ich schicke ma trotzdem die Aufgabenstellung.

Die Funktion berechnen(int i, int j) soll folgendes machen.

• mit dem aktuellen Stein i soll immer der Nachfolger j im Array Steine betrachtet werden.
• Passt der aktuelle Nachfolger wird die Funktion verlassen und der nächste Stein betrachtet.
• Passt der aktuelle Nachfolger indem man ihn dreht, dann wird er gedreht, die Funktion wird verlassen und der nächste Stein betrachtet.
• Passt der aktuelle Nachfolger nicht(auch nicht durch drehen), dann wird die Funktion berechnen(int i, int j) erneut aufgerufen(Rekursion) und der übernächste Nachfolger überprüft. Passt der übernächste nicht, wird der überübernächste überprüft usw..
• D.h. wenn Sie im Hauptprogramm Stein i = 1 an berechnen(int i, int j) übergeben haben, dann überprüft berechnen(int i, int j) rekursiv der Reihe nach die Steine j = 2 ... 7, ob sie (ggf. auch durch drehen) passen. Wenn Sie im Hauptprogramm Stein j = 4 an berechnen(int i, int j) übergeben haben, dann überprüft berechnen(int i, int j) rekursiv der Reihe nach die Steine 5 - 7, ob sie (ggf. auch durch drehen) passen
• Falls der übernächste, drittnächste etc. Stein passt, wird er mit dem unmittelbar nächsten Stein im Array Steine vertauscht.
• Wenn es bei den restlichen Steinen keinen passenden Anlegekandidaten mehr gibt soll das Spiel mit einer entsprechenden Bildschirmausgabe beendet werden.

D.h bei jedem Drehen oder Steinetausch, wird die Reihenfolge bzw. Anordnung der Steine Array Steine aktualisiert.

Idee:
Zuerst dachte ich daran, dass ich in der main eine For-Schleife schreibe und die Laufvariable i übergebe aber da bin ich mir nicht sicher ob ich da richtig liege, da ich ja auch irgendwie die Variable j übergeben muss. Also meine Frage hier muss ich in der main eine for in for schreiben mit den jeweiligen Variablen i für die äussere Schleife und j für die innere Schleife ?
Wenn ja, wie mache ich das mit der Rekursion in der Funktion berechnen(int i, int j) ?

 

[Technipion]

Also meine Frage hier muss ich in der main eine for in for schreiben mit den jeweiligen Variablen i für die äussere Schleife und j für die innere Schleife ?

Jein. So wie ich das sehe brauchst du in der main() zwar eine for-Schleife, die über i = 0 .. n läuft, aber das j soll eigentlich von der Funktion berechnen(i, j) selbst bestimmt werden (über Rekursion). Also quasi

main {
    for i in 0 .. n {
        ...
        berechnen(i, i+1);
        ...
    }
}


func berechnen(i, j) {
    // teste ob Stein Nr. j passt:
    ...
    // ggf. nächsten Stein überprüfen:
    berechnen(i, j+1); // <--- Rekursion
}

Gruß Technipion

 

[cwriter]

Zuerst dachte ich daran, dass ich in der main eine For-Schleife schreibe und die Laufvariable i übergebe aber da bin ich mir nicht sicher ob ich da richtig liege, da ich ja auch irgendwie die Variable j übergeben muss.

Das ist nicht allzu falsch.

Wenn ja, wie mache ich das mit der Rekursion in der Funktion berechnen(int i, int j) ?

Gehen wir doch mal die Aufgabenstellung durch:

mit dem aktuellen Stein i soll immer der Nachfolger j im Array Steine betrachtet werden.

Interessiert nicht, ist nur Overview.

Passt der aktuelle Nachfolger wird die Funktion verlassen und der nächste Stein betrachtet.

Da haben wir:

int berechnen(int i, int j)
{
    if(passt(i, j)) return:
}

Passt der aktuelle Nachfolger indem man ihn dreht, dann wird er gedreht, die Funktion wird verlassen und der nächste Stein betrachtet.

Daraus folgt:

int berechnen(int i, int j)
{
    if(passt(i, j)) return 0:
    if(passt(i, gedreht(j)))
    {
        drehe(j);
        return 0;
    }
}

Passt der aktuelle Nachfolger nicht(auch nicht durch drehen), dann wird die Funktion berechnen(int i, int j) erneut aufgerufen(Rekursion) und der übernächste Nachfolger überprüft. Passt der übernächste nicht, wird der überübernächste überprüft usw..

Also:

int berechnen(int i, int j)
{
    if(passt(i, j)) return 1:
    else if(passt(i, gedreht(j)))
    {
        drehe(j);
        return 1;
    }
    else
    {
        berechnen(i, j+1);
    }
}

Falls der übernächste, drittnächste etc. Stein passt, wird er mit dem unmittelbar nächsten Stein im Array Steine vertauscht.

Also:

int berechnen(int i, int j)
{
    if(passt(i, j)) return 1:
    else if(passt(i, gedreht(j)))
    {
        drehe(j);
        return 1;
    }
    else
    {
        if(berechnen(i, j+1) == 1)
        {
            tausche(i+1, j+1);
        }
    }
}

Als nächstes ist die Aufgabenstellung mehr als schlecht (mehr dazu später), aber man kann sich ja selbst was überlegen:

int berechnen(int i, int j)
{
    if(i > max_stein || j > max_stein) return 0; // Bounds check
    if(passt(i, j)) return 1:
    else if(passt(i, gedreht(j)))
    {
        drehe(j);
        return 1;
    }
    else
    {
        if(berechnen(i, j+1) == 1)
        {
            tausche(i+1, j+1);
        }
    }
    return 0; // Muss was zurückgeben
}

Ok, dann zur main: Aus der Aufgabenstellung ist das nicht ganz klar, aber da i nicht verändert wird, muss das wohl mit einer Schleife in der main geschehen:

for(i...)
{
    if(berechnen(i, i+1) == 0) // Warum i, i+1? => Weil j per Definitionem ein Nachfolger sein muss
    {
        // Ende der Fahnenstange
    }
}

So, viel zu viel geholfen. Nun zum Rant:

Die Aufgabenstellung ist falsch bzw. löst das implizierte Problem nicht. Genauer gesagt ist das ein Greedy-Algorithmus (nimmt die erstbeste Möglichkeit). Das führt zu suboptimalen Resultaten. Ein Beispiel gefällig?

(1 | 2) => (2 | 3) => (2 | 2) => (3 | 4) => (4 | 5) => ... usw (in die Unendlichkeit)

Es ist offensichtlich, dass hier eine unendlich lange Kette möglich wäre, die alle Steine benutzt (Stein 1, Stein 3, Stein 2, Stein 4, Stein 5, ....). Aber der Beschriebene Algorithmus wird immer den Stein (2 | 2) übrig haben. Warum? Weil er den Stein (2 | 3) nimmt und der Stein (2 | 2) niemals mehr passen wird.
Ok, also haben wir herausgefunden, dass der Algorithmus nicht maximiert. (Dieses Beispiel ist ein einfacher Fall, um zu beweisen, dass der Algorithmus inkorrekt ist - es gibt viele andere Probleme durch die Erzwungene Startorientierung ohne Option, einen anderen Startpunkt zu wählen und die inkomplette Aufzählung der Möglichkeiten).
Dann ist die Rekursion hier völliger Blödsinn und hat überhaupt keine Existenzberechtigung. Man nutzt den Stack ja nicht einmal für Zwischenwerte. (= Unnötiger Stackoverflow für nichts und wieder nichts).
Rekursion ist dann einfacher als Iteration, wenn man einen Zustandsautomaten mit Variablen bauen will. Hier wird das weggeworfen.

Ok, dann schauen wir uns mal die Laufzeit an. Die Laufzeit hier ist O(n^2) durch die beiden Iteratoren. Ist das besser als mein Code oben?
Mein Code hat eine Laufzeit von O(n^n), also ja: Hier ist der Algorithmus der Aufgabe besser.
Parallelisierbarkeit: Nicht vorhanden im Aufgabenalgorithmus, vorhanden im Vorschlag.


Ach, der Professor wollte wohl nett sein und ein abwechslungsreiches Beispiel bringen, aber ich sehe nichts gutes an der Aufgabe.
Naja, mit den Tipps ist die Aufgabe ja immerhin lösbar.

Gruss
cwriter

 

[Sekiro24]

Ich habe das jetzt mal wie folgt geschrieben, jedoch wird mir vom compiler gesagt, dass es 2 Fehler gibt.

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int Steine[7][2];
int berechnen(int, int);
int i, j, temp;
int main(){


    printf("Bitte geben Sie nun 7 Dominosteine ein\n");
    einlesen();
    for(i = 0; i < 7; i++)printf("%d. %d/%d\n", (i+1) ,Steine[i][0], Steine[i][1]);
    for(i = 0; i < 7; i++)
      if(berechnen(i, i+1) == 0)
        {

        }
    return 0;
}

void einlesen(){
    for(i = 0; i < 7; i++){
        printf("%d.\n", (i+1));
        for(j = 0; j < 2; j++)
          scanf("%d", &Steine[i][j]);
    }
}

int berechnen(int i, int j) {
    if(i > 7 || j > 7) return 0;
    if(Steine[i][0] == Steine[j][0])
        return 1;
    else
        if(Steine[i][0] == Steine[j][1])
        {
            /*Drehen*/
            temp = Steine[j][1];
            Steine[j][1] = Steine[j][0];
            Steine[j][0] = temp;
            return 1;
        }
    else{
            brechnen(i, (j+1));
        }
    return 0;
}

 

[Technipion]

jedoch wird mir vom compiler gesagt, dass es 2 Fehler gibt.

Ich weiß das klingt jetzt weit hergeholt, aber wie wäre es - für die Zukunft - wenn du diese Fehler dann auch mitposten würdest?

Mir fällt direkt auf, dass in der main() die Funktion einlesen() benutzt wird, die der Compiler aber zu dem Zeitpunkt noch gar nicht kennt. Das müsste also einen Error erzeugen. Lösung? Lege ganz oben einen Prototypen an, genau wie bei berechnen(...).

Ich halte mich aber zunächst noch zurück, ich kann nämlich schon cwriters Tastatur klackern hören

 

[Sekiro24]

Der Fehler lag eher unten bei berechnen. Ich habe ausversehen brechnen statt berechnen geschrieben.

 

[Sekiro24]

Es wird auch nicht wirklich getauscht.

 

[cwriter]

Es wird auch nicht wirklich getauscht.

Nummer 42 der Sekiro'schen Weisheiten.

Du hast in deinem Code auch keine Zeile, die das tun sollte...

Nicht böse gemeint, aber du solltest wirklich deine Arbeitsweise überdenken. Du eröffnest ein Thema (vor einem Monat), dann liegt es ein paar Wochen brach ohne Lebenszeichen und dann bekommen wir vorwurfsvolle Einzeiler vorgelegt.
Wir sind geduldig und haben schon viel gesehen (und wollen dich sicher nicht entmutigen), aber erweise uns doch den Respekt, etwas mehr Gedanken in deine Posts einfliessen zu lassen. Wenn du etwas nicht verstehst, dann frage nach einer Erklärung (idealerweise mit einer Beschreibung, warum du etwas nicht verstehst). Wenn etwas nicht kompiliert, dann gib uns die Fehlermeldungen (idealerweise 1 zu 1 kopiert). Wenn der Code etwas nicht tut, was er deiner Meinung nach tun sollte, dann sage uns, warum du meinst, dass die Funktionalität da sein soll und wo du die betreffenden Codezeilen vermutest.

Wir geben uns Mühe, unsere Posts so hilfreich wie möglich zu schreiben und lassen viele Gedanken einfliessen - entsprechend kann es sein, dass man mal 20-30 Minuten über einem Post sitzt. Entgegne diese Höflichkeit, indem du es uns gleichtust.

Ok, Schwamm drüber, Blick nach vorne: Zu deinem Problem.

Jetzt, da du weisst, dass du den Code nicht hast: Wo ist der Knoten, der dich daran hindert, den Code zu schreiben?

Gruss
cwriter

 

[Sekiro24]

Sorry nochmal trotzdem, musste in letzter Zeit mehr für andere Fächer machen.
Also ich habe eben bemerkt das ich das mit dem tauschen offensichtlich nicht habe - eingesehen.
Du hast dazu folgendes geschrieben:

if(berechnen(i, j+1) == 1) { tausche(i+1, j+1); }

Für die Stelle wo getauscht werden soll, also "tausche(i+1 , j+1)", habe ich folgendes geschrieben:

if (berechnen(i, j+1) == 1)
                {
                  /*Tauschen*/
                  temp = Steine[i + 1][0];
                  temp1 = Steine[i + 1][1];
                  Steine[i + 1][0] = Steine[j + 1][0];
                  Steine[i + 1][1] = Steine[j + 1][1];
                  Steine[j + 1][0] = temp;
                  Steine[j + 1][1] = temp1;
                }

 

[cwriter]

Sorry nochmal trotzdem, musste in letzter Zeit mehr für andere Fächer machen.

Das kann ich durchaus verstehen . Allerdings ist meine Erfahrung, dass man solche Programme jeweils in höchstens einer Woche bearbeiten sollte, da man sonst mehr Zeit mit dem Wieder-Einlesen verbringt als mit dem Problem selbst. Aber vielleicht ist das bei dir ja anders. Und es kann ja immer etwas wichtigeres dazwischenkommen, da hast du schon recht.

Für die Stelle wo getauscht werden soll, also "tausche(i+1 , j+1)", habe ich folgendes geschrieben:

Ok, damit sieht das Programm eigentlich schon recht komplett aus. Ich habe das Programm selbst nicht geschrieben/nicht ausgeführt; geht es denn jetzt wie erwartet?

Gruss
cwriter