Hans Peter Schneider · Die JavaKara-Umgebung wurde programmiert für die von Objektorientierung ungestörte Einführung in die sequentielle Programmierung mit C-Strukturen, die der

Hans Peter Schneider

Rekursion mit JavaKaraeine Unterrichtsreihe des Faches Informatik

im Rahmen des Wahlpflichtunterrichts der Klasse 9an Gymnasien

1. Semesterarbeit zur Virtuellen Lehrerweiterbildung Informatik in Niedersachsen

Virtuelle Lehrerweiterbildung Informatik in NiedersachsenHans Peter Schneider Rekursion mit JavaKara Seite 2

Inhalt Seite

JavaKara . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

Beschreibung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

Einsatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

Rekursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Rekursion vs. Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Modell der Impliziten Speicherung . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Unterrichtsreihe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1. „Hin und Zurück” – Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2. „Labyrinth rekursiv” – Anwendung . . . . . . . . . . . . . . . . . . . . . . . 8

3. „Füllen” – Vertiefung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

Weitere Aufgaben zur Rekursion . . . . . . . . . . . . . . . . . . . . . . . . 9

1. „Türme von Hanoi” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2. ggT mit Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

Quellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11


JavaKara

Beschreibung

Die ETH Zürich [1] bietet ein Java-Programm zum kostenlosen Download an, das für den Unterrichteine einfache Umgebung bietet, um Programmieren zu lernen. Ein Roboter-Objekt namens Kara in Formeines Marienkäfers kann mittels eines kleinen Befehlssatzes in einer diskreten Welt gesteuert werden.Unter anderem kann dieser Roboter in der Sprache Java programmiert werden, wobei die sequentielleProgrammierung im Vordergrund steht, Objektorientierung und Ereignissteuerung werden nicht unter-stützt.

Die Welt, in der sich Kara bewegt, ist zweidimensional, in beiden Hauptrichtungen zyklisch undbesteht aus einem rechteckigen Bereich aus endlich vielen quadratischen Feldern. Jedes Feld kann miteinem Kleeblatt, einem Pilz oder einem Baumstumpf belegt sein. Kara kann auf den freien Feldern undüber Kleeblätter laufen. Ein Pilz wird von Kara verschoben, wenn das Feld dahinter frei ist. Ein Baum-stumpf ist für Kara ein unbewegliches Hindernis. Der Benutzer kann die Welt frei gestalten und speichern.

In der Java-Umgebung wirdKara durch das Objekt kararepräsentiert, die zulässigenBefehle und Sensoren des Ro-boters sind als Methoden diesesObjekts implementiert (sieheKasten). Die Hauptklasse desJava-Programms wird von dervordefinierten Klasse Java-KaraProgram abgeleitet. Indieser wird das Programmselbst innerhalb der Methode public void myProgram() implementiert, die die gleichnamigeMethode der Elternklasse überlagert. Innerhalb der Klasse können wie in jeder Klasse weitere Methodenund Variablen definiert werden. Weitere eigene Klassen können zwar definiert und verwendet werden,dies geht aber über die eigentliche Zielsetzung von JavaKara hinaus. Das fertige Programm wird aus derUmgebung heraus kompiliert und ausgeführt, dabei wird die zugehörige .class-Datei erzeugt und als Teilvon allkara.jar ausgeführt.

Einsatz

Die JavaKara-Umgebung wurde programmiert für die von Objektorientierung ungestörte Einführungin die sequentielle Programmierung mit C-Strukturen, die der Sprache Java zu Grunde liegen. Die Weltund der Befehlssatz von JavaKara erlauben am Anfang sogar eine variablen- und parameterfreie Program-mierung, die es ermöglicht ohne großen Aufwand die Schüler zu komplexen kognitiven Strukturen wie

Die Befehlevoid kara.move(); ein Feld vorwärts bewegenvoid kara.turnLeft(); auf dem Feld eine Vierteldrehung linksvoid kara.turnRight(); auf dem Feld eine Vierteldrehung rechtsvoid kara.removeLeaf(); Kleeblatt aufnehmenvoid kara.putLeaf(); Kleeblatt ablegen

