Robotik in NWT
Karl soll Ziegelstapel der Größe nach sortieren.
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)
1. Schritt: Sortieren von zwei Ziegelstapeln
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.
Idee für einen Algorithmus
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.
möglicher Quelltext
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
2. Schritt: Karl soll drei Stapel sortieren
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:
- Gehe in den nächsten Zwischenraum.
- Gehe wieder zurück an den Ausgangspunkt.
3. Schritt: Karl sortiert mehrere Stapel
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.
4. Schritt: Karl sortiert mehrere Stapel
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?
Programmbibliothek
// 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
Programm - Quelltext
{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