Robot Karol: Ziegelstapel der Höhe nach sortieren: Unterschied zwischen den Versionen

Aus MINT.lentner.net
Zur Navigation springen Zur Suche springen
 
(30 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
 +
__NOTOC__
 
[[Robot Karol | >>> zurück zur Übersicht von Robot Karol]]
 
[[Robot Karol | >>> zurück zur Übersicht von Robot Karol]]
  
Zeile 14: Zeile 15:
 
... '''und so wird eine einfache Sortieraufgabe zu einer knackige Sache!'''
 
... '''und so wird eine einfache Sortieraufgabe zu einer knackige Sache!'''
  
−
===Sortieridee===
+
==1. Sortieridee==
  
 +
===Macht zur Einführung in der Klasse folgendes Spiel:===
 +
Alle Schülerinnen (außer einer, die Karol spielt) stellen sich nebeneinander (in zufälliger Reihenfolge) an der Wand auf. Jetzt sollen die Schülerinnen dem Alter nach sortiert werden - die Jüngste links, die Älterste rechts, ... . Eine Schülerin spielt Karol. Sie geht immer wieder von rechts nach links, befragt zwei benachbarte Schülerinnen nach ihrem Geburtsdatum und vertauscht diese Schülerinnen eventuell, falls sie falsch stehen. Beobachtet, wie bei jedem Durchlauf immer nur die jeweils jüngste Schülerin ganz nach links wandert! Karol (oder Karoline) muss wie oft von rechts nach links laufen?
  
−
Mit den Knöpfen unter Deinem Grafikfenster kannst Du natürlich per Hand alles bauen. Das kannst Du unter ''"Welt speichern"'' auch '''aufheben''' und durch ''Öffnen Welt'' auch '''jederzeit wieder herholen'''. Das macht man auch, um '''einmalig mal eine Spielwelt''' (z.B. Ein Level für ein Computerspiel) '''zu entwerfen'''.
 
  
−
Mit ''Welt direkt festlegen'' (vorher in 2D-Modus wechseln!) geht das auch ganz fix.
 
  
−
'''Aber Roboter programmiert man aus anderen Gründen:''' Du möchtest Anweisungen so geben, dass Karol selber die Dinge baut - und zwar so baut, wie Du willst.
+
Wenn Karol an der unsortierten Ziegelstapelreihe (von rechts nach links) vorbei läuft, kann er nur benachbarte Stapelhöhen vergleichen. Karol sieht nicht - wie Du - ''"auf einen Blick"'' den kleinsten Stapel! Also wird er an der Stapelreihe vorbeigehen und immer nur '''benachbarte Stapel richten''', also vertauschen, wenn sie in falscher Ordnung stehen.
  
−
Stell' Dir vor, der Roboter Karol ist Dein Lehrjunge und '''Du lernst ihm, das Schwimmbad zu bauen'''.
+
Dann wandert aber nur der kleinste Stapel sicher ganz nach Süden an den richtigen, endgültigen Platz '''bei einem''' Durchlauf. Also muss er mehrmals an allen vorbei. Beim zweiten Durchlauf werden schon '''die beiden''' kleinsten Stapel im Süden an richtiger Rangfolge stehen, u.s.w..  
  
 +
Und auch, um zwei benachbarte Stapel zu vergleichen, muss Karol Ziegel abtragen, bis einer der beiden Stapel leer ist und dann sehen, was wo übrig bleibt, denn '''Karol kann keine Zahlen vergleichen'''. ... also lass uns ganz am Anfang beginnen:
  
−
<br style="clear:left; ">
+
==2. Einfache neue Bewegungsanweisungen==
 +
Da wir sehr häufig einen Sidestep links oder rechts (immer wieder) brauchen, wollen wir folgende neuen Anweisungen vereinbaren:
  
−
===Version 1: Gib Karol Deine Anweisungen im Anweisungsfenster links===
+
Anweisung LinksGehen
 +
  LinksDrehen Schritt RechtsDrehen
 +
*Anweisung
  
−
[[Datei: karolbad1.png |thumb|links|250px|Einfach nur alle Handgriffe kopieren]]
+
Anweisung RechtsGehen
 +
  RechtsDrehen Schritt LinksDrehen 
 +
*Anweisung
  
−
Im Programmierfenster links kannst Du Karol Anweisungen geben. Bist Du schnell im Schreiben, dann kannst Du einfach '''Schritt''' schreiben, '''LinksDrehen''', u.s.w. und ein Knopfdruck auf den ''Playbutton'' startet Karol. Karol baut jetzt für Dich nach Deinen Anweisungen. Du kannst auch mit der ''rechten Maustaste'' Befehle auswählen und einfügen, ohne sie zu schreiben.
+
==3. Vergleichen zweier Stapel==
  
−
Jetzt kannst Du immer wieder ''starten'' und Karol bei der ''selbstständigen Arbeit'' zusehen.
+
Um zwei Stapel zu vergleichen, vor denen Karol steht, bleibt ihm nichts anderes übrig, als von beiden Stapeln gleich viele Ziegel abtragen, bis einer der beiden Stapel leer ist. Dann weiß er: Auf dem leeren Platz war zuvor der kleinere Stapel. Karol kann die abgetragenen Ziegel hinter sich parken. Das macht die folgende Anweisung:
  
−
Mit den '''Short-Cuts <Strg>+<X>, <Strg>+<C> und <Strg>+<V>''' kannst Du ganze Textblöcke einfach kopieren und sparst Dir viel Schreibarbeit.
+
Anweisung gleicheweglegen
 +
//Karol steht vor zwei Stapeln und überprüft den vorliegenden und den linken Stapel
 +
//Solange beide Stapel Ziegel bergen, legt er von jedem Stapel einen Ziegel hinter sich
 +
//Am Ende ist einer der beiden Reststapel leer
 +
//Karol steht am Ende immer am rechten Stapel
 +
  MarkeSetzen
 +
  solange IstMarke tue
 +
    wenn NichtIstZiegel dann MarkeLöschen *wenn
 +
    LinksGehen
 +
    wenn NichtIstZiegel dann
 +
        RechtsGehen MarkeLöschen
 +
    sonst
 +
        RechtsGehen
 +
    *wenn
 +
    wenn IstMarke dann
 +
        Aufheben LinksDrehen LinksDrehen Hinlegen
 +
        RechtsDrehen Schritt RechtsDrehen
 +
        Aufheben LinksDrehen LinksDrehen Hinlegen
 +
        LinksDrehen Schritt LinksDrehen
 +
    *wenn
 +
  *solange
 +
*Anweisung
  
−
'''Tipp:''' Probier' mal, den ganzen Textblock des Programms unten nochmal 5x zu kopieren, dann baut Karol ein '''5 Reihen hohes Schwimmbad'''!
+
==4. Evtl. den größeren Stapel und den leeren vertauschen==
  
−
'''Aber:''' Du sagst ja Deinem Lehrling auch nicht 100x '''"Gehe einen Schritt!"''' (eher sagst Du genervt, ''"Das hab ich Dir doch schon 100x gesagt"''. Sondern Du sagst, '''"Gehe 100 Schritte!"''' Kann man Karol auch sagen, dass er etwas 100x machen soll?
+
Nachdem alle Ziegel, die es links '''und''' rechts gibt, weg sind, erkennt Karol den Platz mit dem ehemals kleineren Stapel. Es ist der leere Platz! In richtiger Reihenfolgen sollte es der linke Platz sein. Falls nicht, schiebt er die Restziegel vom linken auf den rechten Platz.
  
−
<br style="clear:left; ">
+
Anweisung umschichten
 +
//Karol steht vor zwei Stapeln. Einer von beiden (der vor ihm oder dessen linker) ist leer
 +
//Karol schichtet die Ziegel des nicht leeren Stapels immer auf den rechten der beiden Stapel
 +
//Am Ende hat immer der rechte Stapel die Ziegel
 +
//Karol steht am Ende immer am rechten Stapel
 +
  wenn NichtIstZiegel dann
 +
      LinksGehen
 +
      solange IstZiegel tue
 +
        Aufheben RechtsGehen Hinlegen LinksGehen
 +
      *solange
 +
      RechtsGehen
 +
  *wenn
 +
*Anweisung
  
−
//Westseite
+
==5. Die geparkten Ziegel hinter sich muss Karol jetzt wieder zurücklegen==
−
  Hinlegen
+
 
−
  Schritt
+
  Anweisung gleichezurücklegen
−
  Hinlegen
+
  //Karol steht vor zwei Stapeln. Der rechte hat Ziegel, der linke ist leer
−
  Schritt
+
  //Karol schichtet die Ziegel hinter sich auf beide Stapel
−
Hinlegen
+
  //Karol steht am Ende immer am rechten Stapel
−
Schritt
+
    LinksDrehen LinksDrehen
−
Hinlegen
+
    solange IstZiegel tue
−
Schritt
+
      Aufheben LinksDrehen LinksDrehen Hinlegen
−
LinksDrehen
+
      LinksDrehen LinksDrehen
−
//Südseite
+
    *solange
−
Hinlegen
+
    RechtsGehen
−
Schritt
+
    solange IstZiegel tue
−
Hinlegen
+
      Aufheben LinksDrehen LinksDrehen Hinlegen
−
Schritt
+
      LinksDrehen LinksDrehen
−
Hinlegen
+
    *solange
−
Schritt
+
    LinksGehen LinksDrehen LinksDrehen
−
Hinlegen
+
  *Anweisung
−
Schritt
+
 
−
LinksDrehen
+
==6. Ein Tausch zweier Stapel (falls die Ordnung falsch war) besteht jetzt aus ...==
−
  //Ostseite
+
 
−
Hinlegen
+
# Ziegel, die es links und rechts gibt, nach hinten legen
−
Schritt
+
# Evtl. den falschen Restestapel umschichten
−
Hinlegen
+
# Die geparkten Ziegel wieder zurücklegen
−
Schritt
+
 
−
Hinlegen
+
  Anweisung tauschen
−
Schritt
+
  //Karol steht vor zwei Stapeln Ziegel. Der Stapel direkt vor ihm und der davon linke Stapel
−
Hinlegen
+
  //Karol will, dass der Stapel vor ihm der größere der Beiden ist. Falls nicht dreht er die Beiden um
−
  Schritt
+
  //Karol steht am Ende immer am rechten Stapel
−
  LinksDrehen
+
  gleicheweglegen
−
  //Nordseite
+
  umschichten
−
  Hinlegen
+
  gleichezurücklegen
−
Schritt
+
  *Anweisung
−
Hinlegen
 
−
Schritt
 
−
Hinlegen
 
−
Schritt
 
−
Hinlegen
 
−
Schritt
 
−
  LinksDrehen
 
  
−
<br style="clear:left; ">
+
==7. HAUPTPROGRAMM==
  
−
===Version 2: Mit Wiederholungen alles einfacher, flexibler und übersichtlicher gestalten===
+
//HAUPTPROGRAMM
−
[[Datei: karolbad2.png |thumb|links|250px|Mit Wiederholungen alles einfacher, flexibler und übersichtlicher gestalten]]
+
//Karol steht vor einer Reihe von Ziegelstapeln
−
[[Datei: karolbad3.png |thumb|links|250px|Wie kann ich Karol lernen, dass er sich an die Raumgröße anpasst?]]
+
//Die Reihe von Ziegelstapeln stehen an der Westseite des Raumes
 +
//Er steht selbst am rechtesten Stapel mit Blick auf den Stapel
 +
//Die Stapel sind evtl. unterschiedlich hoch
 +
//Karol will die Stapel so sortieren, dass die jeweils größeren Stapel rechts stehen
 +
//Er geht mehrmals an allen Stapeln vorbei und dreht alle, die falsch stehen, um
  
−
Sieh' Dir mal das Programm unten genau an! Es hat dieselbe Wirkung, wie der ''"irre"'' Befehlstext oben. Ist er nicht 10x einfacher zu verstehen, 10x übersichtlicher? Du kannst offensichtlich auch Befehle hintereinander schreiben statt nur immer untereinander. Dadurch werden auch Sinn-zusammenhängende ''"Codeschnipsel"'' leichter erkennbar.
+
//zuerst geht er einmal an allen Stapeln vorbei und tauscht Stapel falscher Reihenfolge
 +
LinksDrehen
 +
solange NichtIstWand tue
 +
  RechtsDrehen
 +
  tauschen
 +
  LinksDrehen
 +
  Schritt
 +
*solange
  
−
Außerdem musst Du '''nur eine Zahl ändern''', wenn Karol die Strecke nicht 4x sondern vielleicht 10x oder 200x gehen und ziegeln soll.
+
//Jetzt ist der kleinste Stapel sicher am Ende
 +
//Die beiden letzten Stapel haben also auf jeden Fall richtige Reihenfolge
 +
//Also markiert Karol die beiden letzten Felder, denn da ist nichts weiter zu tun
 +
MarkeSetzen
 +
LinksDrehen LinksDrehen
 +
Schritt
 +
MarkeSetzen
  
−
'''Aber:''' Karol geht immer stur 4x nach vorne, Kann also nur 5x5 Schwimmbäder bauen. Wenn man aber vorher nicht weiß, wie groß das Grundstück des Kunden ist, sollte man sagen können: Gehe und ziegle sooft wie nötig - also bis zur gegenüber liegenden Wand ...!!!
+
//Stünde jetzt Karol vor der (nördlichen Start-) Wand, wäre er fertig
 +
//Er geht also zurück nach Norden und macht sich auf zu weiteren Durchläufen
 +
solange NichtIstWand tue
 +
  //Zurücklaufen zum START (Norden)
 +
  solange NichtIstWand tue Schritt *solange
 +
  LinksDrehen
 +
  //Erneut nach Süden laufen und Nachbarn sortieren
 +
  solange NichtIstMarke tue
 +
      tauschen LinksGehen
 +
  *solange
 +
  //Das letze Paar ist wiederum sicher in richtiger Reihenfolge, was Karol durch eine Markierung festhält
 +
  RechtsDrehen Schritt MarkeSetzen
 +
*solange
 +
LinksDrehen
  
−
<br style="clear:left; ">
+
==8. Das komplette Programm ohne erneute Kommentare==
  
−
  wiederhole 4 mal
+
  Anweisung LinksGehen LinksDrehen Schritt RechtsDrehen *Anweisung
−
  Hinlegen Schritt
+
Anweisung RechtsGehen RechtsDrehen Schritt LinksDrehen  *Anweisung<br>
−
   Hinlegen Schritt
+
Anweisung gleicheweglegen
−
   Hinlegen Schritt
+
  MarkeSetzen
−
   Hinlegen Schritt
+
  solange IstMarke tue
 +
    wenn NichtIstZiegel dann MarkeLöschen *wenn
 +
    LinksGehen
 +
    wenn NichtIstZiegel dann
 +
        RechtsGehen MarkeLöschen
 +
    sonst
 +
        RechtsGehen
 +
    *wenn
 +
    wenn IstMarke dann
 +
        Aufheben LinksDrehen LinksDrehen Hinlegen
 +
        RechtsDrehen Schritt RechtsDrehen
 +
        Aufheben LinksDrehen LinksDrehen Hinlegen
 +
        LinksDrehen Schritt LinksDrehen
 +
    *wenn
 +
  *solange
 +
*Anweisung<br>
 +
Anweisung umschichten
 +
   wenn NichtIstZiegel dann
 +
      LinksGehen
 +
      solange IstZiegel tue
 +
        Aufheben RechtsGehen Hinlegen LinksGehen
 +
      *solange
 +
      RechtsGehen
 +
   *wenn
 +
*Anweisung<br>
 +
Anweisung gleichezurücklegen
 +
    LinksDrehen LinksDrehen
 +
    solange IstZiegel tue
 +
      Aufheben LinksDrehen LinksDrehen Hinlegen
 +
      LinksDrehen LinksDrehen
 +
    *solange
 +
    RechtsGehen
 +
    solange IstZiegel tue
 +
      Aufheben LinksDrehen LinksDrehen Hinlegen
 +
      LinksDrehen LinksDrehen
 +
    *solange
 +
    LinksGehen LinksDrehen LinksDrehen
 +
*Anweisung<br>
 +
Anweisung tauschen
 +
  gleicheweglegen
 +
  umschichten
 +
  gleichezurücklegen
 +
*Anweisung<br>
 +
LinksDrehen
 +
solange NichtIstWand tue
 +
  RechtsDrehen
 +
  tauschen
 +
  LinksDrehen
 +
  Schritt
 +
*solange
 +
MarkeSetzen
 +
LinksDrehen LinksDrehen
 +
Schritt
 +
MarkeSetzen
 +
solange NichtIstWand tue
 +
   solange NichtIstWand tue Schritt *solange
 
   LinksDrehen
 
   LinksDrehen
−
  *wiederhole
+
  solange NichtIstMarke tue
 +
      tauschen LinksGehen
 +
  *solange
 +
  RechtsDrehen Schritt MarkeSetzen
 +
  *solange
 +
LinksDrehen
  
−
<br style="clear:left; ">
+
==Aufgaben:==
 +
# Kannst Du in der abgebildeten Welt feststellen, wie viele Vergleiche - wie viele Ziegelumschichtungen - Karol machen musste?
 +
# Kannst Du nicht doch die vielen Mehrfachvergleiche verhindern, wenn Du Dir mehr Platz nimmst, um Dir (mit Marken) doch so manches zu merken?
 +
# Wie viele Vergleiche sind im schlimmsten Fall nötig, um 100 Objekte durch paarweise Vergleiche in der oben benutzten Reihenfolge zu sortieren?

Aktuelle Version vom 3. Mai 2021, 09:03 Uhr

>>> zurück zur Übersicht von Robot Karol

unsortierte Reihe
sortierte Reihe


Es gehört zu den wichtigsten und am häufigsten gestellten Aufgaben, irgendwelche Objekte zu sortieren. Da man oft große Datenmassen sortieren muss, ist es auch äußerst wichtig, möglichst schnelle Sortiermethoden zu entwickeln. Dabei ist für die Geschwindigkeit natürlich entscheidend, was der Sortierer alles kann. Und da sind wir beim Knackpunkt.

Karol kann recht wenig.

  1. Karol kann sich zum Beispiel nichts merken (alles, was er früher schon einmal angeschaut hat, muss er immer wieder anschauen)
  2. Karol kennt keine Zahlen, kann keine Zahlen vergleichen.
  3. Karol kennt nur seine unmittelbare Nachbarschaft.

... und so wird eine einfache Sortieraufgabe zu einer knackige Sache!

1. Sortieridee

Macht zur Einführung in der Klasse folgendes Spiel:

Alle Schülerinnen (außer einer, die Karol spielt) stellen sich nebeneinander (in zufälliger Reihenfolge) an der Wand auf. Jetzt sollen die Schülerinnen dem Alter nach sortiert werden - die Jüngste links, die Älterste rechts, ... . Eine Schülerin spielt Karol. Sie geht immer wieder von rechts nach links, befragt zwei benachbarte Schülerinnen nach ihrem Geburtsdatum und vertauscht diese Schülerinnen eventuell, falls sie falsch stehen. Beobachtet, wie bei jedem Durchlauf immer nur die jeweils jüngste Schülerin ganz nach links wandert! Karol (oder Karoline) muss wie oft von rechts nach links laufen?


Wenn Karol an der unsortierten Ziegelstapelreihe (von rechts nach links) vorbei läuft, kann er nur benachbarte Stapelhöhen vergleichen. Karol sieht nicht - wie Du - "auf einen Blick" den kleinsten Stapel! Also wird er an der Stapelreihe vorbeigehen und immer nur benachbarte Stapel richten, also vertauschen, wenn sie in falscher Ordnung stehen.

Dann wandert aber nur der kleinste Stapel sicher ganz nach Süden an den richtigen, endgültigen Platz bei einem Durchlauf. Also muss er mehrmals an allen vorbei. Beim zweiten Durchlauf werden schon die beiden kleinsten Stapel im Süden an richtiger Rangfolge stehen, u.s.w..

Und auch, um zwei benachbarte Stapel zu vergleichen, muss Karol Ziegel abtragen, bis einer der beiden Stapel leer ist und dann sehen, was wo übrig bleibt, denn Karol kann keine Zahlen vergleichen. ... also lass uns ganz am Anfang beginnen:

2. Einfache neue Bewegungsanweisungen

Da wir sehr häufig einen Sidestep links oder rechts (immer wieder) brauchen, wollen wir folgende neuen Anweisungen vereinbaren: 

Anweisung LinksGehen 
  LinksDrehen Schritt RechtsDrehen 
*Anweisung

Anweisung RechtsGehen 
  RechtsDrehen Schritt LinksDrehen  
*Anweisung

3. Vergleichen zweier Stapel

Um zwei Stapel zu vergleichen, vor denen Karol steht, bleibt ihm nichts anderes übrig, als von beiden Stapeln gleich viele Ziegel abtragen, bis einer der beiden Stapel leer ist. Dann weiß er: Auf dem leeren Platz war zuvor der kleinere Stapel. Karol kann die abgetragenen Ziegel hinter sich parken. Das macht die folgende Anweisung: 

Anweisung gleicheweglegen
//Karol steht vor zwei Stapeln und überprüft den vorliegenden und den linken Stapel
//Solange beide Stapel Ziegel bergen, legt er von jedem Stapel einen Ziegel hinter sich
//Am Ende ist einer der beiden Reststapel leer
//Karol steht am Ende immer am rechten Stapel
 MarkeSetzen
 solange IstMarke tue
    wenn NichtIstZiegel dann MarkeLöschen *wenn
    LinksGehen
    wenn NichtIstZiegel dann
       RechtsGehen MarkeLöschen
    sonst
       RechtsGehen
    *wenn
    wenn IstMarke dann
       Aufheben LinksDrehen LinksDrehen Hinlegen
       RechtsDrehen Schritt RechtsDrehen
       Aufheben LinksDrehen LinksDrehen Hinlegen
       LinksDrehen Schritt LinksDrehen
    *wenn
 *solange
*Anweisung

4. Evtl. den größeren Stapel und den leeren vertauschen

Nachdem alle Ziegel, die es links und rechts gibt, weg sind, erkennt Karol den Platz mit dem ehemals kleineren Stapel. Es ist der leere Platz! In richtiger Reihenfolgen sollte es der linke Platz sein. Falls nicht, schiebt er die Restziegel vom linken auf den rechten Platz. 

Anweisung umschichten
//Karol steht vor zwei Stapeln. Einer von beiden (der vor ihm oder dessen linker) ist leer
//Karol schichtet die Ziegel des nicht leeren Stapels immer auf den rechten der beiden Stapel
//Am Ende hat immer der rechte Stapel die Ziegel
//Karol steht am Ende immer am rechten Stapel
  wenn NichtIstZiegel dann
     LinksGehen
     solange IstZiegel tue
       Aufheben RechtsGehen Hinlegen LinksGehen
     *solange
     RechtsGehen
  *wenn
*Anweisung

5. Die geparkten Ziegel hinter sich muss Karol jetzt wieder zurücklegen

Anweisung gleichezurücklegen
//Karol steht vor zwei Stapeln. Der rechte hat Ziegel, der linke ist leer
//Karol schichtet die Ziegel hinter sich auf beide Stapel
//Karol steht am Ende immer am rechten Stapel
   LinksDrehen LinksDrehen
   solange IstZiegel tue
      Aufheben LinksDrehen LinksDrehen Hinlegen
      LinksDrehen LinksDrehen
   *solange
   RechtsGehen
   solange IstZiegel tue
      Aufheben LinksDrehen LinksDrehen Hinlegen
      LinksDrehen LinksDrehen
   *solange
   LinksGehen LinksDrehen LinksDrehen
*Anweisung

6. Ein Tausch zweier Stapel (falls die Ordnung falsch war) besteht jetzt aus ...

  1. Ziegel, die es links und rechts gibt, nach hinten legen
  2. Evtl. den falschen Restestapel umschichten
  3. Die geparkten Ziegel wieder zurücklegen
Anweisung tauschen
//Karol steht vor zwei Stapeln Ziegel. Der Stapel direkt vor ihm und der davon linke Stapel
//Karol will, dass der Stapel vor ihm der größere der Beiden ist. Falls nicht dreht er die Beiden um
//Karol steht am Ende immer am rechten Stapel
  gleicheweglegen
  umschichten
  gleichezurücklegen
*Anweisung

7. HAUPTPROGRAMM

//HAUPTPROGRAMM
//Karol steht vor einer Reihe von Ziegelstapeln
//Die Reihe von Ziegelstapeln stehen an der Westseite des Raumes
//Er steht selbst am rechtesten Stapel mit Blick auf den Stapel
//Die Stapel sind evtl. unterschiedlich hoch
//Karol will die Stapel so sortieren, dass die jeweils größeren Stapel rechts stehen
//Er geht mehrmals an allen Stapeln vorbei und dreht alle, die falsch stehen, um

//zuerst geht er einmal an allen Stapeln vorbei und tauscht Stapel falscher Reihenfolge
LinksDrehen
solange NichtIstWand tue
  RechtsDrehen
  tauschen
  LinksDrehen
  Schritt
*solange

//Jetzt ist der kleinste Stapel sicher am Ende
//Die beiden letzten Stapel haben also auf jeden Fall richtige Reihenfolge
//Also markiert Karol die beiden letzten Felder, denn da ist nichts weiter zu tun
MarkeSetzen
LinksDrehen LinksDrehen
Schritt
MarkeSetzen

//Stünde jetzt Karol vor der (nördlichen Start-) Wand, wäre er fertig
//Er geht also zurück nach Norden und macht sich auf zu weiteren Durchläufen
solange NichtIstWand tue
  //Zurücklaufen zum START (Norden)
  solange NichtIstWand tue Schritt *solange
  LinksDrehen
  //Erneut nach Süden laufen und Nachbarn sortieren
  solange NichtIstMarke tue
     tauschen LinksGehen
  *solange
  //Das letze Paar ist wiederum sicher in richtiger Reihenfolge, was Karol durch eine Markierung festhält
  RechtsDrehen Schritt MarkeSetzen
*solange
LinksDrehen

8. Das komplette Programm ohne erneute Kommentare

Anweisung LinksGehen LinksDrehen Schritt RechtsDrehen *Anweisung
Anweisung RechtsGehen RechtsDrehen Schritt LinksDrehen  *Anweisung

Anweisung gleicheweglegen
 MarkeSetzen
 solange IstMarke tue
    wenn NichtIstZiegel dann MarkeLöschen *wenn
    LinksGehen
    wenn NichtIstZiegel dann
       RechtsGehen MarkeLöschen
    sonst
       RechtsGehen
    *wenn
    wenn IstMarke dann
       Aufheben LinksDrehen LinksDrehen Hinlegen
       RechtsDrehen Schritt RechtsDrehen
       Aufheben LinksDrehen LinksDrehen Hinlegen
       LinksDrehen Schritt LinksDrehen
    *wenn
 *solange
*Anweisung

Anweisung umschichten
  wenn NichtIstZiegel dann
     LinksGehen
     solange IstZiegel tue
       Aufheben RechtsGehen Hinlegen LinksGehen
     *solange
     RechtsGehen
  *wenn
*Anweisung

Anweisung gleichezurücklegen
   LinksDrehen LinksDrehen
   solange IstZiegel tue
      Aufheben LinksDrehen LinksDrehen Hinlegen
      LinksDrehen LinksDrehen
   *solange
   RechtsGehen
   solange IstZiegel tue
      Aufheben LinksDrehen LinksDrehen Hinlegen
      LinksDrehen LinksDrehen
   *solange
   LinksGehen LinksDrehen LinksDrehen
*Anweisung

Anweisung tauschen
  gleicheweglegen
  umschichten
  gleichezurücklegen
*Anweisung

LinksDrehen
solange NichtIstWand tue
  RechtsDrehen
  tauschen
  LinksDrehen
  Schritt
*solange
MarkeSetzen
LinksDrehen LinksDrehen
Schritt
MarkeSetzen
solange NichtIstWand tue
  solange NichtIstWand tue Schritt *solange
  LinksDrehen
  solange NichtIstMarke tue
     tauschen LinksGehen
  *solange
  RechtsDrehen Schritt MarkeSetzen
*solange
LinksDrehen

Aufgaben:

  1. Kannst Du in der abgebildeten Welt feststellen, wie viele Vergleiche - wie viele Ziegelumschichtungen - Karol machen musste?
  2. Kannst Du nicht doch die vielen Mehrfachvergleiche verhindern, wenn Du Dir mehr Platz nimmst, um Dir (mit Marken) doch so manches zu merken?
  3. Wie viele Vergleiche sind im schlimmsten Fall nötig, um 100 Objekte durch paarweise Vergleiche in der oben benutzten Reihenfolge zu sortieren?
Abgerufen von „http://mint.lentner.net/index.php?title=Robot_Karol:_Ziegelstapel_der_Höhe_nach_sortieren&oldid=2134“