Pseudocode Kinoaufgabe 2017

[Gast here]

Hi, 

ich möchte mich regelmäßig an dieser Art Aufgaben üben und suche professionelle Hinweise zu der richtigen Erledigung.

Da diese ~20min sehr wenig Zeit für mich sind, diese Aufgabe zu lesen, zu verstehen und dann noch richtig zu lösen, denke ich, dass Pseudocode üben sinnvoll ist, weil Syntax vernachlässigt werden kann.

Ist meine Herangehensweise an Pseudocode in dieser Form richtig und würde von Prüfern akzeptiert werden? 

Ich habe gelesen, dass es keine einheitlichen Vorgaben für Pseudocode gibt, doch an irgendwas muss man sich ja orientieren.
Ich habe es versucht, so verständlich wie möglich aufzuschreiben.

Gerne auch direkten Bezug zu meiner Lösung, die ich am PC in der angedachten Zeit hinbekommen habe.

Auf Papier wäre es wohl zeitlich nichts geworden, wegen auftretenden Korrekturen am Code.

Ich habe selber nicht auf Korrektheit der Lösung geprüft, sondern würde das alles gerne des Posts werden lassen - es dient ja dem Lernen.

Grüße
 

Es soll ermittelt werden, ob im Kino n aufeinanderfolgende Sitze in einer Reihe frei sind
(z.B. die drei Sitze mit den Sitznummern 207, 208 und 209 in Reihe 2)

Jede Reihe hat 30 Sitze

Sitzplan Kino 

Reihe    Sitznummer

1        101 102 103 104 105 106 107 108...130
2         201 202 203 204 205 206 207 208...230
3        301 302 303 304 305 306 307 308...330
...
7        401    402 403 404 405 406 407 408...430

Die Funktion greift auf folgendes Array kino vom Typ boolean zu.
Das Array enthäöt die Sitzbelegung für die entsprechende Vorstellung
Dabei gilt:

true(T) = Sitz ist frei
false(F) = Sitzt ist besetzt

Reihe 0 1 2 3 4 5 6 7 8...29
0      F T F F F F F F F...F    
1     F F T T F F T T T...F
2     F F T T T T T T F...F
...
6     F F F F F F F F F...F

Übergabewert ist die Anzahl der gewünschten nebeneinanderliegenden freien Sitze (Variable anzahlSitze).
Der Wertebereich der anzahlSitze beträgt 1 bis 30

Die Funktion soll folgendes zurückgeben:
Die Sitz Nr. des ersten Sitzes in der Sitzfolge (z.B. 207 von 207, 208, 209) wenn die Suche erfolgreich war.
Wert 0 wenn Suche nicht erfolgreich

Erstelle die Funktion freieSitze(anzahlSitze: int): int

 

freieSitze(anzahlSitze: int): int
    int Array final_array;


    wenn Länge von finalArray == n:
        return finalArray an der Stelle 1
    
    solange nicht alle Reihen und Plätze durchlaufen sind:

        für jede Reihennumer in Reihe:
            für jede Sitznummer in Sitze:
                falls aktuelle Sitznummer == T:
                    speichere aktuelle Sitznummer und Reihennumer als ein Element in final_array;
                falls aktuelle Sitznummer == F:
                    lösche Elemente aus finalArray
                falls letzter Sitz in letzter Reihe erreicht:
                    return 0

                
            

[Visar]

freieSitze(anzahlSitze: int): int
    int Array final_array;

    wenn Länge von finalArray == n:
        return finalArray an der Stelle 1

Die Bedingung kann nie true zurückgeben, entsprechend wird nie ein return erfolgen.

Dürfte unter anderem daran liegen, dass n nicht definiert wird und final_array zu diesem Zeitpunkt noch kein Element hinzugefügt wurde.

solange nicht alle Reihen und Plätze durchlaufen sind:
    für jede Reihennumer in Reihe:
        für jede Sitznummer in Sitze:
            falls aktuelle Sitznummer == T:
                speichere aktuelle Sitznummer und Reihennumer als ein Element in final_array;
            falls aktuelle Sitznummer == F:
                lösche Elemente aus finalArray
            falls letzter Sitz in letzter Reihe erreicht:
                return 0

