Karl soll mehrere Ziegelstapel der Größe nach sortieren. Hierzu zerlegt er das Problem in viele kleinere Probleme. So sortiert er zunächst nur zwei Stapel, anschließend drei und zum Schluß eine beliebige, vorher unbekannte Menge von Ziegelsteinen, zwischen denen sich jeweils ein Leerplatz befindet.Video (Youtube)
Karl steht zwischen zwei Ziegelstapeln beliebiger Höhe. Er soll herausfinden, ob der vordere oder der hintere Stapel mehr Ziegelsteine hat. Ist der vordere Stapel höher, soll er die Stapel vertauschen.
Wie könnte Karl vorgehen? Beachte: Er hat nur die Befehle Aufheben LinksDrehen Schritt RechtsDrehen und Hinlegen zur Verfügung.
Gliedere deinen Algorithmus, indem du eigene Anweisungen und eigene selbstdefinierte Bedingungen definierst.
Lege solange „vorne und hinten ein Ziegel ist“, jeweils eine Ziegellage zur Seite.
Fehlt hinten oder vorne ein Ziegel legt man im Fall, dass vorne noch Ziegel liegen alle Ziegel nach hinten. Ist vorne keine Ziegel mehr, so war hinten der gößere Stapel.
Anschließend legt man die zuvor weggelegten Steine wieder auf den alten Platz.
Anweisung Umdrehen LinksDrehen LinksDrehen *Anweisung Bedingung VorneUndHintenZiegel wenn NichtIstZiegel dann falsch sonst Umdrehen wenn NichtIstZiegel dann falsch sonst wahr *wenn Umdrehen *wenn *Bedingung Anweisung EineLageZiegelZurSeite Aufheben LinksDrehen Schritt RechtsDrehen Hinlegen RechtsDrehen Schritt RechtsDrehen Aufheben RechtsDrehen Schritt LinksDrehen Hinlegen LinksDrehen Schritt LinksDrehen *Anweisung Anweisung ZiegelNachHinten wiederhole solange IstZiegel Aufheben Umdrehen Hinlegen Umdrehen *wiederhole *Anweisung {ab hier gehts los} wiederhole solange VorneUndHintenZiegel EineLageZiegelZurSeite *wiederhole wenn IstZiegel dann ZiegelNachHinten *wenn LinksDrehen Schritt LinksDrehen wiederhole solange VorneUndHintenZiegel EineLageZiegelZurSeite *wiederhole LinksDrehen Schritt LinksDrehen
Karl soll jetzt 3 Stapel sortieren. Dazu vergleicht er zunächst die ersten zwei Stapel, dann geht er in den nächsten Zwischenraum und vergleicht diese.
Welche Höhe haben die einzelnen Stapel nach einem Durchgang?
Wie viel Durchgänge muss Karl maximal machen, damit alle Stapel sortiert sind?
Definiere folgende Unteranweisungen:
Karl sortiert mehrere Stapel.
Zunächst legt er für jedes zu vergleichende Stapelpaar sich einen Stein zur Seite. Als Hilfe kann man bei der Generierung der Welt zwischen das letzte Stapelpaar eine Marke setzen. Dies kann Karl allerdings auch am Anfang selbst erledigen.
Bei jedem Durchgang nimmt er einen Stein fort, so weiß Karl wann er den letzten Durchgang zu machen hat.
Karl sortiert beliebige Stapel. Allerdings nicht mehr, als die Höhe seiner Welt es zulässt.
Hier könnte man den Algorithmus noch verändern, wenn man diese Einschränkung nicht zulassen möchte.
Welche Erweiterungen wären sonst noch möglich?
// Sortieralgorithmus Anweisung Umdrehen Schnell RechtsDrehen RechtsDrehen Langsam *Anweisung Bedingung NichtRechtsMarkeZiegel Schnell wahr RechtsDrehen wenn NichtIstZiegel dann Schritt wenn IstMarke dann falsch *wenn Umdrehen Schritt Umdrehen *wenn LinksDrehen Langsam *Bedingung Anweisung MarkenAufräumen LinksDrehen Schritt RechtsDrehen wiederhole solange NichtRechtsMarkeZiegel Schritt *wiederhole RechtsDrehen Schritt MarkeLöschen RechtsDrehen RechtsDrehen Schritt LinksDrehen wiederhole solange NichtIstMarke Schritt *wiederhole MarkeLöschen LinksDrehen Schritt LinksDrehen *Anweisung Bedingung NichtRechtsMarkeZiegel wahr RechtsDrehen wenn NichtIstZiegel dann Schritt wenn IstMarke dann falsch *wenn Umdrehen Schritt *wenn RechtsDrehen *Bedingung Bedingung NochEinDurchgang Schnell falsch LinksDrehen Schritt(2) wenn IstZiegel dann wahr Aufheben *wenn Umdrehen Schritt(2) LinksDrehen Langsam *Bedingung Bedingung ZiegelVorneUndHinten // Bedingung wahr falls Vo u. Hi. Ziegel Schnell falsch wenn IstZiegel dann Umdrehen wenn IstZiegel dann wahr *wenn Umdrehen *wenn Langsam *Bedingung Bedingung IstRechtsZiegel Schnell falsch RechtsDrehen wenn IstZiegel dann wahr *wenn LinksDrehen Langsam *Bedingung Anweisung GeheVor Schnell LinksDrehen Schritt RechtsDrehen Schritt(2) RechtsDrehen Schritt LinksDrehen Langsam *Anweisung Anweisung ZiegelAufAndereSeite //schaufelt Ziegel von Vorne nach Hinten oder umgekehrt Schnell wiederhole solange IstZiegel Aufheben Umdrehen Hinlegen Umdrehen *wiederhole Langsam *Anweisung Anweisung ZiegelZurSeiteSchaffen // Legt jeweils eine Lage zur Seite wiederhole solange ZiegelVorneUndHinten Aufheben LinksDrehen Schritt LinksDrehen Hinlegen LinksDrehen Schritt RechtsDrehen Aufheben RechtsDrehen Schritt RechtsDrehen Hinlegen RechtsDrehen Schritt LinksDrehen *wiederhole *Anweisung Anweisung GrosserStapelNachHinten // Hauptanweisung ZiegelZurSeiteSchaffen ZiegelAufAndereSeite LinksDrehen Schritt LinksDrehen ZiegelZurSeiteSchaffen LinksDrehen Schritt LinksDrehen *Anweisung Anweisung Zurueck // läuft von der unteren Marke zur oberen Marke // und dann zurück zum Ausgangspunkt Schnell LinksDrehen Schritt LinksDrehen wiederhole solange NichtIstMarke Schritt *wiederhole LinksDrehen Schritt LinksDrehen Langsam *Anweisung Anweisung MarkeAmAnfangSetzen Schnell LinksDrehen Schritt MarkeSetzen Umdrehen Schritt LinksDrehen Langsam *Anweisung Anweisung ProStapelEinenZiegelHinlegen Schnell LinksDrehen Schritt RechtsDrehen Schritt wiederhole solange IstRechtsZiegel LinksDrehen Hinlegen RechtsDrehen Schritt(2) *wiederhole Umdrehen Schritt(3) LinksDrehen Schritt MarkeSetzen Umdrehen Schritt RechtsDrehen Schritt(2) LinksDrehen Schritt MarkeSetzen Umdrehen Schritt RechtsDrehen wiederhole solange NichtIstMarke Schritt *wiederhole LinksDrehen Schritt LinksDrehen Langsam *Anweisung Anweisung ZiegelZaehlen // Legt einen! seitlichen Ziegel auf einen Stapel // dieser dient zum Zählen der Durchgänge Schnell Aufheben Schritt RechtsDrehen Schritt RechtsDrehen wiederhole solange NichtIstMarke Schritt *wiederhole RechtsDrehen Schritt Hinlegen RechtsDrehen Langsam *Anweisung Anweisung ZiegelEinsammeln Schnell LinksDrehen Schritt(2) RechtsDrehen wiederhole solange NichtIstMarke wenn IstZiegel dann ZiegelZaehlen *wenn Schritt *wiederhole MarkeLöschen RechtsDrehen Schritt RechtsDrehen wiederhole solange NichtIstMarke Schritt *wiederhole LinksDrehen Schritt LinksDrehen // zum Schluß noch einen Ziegel wegnehmen LinksDrehen Schritt(2) Aufheben Umdrehen Schritt(2) LinksDrehen Langsam *Anweisung Anweisung MarkenAufraeumen LinksDrehen Schritt RechtsDrehen wiederhole solange NichtRechtsMarkeZiegel Schritt *wiederhole RechtsDrehen Schritt MarkeLöschen Umdrehen Schritt LinksDrehen wiederhole solange NichtIstMarke Schritt *wiederhole MarkeLöschen LinksDrehen Schritt LinksDrehen *Anweisung
{Karl sortiert eine beliebige Anzahl} {weniger als 6} Einfügen sortieren_bibliothek.kdp *Einfügen MarkeAmAnfangSetzen ProStapelEinenZiegelHinlegen ZiegelEinsammeln wiederhole solange NochEinDurchgang wiederhole solange NichtIstMarke GeheVor GrosserStapelNachHinten *wiederhole Zurueck *wiederhole MarkenAufräumen