Die Sensorenboolean kara.treeFront(); ist in Laufrichtung ein Baum?boolean kara.treeLeft(); ist links ein Baum?boolean kara.treeRight(); ist rechts ein Baum?boolean kara.onLeaf(); steht Kara auf einem Blatt?boolean kara.mushroomFront(); ist in Laufrichtung ein Pilz?


4. Codepublic class ImmerAnDerWandLangextends JavaKaraProgram { public void myProgram() { while (!kara.onLeaf()) { kara.turnLeft(); while (kara.treeFront()) { kara.turnRight(); }; kara.move(); }; };};

public class FindeBlatt extends JavaKaraProgram { public void myProgram(){ while (!kara.onLeaf()) { kara.move();

3. Struktogramm

2. AlgorithmusIst links ein Durchgang, so benutzediesen; sonst, wenn geradaus frei,folge dem Gang; sonst, wenn rechtsein Durchlass, benutze diesen;sonst kehre um. Dies alles immerwieder bis zum Kleeblatt.

1. StrategieMan taste nach derlinken Wand undfolge dieser bis zumKleenlatt.

den Begriff der Rekursion zu führen. Das niedliche Design spricht Schüler in der Klasse 9 nicht mehr sehran, es ist eher was für die Klassen 5 bis 7, dennoch ist JavaKara als Werkzeug für die Unterrichtsreihe„Einführung in die Java-Programmierung” im zweiten Quartal des Kurses sehr wertvoll. Die Verwen-dung von Java-Kara fügt sich wie folgt in den Kanon des Informatikunterrichts der Klasse 9 mit 4Wochenstunden ein:

1. Halbjahr: Webseitengestaltung mit HTML und CSS: Gewöhnung an geschachtelte Strukturen,Gestaltung einer Website.

2. Halbjahr: Einführung in die Programmierung mit JavaKara: Programmstrukturen, Variablen, Felder, Sortieralgorithmen, Rekursion.

3. Halbjahr: Einführung in JavaScript:Verwendung des HTML-DOMs und ereignisgesteuerter Programmierung,Programmierprojekt: Gesellschaftsspiel (Memory, TicTacToe, Mühle, Minesweeper oderähnliches).

4. Halbjahr: Javaprogrammierung: Anwendungen mit eigenem Fenster,OOP, Ereignissteuerung, GUI mit AWT, Computergrafik

Naheliegend ist ein Start mit der Einführung der while-Struktur,um Kara zu einer Markierung (etwa einem Blatt) laufen zu lassen. Besonderseignen sich im weiteren Verlauf Probleme aus dem „Irrgarten”-Sortiment, andenen die Schüler üben, Lösungsstrategien zu entwickeln, die sie verfeinern und über Struktogrammeschließlich bis zum Code führen. Exemplarisch dafür ist Lösung „Immer an der Wand lang” für nichtzyklische Labyrinthe: Man versetze die Schüler in die Lage desKäfers, in dem man ihnen das Problem stellt, in einem finsteren,unbekannten Raum den Ausgang zu finden, wobei sie sich nur aufihren Tastsinn verlassen können. In der Regel kommen die Schülerselbst auf die Strategie „Immer an der Wand lang”, sie müssen diesedann verbalisieren und schrittweise genauer formulieren, bis die

Strategie sich in einen Algorithmus fassen lässt.


Rekursion

Rekursion vs. Iteration

Schon einige der ersten höheren Programmiersprachen, also solche, die die Implementierung vonMethoden erlauben, kannten den Selbstaufruf der Methode innerhalb ihrer eigenen Deklaration. Dochselbst in Java, eine Sprache, in der sich weitgehend das System um Sicherheit, Kontrolle undSpeicherverwaltung kümmern muss, kann der endlose Selbstaufruf nicht abgefangen werden und führt beiunsachgemäßer Anwendung zum Stack-Overflow und damit schlimmstenfalls zum Absturz des Rechners.Die Iteration kommt in der Regel mit einer definiert endlichen Speichermenge aus, ein Stack-Overflow istnur vorsätzlich aber nicht fahrlässig zu erzeugen. Schülern fällt es schwer, den Rekursionsbegriff zubegreifen und rekursiv Probleme zu lösen, zu Anfang greifen sie immer lieber auf iterative Verfahrenzurück. Daher muss bei der Einführung der Rekursion möglichst gleich zu Anfang Probleme auftauchen,die sich rekursiv sehr kurz und elegant lösen lassen, iterativ aber nur sehr umständlich und arbeitsintensiv.Beispiele für sehr effiziente, kurze Rekursionen sind die „Türme von Hanoi”, das Euler-Verfahren zurBestimmung des ggT zweier Zahlen und das Füllen einer beliebigen, einfarbig zusammenhängendenPixelfläche: Die rekursiven Kerne der Lösungen dieser Beispiele lassen sich jeweils mit weniger als zehnZeilen implementieren und entfalten bei der Ausführung enorme Kraft und Effektivität.

Modell der impliziten Speicherung

Der Programm-Stack in der Laufzeitumgebung dient der Steuerung vonUmterprogrammaufrufen: Wird ein Unterprogramm aufgerufen, wird dieAdresse des ersten Befehls des Unterprogramms im Hauptspeicher in denProgrammzeiger geladen. Damit der Programmzeiger nach Beendigung desUnterprogramms zum Ausgangspunkt, von dem aus das Unterprogrammaufgerufen wurde, zurückfindet, wird zuvor die aktuelle Adresse imProgrammzeiger auf den Stack gelegt. Bei Beendigung des Unterprogrammswird stets ein ret (return)-Befehl ausgeführt, der die oberste Adresse vomStack nimmt und zurück in den Programmzeiger lädt. Der Programmschritt-Inkrement sorgt dafür, dass das Programm an der Stelle nach dem Aufruf desUnterprogramms fortgesetzt wird.

Ist das Unterprogramm nun rekursiv, enthält es also einen Sprungbefehl zuseiner eigenen Startadresse, so wird mit jedem neuen Aufruf eine Adresse aufdem Stack abgelegt. Die Anzahl der Adressen auf dem Stack, bzw. der Wertdes Stackzeigers ist eine Größe, die Information enthält, die vom laufenden Programm benutzt wird. Inder Regel ist diese in der rekursiven Lösung nur implizit verwendete Information (implizit, da diese Größenicht vorsätzlich oder zugreifbar im Programm verwaltet wird) gerade die, die zur Steuerung einerSchleife der korrespondierenden iterativen Lösung explizit angegeben oder errechnet werden muss. Die


Struktur der Rekursion dient selbst also als Informationsspeicher für die Ausführung des Programms. Diesist im einführenden Problem „Hin und wieder zurück” besonders deutlich zu erkennen und kann daranmit den Schülern erarbeitet werden.

Unterrichtsreihe

Die Reihe zur Einführung der Rekursion umfasst drei zentrale Probleme, zu denen Lösungenentwickelt und implementiert werden. Das erste Problem „Hin und wieder zurück” ist so einfach, dass dieSchüler die iterative Lösung selbst entwickeln und nach gemeinschaftlicher Erarbeitung der rekursivenLösung beide Lösungen gegenüberstellen können. Das zweite Problem „Labyrinth rekursiv” vermitteltdann die Vorteile des rekursiven Algorithmus bei speziell strukturierten Problemen. Das dritte Problemdes „Füllens” einer beliebigen, einfarbigen Pixelfläche zeigt die Macht der Rekursion und gleichzeitig ihreSchwäche: Einerseits ist das „Füllen”-Problem iterativ mit vertretbarem Aufwand nicht zu lösen,andererseits benötigt die rekursive Lösung bei großen Flächen (1024×768 = 786432 Pixel)hudertausende von rekursiven Aufrufen, die bei den üblichen Rechnern in der Regel einen „stackoverflow” verursachen und so, wenn nicht den Rechner, doch zumindest das Programm zum Absturzbringen.

„Hin und wieder zurück” – Einführung

Ein Aufgabenbeispiel, wo eine iterative Lösung praktischer erscheint,das sich aber gut dazu eignet den Unterschied zwischen Rekursion undIteration zu diskutieren, ist das Problem des „Hin und wieder zurück”:

Kara soll gerade auf einen Baum zulaufen, dort umkehren und genau zu dem Feld zurückkehren, von demKara gestartet ist. Dabei darf es keine Rolle spielen, wie viele Felder der Baum von der Ausgangspositionentfernt ist. Dazu können die Schüler verschiedene Lösungsansätze selbst entwickeln, wobei sie in derRegel iterative Lösungen vorschlagen, zum Beispiel:

1. Markierung des Ausgangsfeldes: Kara legt ein Kleeblatt auf sein Ausgangsfeld, dann läuft er biszum Baum, dreht sich um und läuft, bis er auf einem Kleeblatt steht.

2. Messen der Entfernung: Kara zählt die Felder bis zum Baum und merkt sich den Wert. Vor demBaum dreht sich Kara um und läuft so viele Schritte zurück, wie gezählt wurden. Schade, dass wir nochnicht gelernt haben, wie Kara zählen und sich eine Zahl merken kann.

Beide Lösungen verlangen in irgendeiner Form einen Speicher, in dem Kara sich die Ausgangspositionmerken kann. Verbietet der Lehrer solche „Hilfen”, wird das Problem komplizierter. Damit wird dann dierekursive Lösung motiviert. Die Lösung lässt sich auf der Kara-Welt gut grafisch entwickeln, dazu eignetsich als Einführung folgende Parodie:

„Einem Mathematiker und einem Ingenieur werden an einem Lagerfeuer jeweils die selben Aufgabengestellt:

1. Ein Topf mit Wasser steht an Position A. Bringe das Wasser zum kochen! - Der Ingenieur nimmt den


public class HinUndWiederZurueckextends JavaKaraProgram {

void geheZumBaumUndZ() { if (kara.treeFront()) { kara.turnLeft(); kara.turnLeft(); } else { kara.move(); geheZumBaumUndZ(); // Rekursion kara.move(); }; };

public void myProgram() { geheZumBaumUndZ(); };};

Topf von Position A und stellt ihn auf das Feuer. - Der Mathematiker nimmt den Topf von Position A undstellt ihn auf das Feuer.

2. Ein Topf mit Wasser steht an Position B, die von A verschieden ist. Bringe das Wasser zum kochen! -Der Ingenieur nimmt den Topf von Position B und stellt ihn auf das Feuer. - Der Mathematiker nimmt denTopf von Position B, stellt ihn auf Position A und hat somit das Problem auf das vorherige zurückgeführt.”

Dieses Grundprinzip des Mathematikers wenden wir jetzt auf unser Problem an. Auf den ersten Blickscheint das Problem, Kara aus einiger Entfernung zum Baum und zurück gehen zu lassen, als zuschwierig, also reduzieren wir für den Anfang das Problem auf ein einfacheres: Wie sieht es aus, wennKara direkt vor dem Baum steht? Überhaupt kein Problem: Kara dreht sich um und fertig.

Jetzt entwickeln wir das Problem rekursiv für zunehmende Entfernungen. Was ist, wenn Kara ein Feldvon dem Baum entfernt steht (was Kara ja nicht weiß)? Ist augenscheinlich zu lösen: Kara geht ein Feldund hat somit das Problem auf das vorherige zurückgeführt. Nach dessen Lösung (umdrehen) mussKara nur noch einmal ein Feld gehen (diesmal in die andere Richtung). Jetzt sehen wir schnell, dass diesesKonzept unser ganzes Problem vollständig löst:

Kara geht ein Feld, hat das Problem auf das Problem mit einem Feld weniger zurückgeführt und nachdessen Lösung geht Kara noch einmal ein Feld.

Analog zur vollständigen Induktion wird das Problem also vom Fall „Entfernung gleich Null” anentfaltet.

„Gehe zum Baum und zurück” bedeutet jetzt im Einzelnen:

- Steht Kara schon vor dem Baum, dann

drehe er sich um.

- Steht Kara nicht vor dem Baum, dann

gehe einen Schritt,

gehe zum Baum und zurück und

gehe einen Schritt ( in die andere Richtung).

Der Selbstaufruf der Definition stellt die Rekursion dar, diesich terminiert durch den Fall, dass Kara vor dem Baum steht.

Bei dieser rekursiven Lösung braucht Kara weder eine Markierung noch eine Variable. Wie aber wirddie Information über das Ausgangsfeld gespeichert? Irgendwo muss sie sein, da sie ja offensichtlich nichtverloren geht, sonst würde Kara ja nicht zum Ausgangsfeld zurückfinden.

Die Information wird (im Gegensatz zur expliziten Speicherung über den Befehl „merke Dir!”)implizit, also quasi unauffällig und nebenbei, in der Zahl der verschachtelten Selbstaufrufe gespeichert.Bei einer Entfernung von ca. fünf Feldern lässt sich diese Verschachtelung auch vollständig grafischillustrieren. Versierte Schüler kommen schnell dahinter, dass diese Methode sehr viel mehr Speicherverbraucht als eine Variable zu definieren oder ein Kleeblatt zu hinterlegen, wird doch mit jedemSelbstaufruf der Programmzustand auf den Stack geschoben und ein neuer Programmzeiger gesetzt. Dader Programmieraufwand sich mit den iterativen Lösungen die Waage hält ist also nicht einzusehen,warum Rekursion sinnvoll sei. An diesem Punkt leite der Lehrer dann zu komplexeren Problemen wie


„Labyrinth rekursiv” über, deren rekursive Lösung aus wenigen Zeilen besteht, deren iterative Lösungenaber überhaupt nur schwer zu entwickeln sind.

„Labyrinth rekursiv” – Anwendung

Wir haben im Laufe des Anfangsunterrichts zur Methodikdes Programmierens bereits ein Labyrinth mit der Strategie„Immer an der Wand lang” gelöst (s.o.). Diese Strategie ist insofern unbefriedigend, da die Schüler sehr schnell feststellen,dass man ohne Schwierigkeiten ein Labyrinth bauen kann, indem Kara bis in alle Ewigkeit nach dem Kleeblatt sucht und esnicht finden kann, da das Labyrinth nicht aus nur einer sondern

aus mehreren (unzusammenhängenden) Wänden besteht und das Kleeblatt gerade an einer anderen Wandals der abgetasteten liegt. Die Frage nach einer besseren Strategie führt schnell zur „Hänsel und Gretel”-Strategie: Kara hinterlege eine Spur, die kennzeichnet, ob Kara ein Teillabyrinth bereits untersucht hat.

(Einige Schüler meinten, diese Strategie solle besser „Ariadne”-Strategie heißen, da es sonst eine Verschwendung von Lebensmittelnbedeuten würde. Wir haben uns dann darauf verständigt, die Strategie„Hänsel und Gretel” zu nennen für den Fall, das die Spur nur gelegtaber nicht wieder eingesammelt wird, aber „Ariadne”, wenn die Spurgemäß des roten Fadens im Labyrinth des Minotaurus beimzurückgehen wieder aufgerollt, äh, eingesammelt wird. Wir werdensehen, dass Einsammeln zur Lösung nicht beiträgt, aber auch keinenbesonderen Aufwand bedeutet. Einsammeln hat jedoch zwei Vorteile:Zum Einen ist das Labyrinth im Anschluss der Lösung einigermaßensauber, zum Anderen wird ein direkter Weg vom Ausgangspunkt zumZiel markiert, dem andere folgen könnten.)

Um eine Spur hinterlegen zu Können, die sich vom Zielunterscheidet (wir erinnern uns: Wir suchten oben nach einemKleeblatt unter lauter Bäumen), Soll Kara im Baumlabyrinth jetztnach einem Pilz suchen, so kann er aus Kleeblättern die Spurlegen. Die Strategie: Steht Kara auf einem Feld und hat den Pilznoch nicht gefunden, so markiert er dieses als schon durchsuchtund wendet sich dann nacheinander dem Labyrinth hinter demvorderen, dem linken und dem rechten Durchgang zu, bevor Karasich umwendet, die Markierung wieder entfernt und sich auf denRückweg macht. Der Ablauf soll gestoppt werden, sobald der Pilzgefunden wurde, dazu implementieren wir die Methode so, dass sieals Rückgabewert den Erfolg/Misserfolg an die aufrufendeMethode weitergibt.

public class LabyrinthRekursivextends JavaKaraProgram {

void turnU() { kara.turnLeft(); kara.turnLeft(); };

boolean fandnPilz() { if (kara.onLeaf()) { //schon durchsucht, schnell zurück! turnU(); } else { kara.putLeaf(); Kara.turnLeft(); for (int i = 0; i < 3; i=i+1) { // drei Richtungen untersuchen: if (kara.mushroomFront()) { return true; } else if (kara.treeFront()) { turnU(); } else { kara.move(); if (fandnPilz()) { return true; } else { kara.move(); }; }; kara.turnLeft(); }; // bereit zur Rückkehr: kara.removeLeaf(); // Ariadne }; return false; // nichts gefunden };

public void myProgram() { fandnPilz(); };};


„Füllen” – Vertiefung

Diese Aufgabe ist geeignet, um Schülern ,die das Prinzip derRekursion durchschaut haben, die Gelegenheit zu geben, selbsteine Rekursive Lösung zu entwickeln. Es geht darum, das Karaeine beliebige von Bäumen eingegrenzte Fläche mit Kleeblättern

restlos füllen soll. Sicher wirdes Wider-stand von einigenSchülern geben, das Problemließe sich mindestens genausogut iterativ lösen, diese kannman dann getrost machenlassen, eine iterative Lösung, die alle Eventualitäten berücksichtigt,werden die Schüler in angemessener Zeit auch nicht annäherndhinbekommen. Der rekursive Ansatz hat hier große Vorteile und istrelativ einfach zu erkären:

Strategie: Wenn Kara auf einem Kleeblatt steht, drehe Kara um undgehe zurück. Im anderen Fall lege Kara auf seine Position einKleeblatt und fülle (rekursiv) die vier Nachbarfelder, wenn auf diesenkein Baum steht.

Der schwierigste Teil ist nicht die Rekursion, sondern in derImplementierung Karas Stellung zu verfolgen und Kara richtig zudrehen und zu bewegen.

Weitere Aufgaben zur Rekursion

„Die Türme von Hanoi”

Der Klassiker der rekursiven Problemstellungen: Auf einem von drei Plätzen steht ein Turm ausaufeinander geschichteten, nach oben kleiner werdenden Scheiben. Aufgabe ist es, den Turm auf einen deranderen Plätze zu bewegen unter folgenden Bedingungen: 1. Es darf nur jeweils die oberste Scheibe einesStapels bewegt werden. 2. Eine Scheibe darf nur auf einen leeren Platz oder auf eine größere Scheibegelegt werden.

Die rekursive Lösung der Aufgabe reduziert ein Problem von n Scheiben darauf, die unterste der

public class Fuellenextends JavaKaraProgram {

void fuelle() { if (kara.onLeaf()) { kara.turnLeft(); kara.turnLeft(); } else { kara.putLeaf(); kara.turnLeft(); // vier Nachbarfelder: for (int i = 0; i < 4; i=i+1) { if (kara.treeFront()) { kara.turnLeft(); kara.turnLeft(); } else { kara.move(); fuelle(); kara.move(); }; kara.turnLeft(); }; kara.turnLeft(); }; };

public void myProgram() { fuelle(); };


Scheiben zu versetzen, in dem man den darüberliegenden Turmvon (n – 1) Scheiben auf dem dritten Platz zwischenlagert. Mangelangt zu folgendem Algorithmus:

versetze Turm aus n Scheiben von Platz p nach Platz q{wenn (n > 1) {

r sei der dritte Platz neben p und q;versetze Turm aus n–1 Scheiben von Platz p nach Platz r;bewege oberste Scheibe von Platz p nach Platz q;versetze Turm aus n–1 Scheiben von Platz r nach Platz q;

} sonst {bewege oberste Scheibe von Platz p nach Platz q;

};};

Hierzu lässt sich auch eine iterative Lösung implementieren, dieaber nicht ganz einfach zu entdecken ist (siehe Kasten rechts, werwill, kann sie ja analysieren).

ggT mit Euler

Den mathematische Satz „Der größte gemeinsame Teiler von zwei natürlichen Zahlen ist auch der größtegemeinsame Teiler jeder der beiden Zahlen mit ihrer Differenz.”

ggT(a, b) = ggT(a, |a–b|) = ggT(b, |a–b|) V a, b C IN

hat Euler zu dem rekursiven Algorithmus zur Bestimmung des größtengemeinsamen Teilers zweier Zahlen entwickelt. Durch die sukzessiveAnwendung der des Satzes als

ggT(a, b) = ggT(min(a, b), |a–b|)kann er die Zahlen a und b so weit verkleinern, bis sie sich bei ihrem ggTtreffen, und sei dieser 1.

An den Implementierungen rechts sehen wir, dass rekursive unditerative Form sich sowohl vom Aufwand als auch vom Algorithmus hersehr ähneln. Die gegenüberstellende Analyse der Implementierungenrückt Themen wie Speicherbedarf und Schnelligkeit der Methoden in denFokus der Diskussion, lassen sich doch in beiden Fällen sowohl Ablaufals auch Speicherabbilder an konkreten Beispielen leicht Schritt fürSchritt verfolgen.

int lowestBit(int i) { //Hilfsmethode// ermittelt niedrigstes Bit = 1 der // binären Darstellung von i int n = 0; while (i%2 == 0) { i = i >> 1; n++; }; return n;};// iterativpublic int hanoi(int n) {// Bewegt n Scheiben.// Die Plätze haben die Nummern // 0, 1 und 2. int[] platz = new int[n];// Merkt sich den aktuellen Plätze // der n Scheiben. Initialisierung// mit p für alle Scheiben: for (int i = 0; i < n; i++) { platz[i] = 0; };// Iteration über 2^n - 1 Bewegungen: for (int i = 1; i < (1 << n); i++) { // Scheinbennummer berechnen: n = lowestBit(i); // Scheibe bewegen: platz[n] = (platz[n]+1+n%2)%3; zeichneTuerme(platz); // Anzeige };};

// rekursivpublic int ggT(int a, int b) { if (a == b) { return a; } else if (a > b) { return ggT(b, a-b); } else { return ggT(a, b-a); };};

// iterativpublic int ggT(int a, int b) { while (a != b) { if (a > b) { a = a - b; } else { b = b - a; }; }; return a;};


Quellen

[1] Eindgenössische Technische Hochschule Zürich, Bereich Edukation, Fach Informatik

„Informatik auf educETH - JavaKara: Einführung in Java”

http://www.educeth.ch/informatik/karatojava/javakara/ , 15.7.2004

Documents

Hans Peter Schneider · Die JavaKara-Umgebung wurde programmiert für die von Objektorientierung ungestörte Einführung in die sequentielle Programmierung mit C-Strukturen, die der