Du ermittelst keine zusammenhängende Reihe von Sitzen, du speicherst bloß alle freien Sitze in einer Liste.

Eigentlich müsstest du prüfen, ob bei anzahlSitze = 3 die aktuelle Sitznummer UND ihre Nachbarn (Sitznummer+1, Sitznummer+2, usw.) frei sind und dann z.B. 207 zurückgeben.

Am Pseudocode selbst hätte ich jetzt wenig zu meckern, den versteht man. Aber die Lösung ist Quatsch.

Bearbeitet 31. Januar 2021 von Visar

[Gast here]

vor 30 Minuten schrieb Visar:

freieSitze(anzahlSitze: int): int
    int Array final_array;

    wenn Länge von finalArray == n:
        return finalArray an der Stelle 1

Die Bedingung kann nie true zurückgeben, entsprechend wird nie ein return erfolgen.

Dürfte unter anderem daran liegen, dass n nicht definiert wird und final_array zu diesem Zeitpunkt noch kein Element hinzugefügt wurde.

solange nicht alle Reihen und Plätze durchlaufen sind:
    für jede Reihennumer in Reihe:
        für jede Sitznummer in Sitze:
            falls aktuelle Sitznummer == T:
                speichere aktuelle Sitznummer und Reihennumer als ein Element in final_array;
            falls aktuelle Sitznummer == F:
                lösche Elemente aus finalArray
            falls letzter Sitz in letzter Reihe erreicht:
                return 0

Du ermittelst keine zusammenhängende Reihe von Sitzen, du speicherst bloß alle freien Sitze in einer Liste.

Eigentlich müsstest du prüfen, ob bei anzahlSitze = 3 die aktuelle Sitznummer UND ihre Nachbarn (Sitznummer+1, Sitznummer+2, usw.) frei sind und dann z.B. 207 zurückgeben.

Am Pseudocode selbst hätte ich jetzt wenig zu meckern, den versteht man. Aber die Lösung ist Quatsch.

Oja, du hast Recht. Ich sehe es auch so. Tatsächlich hatte ich den Gedanken zu Reihen im Kopf, habe ihn aber durch den Zeitdruck wieder verworfen. 

Ich glaube, ich solle erstmal versuchen, die Aufgaben sinnvoll zu lösen, mit deutlich mehr Zeit. Noch habe ich ja über 2 Jahre Zeit dafür, wollte mich nur schonmal drauf einstellen.

Ich werde später nochmal ein Update dazu machen.

[Gast here]

So, neuer Versuch.
Kann ich die Counter irgendwie im Pseudocode auslassen? Das macht es irgendwie unnötig kompliziert.

Ich würde einfach nur sagen wollen: "Zähle Reihen, Zähle Sitze" und setze diese zurück, wenn
 

freieSitze(anzahlSitze: int)
    int sitzCounter = 0;
    int reihenCounter = 0;
    int Array final_array;

    für jede Reihennumer in Reihe:
        erhöhe reihenCounter um 1;
        lösche Elemente aus final_array;
        sitzCounter = 0;
            
        für jede Sitznummer in Sitze:
            erhöhe sitzCounter um 1;
            
            wenn Länge von finalArray == anzahlSitze:
                //Ausgabe Reihe + Sitz
                return string(reihenCounter) +  string(finalArray an der Stelle 0);

            falls aktuelle Sitznummer == T:
                füge aktuelle Sitznummer als letztes Element in final_array;
                    
            falls aktuelle Sitznummer == F:
                lösche alle Elemente aus finalArray;
                
    //falls letzter Sitz in letzter Reihe erreicht (Schleifen komplett durchlaufen)
    return 0

 

Bearbeitet 31. Januar 2021 von here

[Visar]

Wenn anzahlSitze = 1 ist und nur mehr der letzte Sitz in der letzten Reihe frei ist, würde ich 0 zurückbekommen.

