Hamster-ProgrammierungSeite 151 Hochschule Harz © Prof. Dr. Bernhard Zimmermann Fachbereich Automatisierung und Informatik Prof. Dr. Sigurd Günther Hamster-Modell

Hamster-ProgrammierungSeite 1

Hochschule Harz © Prof. Dr. Bernhard ZimmermannFachbereich Automatisierung und Informatik Prof. Dr. Sigurd Günther

Hamster-Modell

Auswahlanweisungen Wiederholungsanweisungen Boolesche Methoden Strukturieren von Programmen Hamster mit Gedächtnis (Boolesche Variablen) Hamster mit Gedächtnis (Zahlen) Integer-Methoden

Verallgemeinerungen von Daten und Methoden

Prozeduren und Methoden mit Parametern

Prozeduren und Methoden, die sich selbst aufrufen (Rekursion)



Hamster-Modell / Methoden

Wiederholung: Testmethoden– liefern ein Ergebnis vom Typ boolean– benutzen eine boolesche return-Anweisung

Methoden können auch andere Informationen als Ergebnis liefern– die Anzahl gesammelter Körner

– zurückgelegte Schritte

– überwundene Höhenstufen

– …



Hamster-Modell / Methoden / return-Anweisung

Integer return-Anweisung– liefert den Wert einer int-Methode

return arithmetischer Ausdruck;

Semantik (Bedeutung):1. Der Wert des arithmetischen Ausdrucks wird berechnet.

2. Die Ausführung der int-Methode wird beendet.

3. Der Wert des arithmetischen Ausdrucks wird als Ergebnis der int-Methode wird zurückgegeben.

Beispiele:return -4;

return 3 * (4-5);

return i * (i + 1);



Hamster-Modell / Methoden / Definition

Definition von int-Methoden– Syntax ist identisch zu Test-Methoden

int Methodenname() { Anweisungsfolge }

Methodenkopf Methodenrumpf

Zusatzbedingung: – In jedem möglichen Weg durch den Methodenrumpf muss eine

Integer return-Anweisung stehen!



Hamster-Modell / Methoden / Beispiel

Anzahl der Körner im Maul ermitteln:

