Zur Hauptnavigation springen [Alt]+[0] Zum Seiteninhalt springen [Alt]+[1]

Highscorediagramm – Teil 4

Teil 4: Maximumsuche

Inhalt: Methoden mit Rückgabewert, Array-Algorithmus Maximumsuche, automatisches Testen

Nachdem die Punktewerte aus der externen Datei eingelesen sind, soll nun der beste Spieler oder die beste Spielerin ermittelt werden. Es wird also das Maximum der Punktewerte gesucht. Die Funktion könnte entweder den größten Wert oder die Position des größten Wertes im Array zurückgeben. Es ist sinnvoller die Position zurückzugeben, da damit der Wert leicht ermittelt werden kann. Umgekehrt ist das nicht möglich.

Der Algorithmus ist der erste einer Reihe von Algorithmen, die alle darauf basieren, dass das Array mit einer for-Schleife durchlaufen werden muss. Der Algorithmus müsste den Schülern aus der Klasse 8 bekannt sein, da er dort behandelt wurde. Dort wurde allerdings der Wert des Maximums ermittelt und nicht die Position im Array1:

Abbildung 1

Abbildung 1: Maximumsuche in Scratch von Lifelong-Kindergarten-Group am MIT-Media-Lab [CC-BY-SA-2.0]

Um den Algorithmus zu wiederholen, kann der Film maximumsuche.mov (Ordner05_praesentationen) gezeigt werden. Die SuS sollten selbstständig erkennen, welches Array-Element ausgewählt wurde. Mit Hilfe des Puzzles ( 13_alg_maximumsuche_puzzle.odt) kann der Algorithmus als Flussdiagramm gelegt werden. Dabei müssen die Verzweigung und die Schleifezerschnitten und die Pfeile von Hand eingezeichnet werden.

Abbildung 2

Die Umsetzung in der Programmiersprache erfolgt in einer eigenen Methode int maximumsuche(). Eindrucksvoll ist es, wenn man den Verlauf der Ausführung verfolgen kann. Das jeweils aktuell untersuchte Element und das aktuell maximale Element sollen farblich hervorgehoben werden. Dazu muss zunächst die graphische Darstellung angepasst werden. Die Methode maximumsuche() muss dann parallel zu der graphischen Darstellung arbeiten und durch eine entsprechende Verzögerung in angemessener Geschwindigkeit ausgeführt werden:

  • In Processing gibt es den Befehl thread(String methodenname), der sehr einfach einen parallelen Thread startet. Durch den Befehl delay(int millisekunden) kann die Ausführung verzögert werden. Damit das Bild neu gezeichnet wird, muss außerdem der Befehl redraw() aufgerufen werden. Dadurch wird die Methode draw() von Processing automatisch neu ausgeführt. In dieser muss die Methode zeichneBalken aufgerufen werden.
  • In Greenfoot wird bei einem Greenfoot.delay(int millisekunden) die Ausführung automatisch an Greenfoot zurückgegeben. In dieser Zeit arbeitet Greenfoot ausstehende Anzeigebefehle ab. Es ist also kein paralleler Thread erforderlich.
  • In normalem Java (z.B. Entwicklungsumgebung: JavaEditor) muss auch ein Thread gestartet werden. Die Syntax ist nicht ganz einfach, so dass die SuS dies nicht selbst programmieren sollten.

Da es sich hierbei um Spezialitäten der jeweiligen Umgebung handelt, wird den Schülerinnen und Schülern der Rahmen vorgegeben. Sie müssen lediglich in der Methode maximumsuche() die notwendigen Befehle aufrufen. Die Hinweise dazu stehen im Quelltext der jeweiligen Programmiersprache.

In der Softwareentwicklung gibt es die Methode der "testgetriebenen Entwicklung". Dabei werden die Tests der Methoden geschrieben, bevor die Implementation der Methoden selbst erfolgt. In jedem Entwicklungsschritt wird überprüft, ob die Tests immer noch korrekt ausgeführt werden. Dies ist auch für die Schule eine gute Möglichkeit, die korrekt Implementation von Schülern selbst testen zu lassen. Der Lehrer gibt dabei die Tests vor. In BlueJ gibt es dafür die Möglichkeit von JUnit-Tests. In Processing, Greenfoot und Java-Editor gibt es diese Möglichkeit nicht. Man kann aber leicht eigene Tests konstruieren, deren Ergebnisse in der Konsole ausgegeben werden. Dies ist hier realisiert. Es werden verschiedene Datensätze zur Kontrolle der Maximumsuche verwendet. Die Schüler starten die Tests durch

  • Processing: Drücken der Taste "t"
  • Greenfoot: Aufruf der Methode testen() im Kontextmenü
  • Java-Editor: Klick auf den Button "Testen"

Zur Übung können die Schüler auch die Minimumsuche implementieren. Sie sollten dabei vor der Implementation der Minimumsuche die Tests entsprechend anpassen.

1 Scratch wird von der Lifelong-Kindergarten-Group am MIT-Media-Lab entwickelt. Siehe http://scratch.mit.edu. Scratch ist lizenziert unter CC BY-SA 2.0

 

 

Hintergrund und Unterrichtsverlauf: Herunterladen [odt][2 MB]

Hintergrund und Unterrichtsverlauf: Herunterladen [pdf][380 KB]

 

Weiter zu Highscorediagramm – Teil 5-6