Diesen recht speziellen Fall deckt das frühe return nicht ab.

return string(reihenCounter) +  string(finalArray an der Stelle 0);

Du erhältst damit nicht die korrekte Sitznummer, wenn du einmal auf die Tabelle schaust.

207 ist der 7. Sitz der 2. Reihe. Bedeutet, dass sich korrekte Sitznummer - wenn die Schleife bei 0 anfängt - aus ((reihenNummer + 1) * 100) + sitzNummer ergeben müsste. Du hättest hingegen ein, uhm, "27"?

 

Bearbeitet 31. Januar 2021 von Visar

[Jana309]

Hallo, bei dieser Lösung wird ein Prüfer wahrscheinlich noch folgende Punkte ankreiden:

1. Du solltest unbedingt das vorgegebene 2D-boolean-array kino nutzen!
Mit der Zeile

falls Sitznummer == T

kannst du nicht abfragen ob der Sitz noch frei ist. Hier reicht es nicht, dass man mit gutem Willen versteht, was gemeint ist. Du MUSST das Array kino[][] nutzen, z.B.

falls kino[Reihennummer][SitzCounter] == T

Dabei ist zu beachten, dass die Sitznummer im Kinosaal und im Array korrekt zugeodnet werden(wie in Angabe erklärt), also z.B. kino[0][0] hält status von sitz 101; kino[5][10] hält status von sitz 611, usw....
(Hier ist wohl auch ein Druckfehler in der Aufgabenstellung, da Reihe 7 die nummern 4xx hat)

2. Als Rückgabetyp ist ein int gefordert. Deine Lösung liefert einen string. Deutlich besser wäre so etwas wie

return 100 * (reihenCounter + 1) +  sitzCounter +1

(oder ähnlich, je nachdem wie deine Variablen genau zählen)
Dein bisheriges return statement liefert nicht nur den falschen Typ sondern oft auch falsche Werte (wie Visar bereits angemerkt hat).

3. Deine Schleifenbedingungen wären mir zu schwammig. Wenn du bei diesem verbosen Stil bleiben willst (was in Pseudocode vielleicht sogar möglich ist), müsste es eher heißen:
 äußere Schleife: für jede Reihe in Kinosaal
 innere Schleife: für jeden Sitz in aktueller Reihe
 
Besser wären aber Schleifenbedinung die man nicht falsch verstehen kann, z.B.
 

solange reihenCounter < Anzahl der Reihen im Saal 
bzw. 
solange sitzCounter < Anzahl der Sitze pro Reihe

Dann würdest du auch die Variablen reihenCounter und sitzCounter verwenden. Diese stehen zwar schon jetzt in deinem Code und zählen fleißig mit, abgerufen werden die Werte aber nie.
 
4. Den kleinen Fehler in der Logik, den schon Visar angemerkt hat. Dieser könnte behoben werden, wenn die Prüfung ob genug freie Sitze gefunden wurden am Ende der inneren Schleife steht, nicht am Anfang.

 

Für die Prüfung nicht ganz so wichtig, für ein effizienteres und besser lesbares Programm solltest du noch folgendes überbedenken:

Du verwendest in deinem Code ein int-Array wo keines notwendig ist. Von dem int-Array werden nämlich nur die Länge und der Wert an Stelle 0 genutzt. Schöner wäre, diesen Wert in eine int Variable (nicht Array) zu speichern und zusätzlich eine countervariable für die freien Sitze hochzuzählen.

Noch zur Pseudocode-Syntax:
- Die Verzweigungen in deinem Pseudocode sind nur über die Einrückungen erkennbar. Überleg dir ob das für eine handschriftliche Prüfung eine gute Idee ist. Wenn du ordentlich schreibst ist das sicher möglich. Sobald du aber anfängst Zeilen nachträglich einzufügen und zu verbessern wird es eng. Es gibt aber auch Alternativen (z.B. wenn ... dann ... sonst ... wenn_ende). Wie auch immer du dich entscheidest: Teil der Herausforderung ist, das ganze auf Papier zu bringen. Übe das am besten gleich mit.
- Versuche deine Syntax konsequent zu halten (du verwedest teilweise "wenn", teilweise "falls")