int AnzahlKoernerImMaul(){

int anzahl = 0;

while (!maulLeer()) { // Koerner ablegen + zaehlen gib(); anzahl = anzahl + 1; }

// Koerner wieder aufnehmen, sonst Seiteneffekt

int i = anzahl; while (i > 0) { nimm(); i = i – 1; }

return anzahl; // ermittelte Anzahl zurueckgeben

}



Hamster-Modell / Methoden / Aufruf

Methodenaufruf– wie bei booleschen Methoden

methodenName();

Ort des Aufrufs:– int-Methoden dürfen überall dort aufgerufen werden, wo

arithmetische Ausdrücke stehen dürfen. Semantik (Bedeutung):

– Ausführen des Methodenrumpfes

– Der von der Methode zurückgegebene Wert wird an der Stelle im Programm verwendet, an der der Methodenaufruf stand.

Beispiel:if (anzahlKoernerImMaul() < 5) gib();



Hamster-Modell / Methoden / Beispiele

Aufgabe 25: Situation– Der Hamster steht direkt vor einem regelmäßigen Berg

unbekannter Höhe. Er selbst hat keine Körner im Maul. Auf der Kachel, auf der er steht, liegt eine bestimmte Anzahl Körner. Ansonsten liegen keine Körner im Feld.

Auftrag:– Der Hamster soll den Berg erklimmen und dabei solange wie

möglich auf jeder Stufe ein Korn ablegen. Er soll dabei jedoch keinen unnötigen Ballast mitschleppen.




Aufgabe 25– Der Hamster soll den Berg erklimmen und dabei solange wie

möglich auf jeder Stufe ein Korn ablegen. Er soll dabei jedoch keinen unnötigen Ballast mitschleppen.

Lösungsidee– Der Hamster ermittelt zunächst die Höhe des Berges und kehrt

an seine Ausgangsposition zurück.

– Anschließend nimmt er falls möglich die benötigte Körnerzahl auf und marschiert erneut los.




Teilaufgaben– Berg hinaufklettern und absteigen

● Stufe aufsteigen

● Stufe absteigen

● Test-Methode für „Gipfel erreicht“

– Stufen zählen




Lösung: Stufen zählen:int zaehleStufen() {

// erklimme die Stufen und merke die Anzahl int anzahl = 0;

while (!gipfelErreicht()) { erklimmeStufe(); anzahl = anzahl + 1; }

// zur Vermeidung von Seiteneffekten wieder absteigen

kehrt(); int schritte = anzahl;

while (schritte > 0) { klettereStufeHinunter(); schritte = schritte - 1; }

kehrt();

return anzahl; }




Lösung für das Hauptprogramm:void main() {

int stufen_anzahl = zaehleStufen();

// nimm genuegend Koerner ins Maul

while ((stufen_anzahl > 0) && kornDa()) { nimm(); stufen_anzahl = stufen_anzahl - 1; }

erklimmeBergUndVerteile();

}

Verteilen der Körner: void erklimmeBergUndVerteile() { while (!gipfelErreicht()) { erklimmeStufe(); if (!maulLeer()) gib(); }

}




Hilfsmethoden:boolean gipfelErreicht(){ return vornFrei();}

void erklimmeStufe(){ linksUm(); vor(); rechtsUm(); vor();}

void klettereStufeHinunter(){ vor(); linksUm(); vor(); rechtsUm();}




Aufgabe 26– Der Hamster steht in einem durch Mauern abgeschlossenen

Raum unbekannter Größe. Solange auf einem seiner vier Nachbarfelder (links, rechts, oberhalb, unterhalb) noch Körner liegen, soll er folgendes tun: Er soll das Nachbarfeld ermitteln, auf dem die meisten Körner liegen, sich dorthin bewegen und die Körner fressen.




Aufgabe 26 -Teilaufgaben– Solange auf einem seiner vier Nachbarfelder (links, rechts,

oberhalb, unterhalb) noch Körner liegen, soll er folgendes tun: Er soll das Nachbarfeld ermitteln, auf dem die meisten Körner liegen, sich dorthin bewegen und die Körner fressen.

Teilaufgaben (Seiteneffekte vermeiden)– Feld mit meisten Körnern ermitteln (Blickrichtung beibehalten)

– Körner vor dem Hamster ermitteln (Position und Blickrichtung beibehalten)




Teilaufgabe: Feld mit den meisten Körnern ermitteln– Richtung mit den meisten Körnern ermitteln

(Anzahl der Linksdrehungen: 0 .. 3)

– Sonderfall: „keine Körner“

● Rückgabe: -1

– In jeder Blickrichtung die Körner vor dem Hamster zählen (danach wieder hinlegen)

– Richtung mit den meisten Körnern merken

● Vorhergehende Anzahl mit aktueller Anzahl vergleichen

● Falls aktuell mehr Körner

=> aktuelle Richtung hat Maximum

● nächste Richtung betrachten




Aufgabe 27: Situation– Der Hamster steht irgendwo in einem abgeschlossenen

mauerlosen rechteckigen Raum unbekannter Größe. Er hat eine bestimmte Anzahl Körner im Maul. Im Feld liegen keine Körner.

Auftrag:– Der Hamster soll zunächst die Größe des Raumes ermitteln.

– Anschließend soll er, falls er genügend Körner im Maul hat, auf den Randkacheln des Raumes jeweils ein Korn ablegen.




Teilaufgaben:– in eine Ecke laufen

– Breite und Höhe des Rechtecks ermitteln (Länge einer Seite)

– Körner im Maul bestimmen

– Körner auf Randfeld (Zeile) ablegen

Aufgabe 27:– Der Hamster soll zunächst die Größe des Raumes ermitteln.

– Anschließend soll er, falls er genügend Körner im Maul hat, auf den Randkacheln des Raumes jeweils ein Korn ablegen.



Hamster-Modell

Auswahlanweisungen Wiederholungsanweisungen Boolesche Methoden Strukturieren von Programmen

Hamster mit Gedächtnis (Boolesche Variablen) Hamster mit Gedächtnis (Zahlen) Integer-Methoden

Verallgemeinerungen von Daten und Methoden

Prozeduren und Methoden mit Parametern

Methoden, die sich selbst aufrufen (Rekursion)



Hamster-Modell / Variablen / Datentypkonzept

Weitere Datentypen in Java für – reelle Zahlen

– Buchstaben

– Zeichenketten (Texte) Variablen (allgemein):

– sind Behälter für Werte

● benötigen Speicherplatz

● der Name identifiziert den Behälter (Speicherplatz)

– haben einen Typ

=> definierter Wertebereich

=> erlaubte Operationen

– werden initialisiert (automatisch oder explizit)

– können durch Zuweisung andere Werte bekommen

– können nur mit Variablen des gleichen Typs verknüpft werden




Definition von Variablen

<Datentyp> Variablen_Name = <Ausdruck> ;

<Datentyp> ist ein Platzhalter für eine Typbezeichnung

=> int

oder => boolean

<Ausdruck> ist ein Platzhalter für einen Ausdruck, der den gleichen Ergebnistyp hat wie die

Variable Gültigkeitsbereich von Variablen

– ist abhängig vom Ort der Definition

– lokale Variablen werden innerhalb von Methoden definiert

– globale Variablen werden außerhalb von Methoden definiert (im Definitionsteil eines Programms)




Eine Zuweisung ändert den Wert einer Variablen:

variablen_name = <Ausdruck> ;

Zusatzbedingungen:– Variable und Ausdruck müssen vom gleichen Typ sein!

Semantik:– Ausdruck auf der rechten Seite berechnen (rechts von „=“ )

– Ergebnis in der Variable speichern

– Der zugewiesene Wert wird als Ergebnis geliefert!

Beispiele:int i1; int i2; int i3;

i1 = i2 = i3 = 3;

if ((i1 = i1 + 1) == (i1 = i1 - 1))

Auch Zuweisungen können als Ausdruck benutzt werden!

Die Reihenfolge der Berechnung der Ausdrücke ist wichtig!




Ausdrücke – sind Verarbeitungsvorschriften zur Ermittlung eines Wertes

– können Ergebnisse unterschiedlichen Typs liefern Typen

boolesche Ausdrücke => boolean

arithmetische Ausdrücke => int Varianten von Ausdrücken

=> Variablenname

oder => Methodenaufruf

oder => Testbefehl

oder => <unärer Operator> Ausdruck

oder => Ausdruck <binärer Operator> Ausdruck

oder => ( Ausdruck )

oder => Zuweisungsausdruck




Operatoren mit Prioritäten für die Ausführung bei Ausdrücken

Prio. Op. Operanden Erg. Typ Funktion

1 +,- int int Vorzeichen

1 ! boolean boolean log. Negation

2 *,/,% int int Punktrechenarten

3 +,- int int Strichrechenarten

4 <,<=,>,>= int boolean Vergleichsop.

5 ==,!= int boolean Gleichheitsop.

6 && boolean boolean log. UND

7 || boolean boolean log. ODER

8 = int int Zuweisung

8 = boolean boolean Zuweisung



Hamster-Modell / Methoden / Verallgemeinerung Methoden können Ergebnisse unterschiedlicher Art (Datentypen)

liefern– boolean– int – void

Syntax der Definition und return-Anweisungen sind identisch boolean rechtsFrei() { boolean testWert; . . .

return testWert; }

int anzahlKoernerImMaul() { int anzahl; . . .

return anzahl; }



Hamster-Modell / Methoden / Verallgemeinerung

Verallgemeinerte Form der return-Anweisung– Dem Schlüsselwort return kann ein Ausdruck folgen – muss

aber nicht! Einschränkungen:

– return-Anweisungen mit einem booleschen Ausdruck dürfen nur in booleschen Methoden stehen.

– return-Anweisungen mit einem int-Ausdruck dürfen nur in int-Methoden stehen.

– return-Anweisungen ohne Ausdruck dürfen nur in Prozeduren stehen.




Verallgemeinerte Form der Methodendefinition

<Typ> methodenName(){ Anweisungsfolge }

Zusätzliche Bedingungen:– Ist der Typ der Methode void (handelt es sich also um eine

Prozedur),

● dürfen im Methodenrumpf nur return-Anweisungen ohne Ausdruck auftreten.

– Hat die Methode einen anderen Typ,

● so müssen alle return-Anweisungen im Methodenrumpf Werte liefern, die zum Methodentyp passen.

● In jedem möglichen Weg durch die Methode muss eine return-Anweisung passenden Typs auftreten.




Verallgemeinerte Form des Methodenaufrufs– Methodenaufrufe sind spezielle Ausdrücke

Einschränkungen:– Methodenaufrufe dürfen nur für Operanden benutzt werden, die

den gleichen Typ haben

● boolean-Methode für booleschen Operanden

● int-Methoden für arithmetischen Operanden

– Prozeduren (void) dürfen nur anstelle von Anweisungen stehen



Hamster-Modell

Auswahlanweisungen Wiederholungsanweisungen Boolesche Methoden Strukturieren von Programmen Hamster mit Gedächtnis (Boolesche Variablen) Hamster mit Gedächtnis (Zahlen) Integer-Methoden Verallgemeinerungen von Daten und Methoden Prozeduren und Methoden mit Parametern




Hamster-Modell / Methodenparameter

Bisher benutzte Möglichkeiten von Methoden– Aktivitäten zusammenfassen in Prozeduren

– Testmethoden mit booleschen Ergebnissen

– Methoden, die Zahlenwerte bestimmen Wie kann man den „Auftrag an den Hamster“, also die

Aktivitäten in einer Methode oder einer Prozedur, noch besser steuern?– Der Hamster soll 4 Schritte vorwärts gehen!

– Der Hamster soll 3 Körner einsammeln!

– Der Hamster soll 2 Schritte vorwärts laufen und 3 Körner sammeln!

– . . .



Hamster-Modell / Methodenparameter / Motivation

void vierVor(){ int schritte = 0;

while (schritte < 4 && vornFrei()) { vor();

schritte = schritte + 1;

}

}

Aufgabe: – Der Hamster soll 6 Schritte vorwärts gehen, falls möglich!

Änderung in der Prozedur: . . . while (schritte < 6 && vornFrei()) {

Aufgabe: – Der Hamster soll 4 Schritte vorwärts gehen, falls möglich!



Hamster-Modell / Methodenparameter / Motivation

void anzahlVor()

{

// erwarte einen int-Wert "Anzahl"

int schritte = 0; while ((schritte < Anzahl) && vornFrei()) { vor(); schritte = schritte + 1; }}

Problem: Wie übermittelt man die Anzahl der Schritte?– Globale Variablen sind ungünstig wegen der unbeabsichtigten

Änderungen in anderen Programmteilen.

– Übergabe der Anzahl beim Aufruf als Parameter

Aufgabe: – Der Hamster soll eine variable Anzahl Schritte vorwärts gehen,

falls möglich!



Hamster-Modell / Methodenparameter / Definition

Definition: (formale) Parameter – sind lokale Variablen von Methoden,

– die dadurch initialisiert werden, dass der Methode bei ihrem Aufruf ein entsprechender Initialisierungswert für die Variable übergeben wird.

Syntax einer Methodendefinition mit 1 Parameter

<Typ> methodenName(Datentyp formalerParameterName){

Anweisungsfolge}



Hamster-Modell / Methodenparameter / Beispiel

Beispiel für Methode mit einem Parameter:

void anzahlVor(int anzahl)

{

int schritte = 0; while ((schritte < anzahl) && vornFrei()) { vor(); schritte = schritte + 1; }}

– Der Parameter (die Variable) anzahl kann bei jedem Aufruf unterschiedliche Werte haben!

Wie ruft man Methoden mit Parametern auf?



Hamster-Modell / Methodenparameter / Aufruf

Aufruf einer Methode

Semantik (call-by-value-Parameterübergabe):– Der Wert des aktuellen Parameters wird ermittelt.

– Für den formalen Parameter wird im Methodenrumpf eine lokale Variable angelegt.

– Die lokale Variable wird mit einer Kopie des Wertes des aktuellen Parameters initialisiert.

aktueller Parameter– muss den gleichen Typ wie der formale Parameter haben

– erlaubt sind

● Werte, Variablen, Ausdrücke, Methodenaufrufe, . . .

methodenName(aktuellerParameter);



Hamster-Modell / Methodenparameter / Aufruf

Beispiele:void main() {

anzahlVor(5); anzahlVor(7 * 3 - 17);

// es gibt die Methode int anzahlKoernerImMaul()

anzahlVor(anzahlKoernerImMaul());

int anzahl = 4; anzahlVor(anzahl);

} Der Wert einer als aktueller Parameter übergebenen

Variablen kann durch den Aufruf einer Methode nicht geändert werden, auch dann nicht, wenn formaler und aktueller Parameter den gleichen Namen haben!

– Variable anzahl im Programm bleibt unverändert!



Hamster-Modell / Methodenparameter / Beispiele

void drehDich(int grad) {

// Der Hamster dreht sich "grad"-mal

int anzahl_drehungen = grad / 90;

while (anzahl_drehungen > 0) {

linksUm();

anzahl_drehungen = anzahl_drehungen - 1;

}

}

void main() {

int links = 90;

int kehrt = 180;

drehDich(links);

drehDich(kehrt);

drehDich(links+kehrt);

drehDich(100);

}



Hamster-Modell / mehrere Methodenparameter

Syntax der Methodendefinition mit mehreren Parametern

<Typ> methodenName (Datentyp param1,

Datentyp param2, ...){

Anweisungsfolge}

Parameter– Anzahl ist nicht begrenzt

– sind lokale Variablen, die erst beim Aufruf initialisiert werden Beispiel für eine Methode mit 2 Parametern int summe(int wert1, int wert2)

{ return wert1 + wert2;}

formaleParameter-liste



Hamster-Modell / mehrere Methodenparameter

Aufruf einer Methode mit n Parametern

Semantik:– Die Werte aller aktuellen Parameter werden von links nach

rechts ermittelt.

– Eine Kopie der Werte wird an die Methode übergeben. aktuelle Parameter

– müssen gleiche Anzahl und gleichen Typ wie die formalen Parameter haben

– können Werte, Variablen, Ausdrücke, Methodenaufrufe, . . .sein

Beispiele:int ergebnis = 0;

ergebnis = summe( 3, 5 – 6 );

// es gibt die Methode int anzahlKoernerImMaul()

ergebnis = summe(anzahlKoernerImMaul() * ergebnis);

methodenName(aktParam1, aktParam2, ..., aktParamn);



Hamster-Modell / mehrere Methodenparameter / Beispiele

void vertausche(int x, int y) {

// vertauscht die Werte von x und y

int zwerg = x;

x = y;

y = zwerg;

}

void main() {

int zahl1 = 4711, zahl2 = 27;

vertausche(zahl1, zahl2);

}



Hamster-Modell / überladene Methoden

Überladene Methoden

Beispiele:int summe(int op1, int op2) { return op1 + op2;}int summe(int op1, int op2, int op3) { return op1 + op2 + op3;}int summe(int op1, int op2, boolean minus) { if (minus) return -(op1 + op2); else return (op1 + op2); }void main() { summe(2,3); summe(2,3,4); summe(2,3,true);}

In einem Programm dürfen 2 oder mehrere Methoden mit dem selben Namen definiert werden, falls sich ihre formalen Parameterlisten durch- die Parameteranzahl oder - die Datentypen der Parameter unterscheiden.

Eine Unterscheidung allein durch den Ergebnisdatentyp ist nicht erlaubt.



Hamster-Modell / Parametrierte Methoden / Aufgaben

Aufgabe 28 - Situation– Der Hamster befindet sich in einem geschlossenen,

rechteckigen Territorium unbekannter Größe. Im Innern des Territoriums befinden sich keine weiteren Mauern. Auf irgendeinem Feld des Territoriums liegt ein Korn. Der Hamster sitzt anfangs in der linken unteren Ecke mit Blickrichtung Ost.

Aufgabe 28 - Auftrag– Der Hamster soll das Korn finden und fressen.

Aufgabe 28 - Nebenbedingungen– Globale Variablen dürfen zur Lösung nicht benutzt werden.




Aufgabe 27 - Teilaufgaben– einen „Kreis“ mit einem variablen Durchmesser testen

(ein „Kreis“ besteht aus vier Richtungen der Länge Durchmesser)

– eine Richtung mit einem variablen Durchmesser (Länge ) testen

Aufgabe 28 - Lösungsidee– Der Hamster grast das Territorium in zyklischen „Kreisen“ ab.

Irgendwann stößt er dann zwangsläufig auf das Korn und frisst es.




void testeEinenKreis(int durchmesser) { // ein Kreis besteht aus vier Richtungen int richtungen = 0; while (!kornDa() && (richtungen < 4)) { testeEineRichtung(durchmesser); richtungen = richtungen + 1; }}

void testeEineRichtung(int durchmesser) { // die Ueberpruefung einer Richtung besteht aus der // Ueberpruefung von so vielen Feldern, wie der Durchmesser // des Kreises angibt int schritte = 0; while (!kornDa() && (schritte < durchmesser) && vornFrei())

{ vor(); schritte = schritte + 1; } if (!kornDa()) linksUm();}




void main() { int durchmesser = 1; // lokale Variable; speichert die // Groesse des aktuellen Durchmessers while (!kornDa()) { testeEinenKreis(durchmesser ); durchmesser = durchmesser + 1; // nach jeder Runde wird der Durchmesser ein Feld // groesser } nimm();}




Aufgabe 29 - Situation– Im Hamster-Territorium befindet sich ein mit Körnern gefülltes

rechteckiges Teilgebiet. Der Hamster sitzt irgendwo in diesem Körnerfeld mit Blickrichtung Ost.

Aufgabe 29 - Auftrag– Der Hamster soll das Körnerfeld abgrasen.





Aufgabe 29 - Teilaufgaben– Ermittlung der Breite

● Seiteneffekt: der Hamster steht anschließend am Rand des Kornfeldes

– Ermittlung der Höhe

● Seiteneffekt: der Hamster steht anschließend in einer Ecke des

Kornfeldes

– Abgrasung des Kornfelds mit den variablen Ausmaßen Breite und Höhe

– Abgrasung einer Reihe des Kornfelds mit der variablen Höhe

Aufgabe 29 - Lösungsidee– Zunächst bestimmt der Hamster die Größe des Kornfeldes und

merkt sich die Ausmaße. Anschließend grast er die einzelnen Körnerreihen ab, wobei er die ermittelten Werte benutzt.




Aufgabe 29 – weitere Test-Territorien




Aufgabe 30 - Situation– Der Hamster hat eine "verschlüsselte" Schatzkarte gefunden. Der "Schatz"

besteht aus einem ganz besonders leckerem Korn. Nach intensivem Überlegen hat der Hamster den Verschlüsselungsalgorithmus entdeckt. Nun will er sich auf die Schatzsuche begeben.

4 6

25

8




Aufgabe 30 - Lösungsalgorithmus

– Die Anzahl an Körnern auf einer Kachel teilt dem Hamster mit, wie viele Kacheln er in welche Richtung laufen muss.

Ist die Anzahl durch die Zahl 4 teilbar, dann muss der Hamster die der Körneranzahl entsprechende Anzahl an Feldern nach Osten laufen. Dort trifft er erneut auf einen Kornhaufen, der ihm den weiteren Weg andeutet.

Ist die Zahl nicht durch 4, wohl aber durch 3 teilbar, dann ist die einzuschlagende Richtung Norden.

Bei einer weder durch 4 noch durch 3 aber durch 2 teilbaren Zahl, muss sich der Hamster nach Westen durchschlagen. Ansonsten ist die Zielrichtung Süden.

4 6

25

8




Aufgabe 30 - Lösungsalgorithmus

– Der Hamster erkennt den Schatz daran, dass ein gefundener Kornhaufen aus nur einem einzigen Korn besteht.

– Anfangs steht der Hamster mit Blickrichtung Ost im Kornfeld. Außerdem ist sichergestellt, dass der Weg von einem Kornhaufen zum nächsten nicht durch Mauern versperrt ist und dass die Schatzkarte auf jeden Fall korrekt ist.

4 6

25

8





Aufgabe 30 – weitere Schatzkarte

5

4

10

3

1

8

31

4

5

35



Hamster-Modell

Auswahlanweisungen Wiederholungsanweisungen Boolesche Methoden Strukturieren von Programmen Hamster mit Gedächtnis (Boolesche Variablen) Hamster mit Gedächtnis (Zahlen) Integer-Methoden Verallgemeinerungen von Daten und Methoden Prozeduren und Methoden mit Parametern




Hamster-Modell / Rekursion / Motivation

Ein Hund lief in die Küche

Ein Hund lief in die Kücheund stahl dem Koch ein Ei,da nahm der Koch die Kelle

und schlug den Hund entzwei.Da kamen alle Hunde

und gruben ihm ein Grabund setzten einen Grabstein

worauf geschrieben war:

Ein Hund lief in die Kücheund stahl dem Koch ein Ei,da nahm der Koch die Kelle

und schlug den Hund entzwei.Da kamen alle Hunde

und gruben ihm ein Grabund setzten einen Grabstein

worauf geschrieben war:Ein Hund lief in die Küche ...




void hinUndZurueck() { int schritte = 0; // laufe zur Wand while (vornFrei()) { vor(); schritte = schritte + 1; } linksUm(); linksUm(); // kehrt // laufe zurück while (schritte > 0) { vor(); schritte = schritte - 1; }}

void main() { hinUndZurueck();}

Aufgabe– Der Hamster soll bis zur nächsten Wand laufen, kehrt machen und zum

Ausgangspunkt zurücklaufen. Lösung mit Schleifen (iterativ)




void hinUndZurueckR() { if (vornFrei()) { vor(); hinUndZurueckR(); vor(); } else { linksUm(); linksUm(); // kehrt }}

void main() { hinUndZurueck();}

Aufgabe– Der Hamster soll bis zur nächsten Wand laufen, kehrt machen und zum

Ausgangspunkt zurücklaufen. Lösung mit Rekursion

Rekursion– Die Prozedur hinUndZurueckR() ruft sich selbst auf!



Hamster-Modell / Rekursion / Definitionen

Inkarnation einer Funktion– Wird bei der Ausführung eines Programms eine Funktion

aufgerufen, dann wird eine Inkarnation dieser Funktion erzeugt. Nach der vollständigen Abarbeitung der Funktion wird die Inkarnation wieder zerstört.

Rekursive Funktion– Eine Funktion ist rekursiv, wenn zu einem Zeitpunkt während

der Programmausführung 2 oder mehrere Inkarnationen dieser Funktion existieren.

– Eine Funktion heißt direkt rekursiv, wenn sie sich selbst erneut aufruft.

– Eine Funktion heißt indirekt rekursiv, wenn von der Funktion mehrere Inkarnationen existieren, obwohl sich diese nicht selbst aufruft.

Rekursionstiefe– Anzahl der gleichzeitig existierenden Inkarnationen einer

Funktion minus 1



Hamster-Modell / Rekursion / Definitionen

Funktionen mit lokalen Variablen– Jede Funktionsinkarnation arbeitet mit einem eigenen Satz von

lokalen Variablen, insbesondere ist es einer Funktionsinkarnation nicht möglich, auf lokale Variablen anderer Funktionsinkarnationen zuzugreifen. Bei der Zerstörung einer Funktionsinkarnation wird auch deren Satz von lokalen Variablen zerstört.

Funktionen mit Parametern– Auch in rekursiven Funktionen werden Parameter wie lokale

Variable behandelt, wobei die lokale Variable auch hier mit einer Kopie des Wertes des aktuellen Parameters initialisiert wird. In rekursiven Funktionen wird der neuen Inkarnation häufig ein veränderter Parameterwert übergeben. Außerdem wird der Parameterwert in der Abbruchbedingung verwendet.

Endlosrekursion– Im Gegensatz zu Programmen mit Endlosschleifen enden

Funktionen mit einer Endlosrekursion mit einem Laufzeitfehler, weil beim Erzeugen einer Inkarnation stets weiterer Speicherplatz benötigt wird.



Hamster-Modell / Rekursion / Definitionen / Beispiele

void main() { sammle(); laufUndSammle();}void laufUndSammle() { while (vornFrei()) { vor(); sammle(); }}void sammle() { while (kornDa()) nimm();}

Inkarnation

main() laufUndSammle()sammle() sammle() Inkarnationen




void hinUndZurueckR() { if (vornFrei()) { vor(); hinUndZurueckR(); vor(); } else { linksUm(); linksUm(); // kehrt }}void main() { hinUndZurueck();}

Ausführung eines rekursiven Programms

main() hinUndZurueck Inkarnationen

Territorium:



Territorium:Territorium:


void hinUndZurueckR() { if (vornFrei()) { vor(); hinUndZurueckR(); vor(); } else { linksUm(); linksUm(); // kehrt }}void main() { hinUndZurueck();}


main() hinUndZurueck (1)

InkarnationenhinUndZurueck (2) hinUndZurueck (3)

vor();

vor();

vor();

vor();

// kehrt

Territorium:Territorium:Territorium:Territorium:Territorium:Territorium:Territorium:Territorium:Territorium:Territorium:




void sammleR() { if (kornDa()) { nimm(); sammleR(); }}

void main() { sammleR();}


main() sammleR (1)

InkarnationensammleR (2) sammleR(3)

nimm();

nimm();

sammleR(4)

nimm();

Territorium: 3




void hinUndZurueckR() { if (vornFrei()) { laufe(); } else { // kehrt linksUm(); linksUm(); }}void main() { hinUndZurueck();}

Ausführung eines indirekt rekursiven Programms

main() hinUndZurueck (1)

InkarnationenTerritorium:laufe (1) hinUndZurueck (2)

vor();

vor();

vor();

void laufe() { vor(); hinUndZurueckR(); vor();}

laufe (2) hinUndZurueck (3)

// kehrt

vor();




int bisZurMauerR() { if (vornFrei()) { vor(); return bisZurMauerR()+1; } else { return 0; }}

Ausführung einer rekursiven (echten) Funktion– Die Funktion bisZurMauer() lässt den Hamster bis zur Mauer

laufen und liefert die Anzahl der benötigten Schritte als Ergebnis.

main() bisZurMauer (1)InkarnationenTerritorium:

bisZurMauer (2) bisZurMauer (3)

vor();

vor();

return 0 + 1;

return 1 + 1;

return 0;




int anzahlKoernerR() { if (!maulLeer()) { gib(); int anzahl = anzahlKörnerR(); nimm(); // zur Vermeidung von Seiteneffekten return anzahl + 1; } else { return 0; }}

Ausführung einer rekursiven Funktion mit lokalen Variablen– Die Funktion anzahlKoerner() liefert (ohne Seiteneffekte)

die Anzahl der Körner, die der Hamster aktuell im Maul hat.

main() anzahlKoernerR (1)InkarnationenDer Hamster hat 2 Körner im Maul.

gib(); int anzahl

gib(); int anzahl

anzahl = 0; nimm();return anzahl+1;

return 0

anzahlKoernerR (2) anzahlKoernerR (3)

anzahl = 1; nimm();return anzahl+1;




void vorR(int anzahl) { if (anzahl > 0 && vornFrei()) { vor(); vorR(anzahl-1); }}

Ausführung einer rekursiven Prozedur mit Parametern– Die Prozedur vor(int anzahl) lässt den Hamster anzahl

Felder nach vorne laufen, maximal jedoch bis zur nächsten Mauer.

main() vorR (1) Inkarnationen

vor(); vorR(1);

vorR (2) VorR (3)

Territorium:

Aufruf in main(): vorR(2);

vor(); vorR(0);

vorR(2);




// Endlosrekursionvoid sammleR() { if (kornDa()) { sammleR(); nimm(); }}

Endlosrekursion



Hamster-Modell / Rekursion / Beispiele

Aufgabe 31 - Situation– Der Hamster steht direkt vor einem regelmäßigen Berg

unbekannter Höhe. Er hat keine Körner im Maul und im Territorium befinden sich auch keine Körner.

– Der Hamster soll den Berg übersteigen.



Hamster-Modell / Rekursion / Aufgaben Aufgabe 31 – Lösungsidee

– Falls der Hamster schon auf dem Gipfel steht, ist das Problem gelöst.

– Wenn der Gipfel noch nicht erreicht ist, erklimmt der Hamster eine Stufe, wodurch er die Komplexität der Situation verringert hat. Auf die komplexitätsreduzierte Situation wendet er rekursiv den gleichen Algorithmus an. Nach dessen Abarbeitung befindet er sich damit auf der entsprechenden Ebene auf der anderen Seite des Bergs. Er muss also nur noch eine Stufe wieder hinuntergehen und hat das Problem gelöst.



Hamster-Modell / Rekursion / Aufgaben

void main() { uebersteigeBerg();}

void uebersteigeBerg() { if (!gipfelErreicht()) { klettereStufeHoch(); uebersteigeBerg(); // rekursiver Aufruf klettereStufeHinunter(); }}

boolean gipfelErreicht() { return vornFrei();}

void klettereStufeHoch() { linksUm(); vor(); rechtsUm(); vor();}

Aufgabe 31 – Programm




void klettereStufeHinunter() { vor(); rechtsUm(); vor(); linksUm();}

void rechtsUm() { kehrt(); linksUm();}

void kehrt() { linksUm(); linksUm();}

Aufgabe 31 – Programm (Fortsetzung)



Hamster-Modell / Rekursion / Beispiele Aufgabe 32 - Situation

– Der Hamster sitzt in einem beliebig großen, quadratischen Territorium in der linken unteren Ecke mit Blickrichtung nach Osten. Er hat keine Körner im Maul. Irgendwo im Territorium liegt ein Korn.

Aufgabe 32 - Auftrag– Der Hamster soll das Korn finden und fressen.

Aufgabe 32 - Nebenbedingungen– Die Suche soll kreisförmig erfolgen.

– Zur Lösung dürfen keine Wiederholungsanweisungen verwendet werden.



Hamster-Modell / Rekursion / Backtracking

Backtracking– Lösungsverfahren, bei dem versucht wird, eine bereits

gefundene Teillösung T systematisch zur Gesamtlösung L eines gegebenen Problems auszubauen.

T

L

T'

– Falls in einem bestimmten Stadium der Lösungssuche ein weiterer Ausbau einer vorliegenden Teillösung nicht mehr möglich ist (Sackgasse), werden ein oder mehrere der letzten Teilschritte rückgängig gemacht. Die dann reduzierte Teillösung versucht man dann auf einem anderen Weg zu erweitern.

L

T



Hamster-Modell / Rekursion / Backtracking

Backtracking– Das Zurücknehmen von Teilschritten und erneute Probieren

anderer Teilschritte wird solange wiederholt, bis eine Lösung des gegebenen Problems gefunden ist oder erkannt wird, dass keine Lösung existiert.

Versuch-Irrtum-Methode (Try-and-Error-Verfahren)



Hamster-Modell / Rekursion / Backtracking / Beispiele

Aufgabe 33 - Situation– Der Hamster steht am Eingang eines zyklenfreien Labyrinths. Er

soll das Labyrinth nach Körnern durchsuchen. Sobald er ein Korn findet, soll er dies fressen und auf dem schnellsten Weg wieder zum Eingang zurückkehren.



Hamster-Modell / Rekursion / Backtracking / Beispiele

Aufgabe 33 - Lösungsidee

– Der Hamster durchsucht den vor ihm liegenden Gang nach Körnern und kehrt zurück, falls er entweder ein Korn gefunden oder eine Wand erreicht hat.

– Falls er auf seinem Weg nach vorne an eine Abzweigung oder Kreuzung gerät, dreht er sich in die entsprechende Richtung um und versucht zunächst in diesem Gang das Korn zu finden.

– Wenn er an die Abzweigung oder Kreuzung ohne Korn zurückkehrt, versucht er das Korn in einem noch nicht betrachteten Gang zu finden.

– Sobald er das Korn gefunden hat, muss er keine weiteren Gänge durchsuchen und kehrt direkt zum Ausgangspunkt zurück.




void main() { sucheGangAb();}

boolean gefunden = false;

void sucheGangAb() {

// Lösung gefunden? if (kornDa()) { nimm(); gefunden = true; }

// Suche an Kreuzungen if (!gefunden && linksFrei()) { // links vorhandenen Gang absuchen linksUm(); vor(); sucheGangAb(); vor(); linksUm(); } . . .

Aufgabe 33 – Programm




. . .

if (!gefunden && rechtsFrei()) { // rechts vorhandenen Gang absuchen rechtsUm(); vor(); sucheGangAb(); vor(); rechtsUm(); }

if (!gefunden && vornFrei()) { // restlichen Gang absuchen vor(); sucheGangAb(); vor(); // zurücklaufen } else kehrt();}. . .





. . .

boolean linksFrei() { linksUm(); boolean frei = vornFrei(); rechtsUm(); return frei;}

boolean rechtsFrei() { rechtsUm(); boolean frei = vornFrei(); linksUm(); return frei;}

void rechtsUm() { linksUm(); kehrt();}void kehrt() { linksUm(); linksUm();}




Hamster-Modell / Rekursion / Backtracking / Aufgaben

Aufgabe 34 - SituationDer Hamster soll das bekannte Springerproblem lösen:

– Der Hamster steht irgendwo mit 25 Körnern im Maul auf einem eingemauerten Schachbrett-Feld mit 5 Zeilen und 5 Spalten (ohne innere Mauern und ohne Körner auf den Kacheln).

– Er soll entsprechend der Bewegungsmöglichkeiten eines Springers beim Schachspiel versuchen, nacheinander alle Felder des Schachbretts mit genau einem Korn zu besetzen.

– Dabei darf er jedes Feld, außer für Tests, nur höchstens einmal betreten.

Zugmöglichkeiten eines Springers




Aufgabe 34 - Lösungsidee– Der Hamster löst das Springerproblem mit Hilfe des

Backtracking-Verfahrens.

– Dazu hüpft er von seinem Ausgangsfeld zu einem zulässigen Zielfeld. Von dort aus begibt er sich auf ein weiteres bislang noch unberührtes Feld usw.

– Im allgemeinen wird der Hamster nicht direkt eine Lösung des Problems finden, sondern irgendwann auf ein Feld geraten, von dem aus kein weiteres unberührtes Feld mehr angesprungen werden kann, d.h. er ist in eine Sackgasse geraten. In diesem Fall nimmt der Hamster so viele Züge zurück, bis er wieder einen anderen zulässigen Zug machen kann.




Aufgabe 35 - Situation– Der Hamster soll das bekannte Acht-Damenproblem lösen:

– Er soll eine Stellung für 8 Schachdamen auf einem Schachbrett finden, so dass sich keine zwei Damen gegenseitig schlagen können. Die Damen sind also so zu platzieren, dass jede Zeile, jede Spalte, und jede Diagonale des Schachbretts höchstens eine Dame enthält. Die Damen werden dabei jeweils durch ein Korn repräsentiert; der Hamster hat anfangs genau 8 Körner im Maul.

Ingesamt existieren für ein 8x8 Schachbrett 92 Lösungen, eine davon ist die folgende:



Hamster-Modell

• Auswahlanweisungen • Wiederholungsanweisungen • Funktionen • Hamster, die nicht mehr auf einer fest vorgegebenen

Landschaft operieren, sondern auf allen, die bestimmte Voraussetzungen erfüllen

• Vermeidung von Laufzeitfehlern • Hamster mit Gedächtnis (Boolesche Variablen) • Hamster mit Gedächtnis (Zahlen)

• Integer-Funktionen • Verallgemeinerung von Daten und Funktionen

• Prozeduren und Funktionen mit Parametern • Rekursive Funktionen

Documents

Hamster-ProgrammierungSeite 151 Hochschule Harz © Prof. Dr. Bernhard Zimmermann Fachbereich Automatisierung und Informatik Prof. Dr. Sigurd Günther Hamster-Modell