- Wenn du komplementäre Bedingungen abfragst, ist WENN - SONST eine gute Idee. Das trägt zu besserer Lesbarkeit bei
Also z.B. statt

WENN sitz frei
    tue X;
WENN sitz besetzt
    tue Y;

besser

WENN sitz frei
    tue X;
SONST
    tue Y;

    
    
Hoffe, das hilft dir weiter

 

[Visar]

vor 1 Stunde schrieb Jana309:

Du verwendest in deinem Code ein int-Array wo keines notwendig ist. Von dem int-Array werden nämlich nur die Länge und der Wert an Stelle 0 genutzt. Schöner wäre, diesen Wert in eine int Variable (nicht Array) zu speichern und zusätzlich eine countervariable für die freien Sitze hochzuzählen.

Auch wenn das Array als nicht notwendig erscheint, finde ich den Ansatz tatsächlich sympathischer. Vielleicht täusche ich mich, aber m.E. kann er dadurch auf den erwähnten Zähler und auch auf eine zusätzliche Bedingung verzichten, die er nur einführen würde, um freierSitz+1, freierSitz+2, ...freierSitz+n zu prüfen. Knackpunkt daran: Die Bedingung wird immer abgeklappert, auch wenn es der erste, freie Sitz ist. Im Hinblick auf die Performance dürfte das Array also die bessere Wahl sein - und in der Realität würde sowieso jeder mit allen n Werten im Array arbeiten wollen.

Zur Veranschaulichung:

ergebnis: list = [] 
#ersterFreierSitz: int = 0


def freieSitze(anzahlSitze: int = 0):
    for reihe in reihen:
        ergebnis.clear()
        #ersterFreierSitz: int = 0
        #freieSitzAnzahl: int = 0

            for sitz in sitze:
                if kino[reihe][sitz] is True:
                    ergebnis.append(((reihe + 1) * 100) + (sitz + 1))
                    #ersterFreierSitz = ((reihe + 1) * 100) + (sitz + 1)
                    #if ersterFreierSitz != 0:
                    #    freieSitzAnzahl += 1

                if kino[reihe][sitz] is False:
                    ergebnis.clear()
                    #ersterFreierSitz = 0
                    #freieSitzAnzahl = 0

                if len(ergebnis) == anzahlSitze:
                #if freieSitzAnzahl == anzahlSitze:
                    return ergebnis[0]
                    #return ersterFreierSitz

	return 0

 

[Whiz-zarD]

vor 5 Stunden schrieb Visar:

Auch wenn das Array als nicht notwendig erscheint, finde ich den Ansatz tatsächlich sympathischer.

Nur ist das kein Array, sondern eine Liste. Ein Array, das den Anschein hat, es würde dynamisch wachsen, funktioniert nur mit Tricks. Außerdem braucht man im Grunde die Liste nicht. Eigentlich braucht man nur einen Zähler:

freieSitze(anzahlSitze : int) : int
    DO sitzreihe = 0 TO kino.length
        counter = 0
        DO sitz = 0 TO kino[sitzreihe].length
            IF kino[sitzreihe][sitz] == true THEN
                counter++
            ELSE
                counter = 0
            END IF

            IF counter == anzahlSitze THEN
                RETURN (100 * (sitzreihe + 1) + (sitz + 1)) - (anzahlSitze - 1)
            END IF
        END DO
    END DO

    RETURN 0
END

Ich zähle pro Sitzreihe einfach einen Counter hoch, wenn ich einen freien Sitz finde. Ansonsten geht er wieder auf 0. Wenn ich die gewünschte Anzahl gefunden habe, ermittle ich dann den ersten freien Sitz und geb ihn dann zurück.

Bearbeitet 1. Februar 2021 von Whiz-zarD

[Gast here]

Danke für die Anregungen, werde ich versuchen zu berücksichtigen! 

Die Lösung lesen sieht so simpel aus, drauf zu kommen ist ein anderer Schuh..