Programmierkurs Java WS 98/99 Vorlesung 7 Dietrich Boles 02/12/98Seite 1 Programmierkurs Java Vorlesung im WS 1998/1999 am FB Informatik der Universität

Programmierkurs Java WS 98/99 Vorlesung 7 Dietrich Boles 02/12/98 Seite 1

Programmierkurs Java

Vorlesung

im WS 1998/1999

am FB Informatik

der Universität Oldenburg

Vorlesung 7

Dietrich Boles


Gliederung von Vorlesung 7

• Speicherverwaltung– Stack

– „Zeiger“

– Heap

• Inkarnationen– von Funktionen

– von Variablen

• Rekursion– Definitionen

– rekursive Prozeduren

– rekursive Funktionen

– Endlosrekursion

• Backtracking

• Beispielprogramme


Speicherverwaltung

Programmcode

Statische Daten

Stack

Heap

globale Variablen

lokale Variablen

Daten unterProgrammkontrolle

Programm-speicher


Stack

• Verwaltung durch Laufzeitsystem

• Arbeitet nach dem Prinzip „last-in-first-out“

• Verwaltung von Funktionsaktivierungen

• Speicherbereich für lokale Variablen

int a float b

void main():

int a float b

void main():int a char b

void p():p();

int a float b

void main():

return;

Stack Stack Stack


Heap

• Programmkontrollierte Verwaltung

• Speicherzuweisung per Anweisung (new/delete)

• Zugriff über „Zeiger-Variablen“ (Referenz-Variablen)

• Unterstützung durch Laufzeitsystem (Garbage Collection, ...)

Heap

int a

new int (a);

Heap

int a

delete (b);

char b char b


Zeiger

• Gibt es in Java so nicht, aber Grundlage für Objektrepräsentation

• Datentyp ADDRESS

• ADDRESS-Variablen: Speicherung von Speicheradressen

ADDRESS v

double v

Stack oder Heap

Heap

2

234.567

Stack oder Heap

Heap

2

4

0

3

5

1

2

4

0

3

5

1


Zeiger

ADDRESS(double) v, w; // Anlegen zweier ADDRESS- // Variablen auf dem Stack

v = new double(); // Speicherplatzzuweisung (Heap)

w = new double(); // v und w enthalten als Werte

// Speicheradressen

*v = 4711.0; // Zuweisung eines Wertes an die

// Speicheradresse, auf die v zeigt

*w = *v + 34.567; // dito für w (Dereferenzierung)

v = w // v und w zeigen nun auf denselben

// Speicherplatz

delete v; // Speicherplatzfreigabe

delete w;


Inkarnation

Funktionsinkarnationen– beim Aufruf einer Funktion f ensteht eine Inkarnation von f

– zur Inkarnation einer Funktion gehören:• ein Ausführungspunkt

• Speicherplätze für funktionslokale Variablen

– eine Inkarnation wird vernichtet, wenn die Funktion verlassen wird

– Blockanweisungen entsprechen namenlosen Funktionen, entsprechend gilt der Inkarnationsbegriff auch hier

Variableninkarnationen– wird während der Programmausführung die Definitionsanweisung einer

Variablen v erreicht, entsteht eine Inkarnation (Instanz) von v

– die Inkarnation von v wird vernichtet, sobald die Lebensdauer von v beendet ist


Inkarnation

• Aktionen beim Aufruf einer Funktion

– es wird auf dem Stack ein Aktivierungssegment (Speicherstück) angelegt

– der aktuelle Zustand des Programms (Registerinhalte) wird im

Aktivierungssegment gespeichert

– im Aktivierungssegment werden Speicherbereiche für Parameter, lokale

Variable und temporäre Daten reserviert

• Aktionen beim Verlassen einer Funktion

– mit Hilfe der abgespeicherten Registerinhalte kann der Zustand des

Programms von vor dem Funktionsaufruf wiederhergestellt werden

– der Funktionswert wird an geeigneter Stelle abgelegt

– das Aktivierungssegment wird zerstört


Inkarnation

Schema:

main(): f1(): f2(int j):

int i; int i; float x;

f1(); f2(i); // ...

int j; return;

f2(5+j);

Stack

main i main i

f1 imain i

f1 imain i

f1 i jmain i

f1 i j

f2 j x f2 j x


Rekursion

• „Definition eines Problems, einer Funktion oder eines Verfahrens durch sich selbst“

• bereits bekannt:– direkt rekursive Syntaxdiagramme:

– indirekt rekursive Syntaxdiagramme:

– Mathematik:<boolescher Ausdruck> :: „true“ | „false“ |

„(“ <boolscher Ausdruck> „)“ ;

<Anweisung> ::= ... | <while-Anweisung> ;

<while-Anweisung> ::= „while“ „(“ <bA> „)“ <Anweisung> ;

n! = 1 falls n = 0

n * (n-1)! sonst{


Rekursive Prozeduren und Funktionen

Definition (Rekursion):

Eine Funktion heißt rekursiv, wenn mindestens zwei Inkarnationen dieser Funktion zur gleichen Zeit bestehen können.

Definition (direkte Rekursion):

Eine Funktion heißt direkt rekursiv, wenn sich die Funktion selbst aufruft, d.h. wenn die zweite Inkarnation der Funktion durch die Funktion selbst erzeugt wird.

Definition (indirekte Rekursion):

Eine Funktion heißt indirekt rekursiv, wenn die zweite Inkarnation der Funktion nicht durch die Funktion selbst erzeugt wird.

Definition (Rekursionstiefe):

Anzahl der Inkarnationen einer Funktion minus 1


Rekursive Prozeduren

Der Hamster soll bis zur nächsten Wand laufen!

Iterative Lösung:

Direkt rekursive Lösung:

void zurMauer() { while (vorn_frei()) vor();}

void zurMauerR() { if (vorn_frei()) { vor(); zurMauerR(); }}



Der Hamster soll alle Körner auf dem aktuellen Feld einsammeln!

Iterative Lösung:


void sammle() { while (korn_da()) nimm();}

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



Korrelation zwischen iterativen und rekursiven Prozeduren:

void p() { while ( <Bedingung> ) <Anweisung>}

void pR() { if ( <Bedingung> ) { <Anweisung> pR(); }}

void p1() { if ( <Bedingung> ) { <Anweisung> while ( <Bedingung> ) <Anweisung> }}

void p2() { if ( <Bedingung> ) { <Anweisung> if ( <Bedingung> ) { <Anweisung> while ( <Bedingung> ) <Anweisung> } }}



Der Hamster soll bis zur nächsten Wand und dann zurück zur Ausgangsposition laufen!

Iterative Lösung:

void hinUndZurueck() { int anzahl = 0; while (vorn_frei()) { vor(); anzahl++; }

links_um(); links_um();

while (anzahl > 0) { vor(); anzahl--; }}





void hinUndZurueckR() { if (vorn_frei()) { vor(); hinUndZurueckR(); vor(); } else { kehrt(); }}

void kehrt() { links_um(); links_um();}



Schema:

main: hUZR (1.) hUZR (2.) hUZR (3.)

hUZR(); vorn_frei -> t vor(); hUZR(); -----> vorn_frei -> t vor(); hUZR(); -----> vorn_frei -> f kehrt(); <----- vor(); <----- vor(); <-----

Befehlsfolge: vor(); vor(); kehrt(); vor(); vor();




Indirekt rekursive Lösung:

void hinUndZurueckR() { if (vorn_frei()) { laufe(); } else { links_um(); links_um(); }}

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


Rekursive Funktionen

Der Hamster soll die Anzahl an Schritten bis zur nächsten Mauer zählen!

Iterative Lösung:

Rekursive Lösung:

int anzahlSchritteR() { if (vorn_frei()) { vor(); return anzahlSchritteR() + 1; } else return 0;}

int anzahlSchritte() { int anzahl = 0; while (vorn_frei()) { vor(); anzahl++; } return anzahl;}


Rekursive Funktionen

Schema:

main: aSR (1.) aSR (2.) aSR (3.)

i=aSR(); vorn_frei -> t vor(); aSR() -----> vorn_frei -> t vor(); aSR() -----> vorn_frei -> f return 0; 0 <----- return 0 + 1; 1 <----- return 1 + 1; 2 <-----i=2;


Rekursive Funktionen mit lokalen Variablen

Der Hamster soll die Anzahl an Körnern im Maul zählen!

int anzahlKoernerR() { if (!maul_leer()) { gib(); int anz = anzahlKoernerR(); nimm(); // Vermeidung von Seiteneffekten! return anz + 1; } else return 0;}

Stack

aKR

mainmain

anz aKR

main

anz aKR

main

anz

aKR anz aKR anz

aKR anz

...


Rekursive Funktionen mit Parametern

Der Hamster soll „anz“-Schritte nach vorne gehen!

void vorR(int anz) { if ((anz > 0) && vorn_frei()) { vor(); vorR(anz-1); }}

Stack

vorR

mainmain

anz=2 vorR

main

anz=2 vorR

main

anz=2

vorR anz=1 vorR anz=1

vorR anz=0

...


Rekursive Funktionen / Endlosrekursion

Endlosrekursion:

Rekursionstiefe: im Prinzip „unendlich“!

erzeugt im allgemeinen einen Laufzeitfehler: Stack overflow!

Dem Java-Interpreter kann man die gewünschte Stackgröße mitteilen!

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


Rekursive Prozeduren und Funktionen

• Anmerkungen:– zu jedem rekursiv formulierten Algorithmus gibt es einen äquivalenten

iterativen Algorithmus

• Vorteile rekursiver Algorithmen:– kürzere Formulierung

– leichter verständliche Lösung

– Einsparung von Variablen

– teilweise sehr effiziente Problemlösungen (z.B. Quicksort)

• Nachteile rekursiver Algorithmen:– weniger effizientes Laufzeitverhalten (Overhead beim Funktionsaufruf)

– Verständnisprobleme bei Programmiernanfängern

– Konstruktion rekursiver Algorithmen „gewöhnungsbedürftig“


Backtracking-Verfahren

• Prinzip:– Versuch, eine Teillösung eines gegebenen Problems systematisch zu einer

Gesamtlösung auszubauen

– falls in einer gewissen Situation ein weiterer Ausbau einer vorliegenden Teillösung nicht mehr möglich ist („Sackgasse“), werden eine oder mehrere der letzten Teilschritte rückgängig gemacht

– die dann erhaltene reduzierte Teillösung versucht man auf einem anderen Weg wieder auszubauen

– Wiederholung des Verfahrens, bis Lösung gefunden wird oder man erkennt, daß keine Lösung existiert

• Grundlage der Programmiersprache PROLOG!

• Bekannte Probleme:– Springerproblem

– Acht-Damenproblem

– Labyrinthsuche



Aufgabe: Der Hamster steht am Eingang eines zyklenfreien Labyrinths, in dem

er ein Korn finden und auf dem schnellsten Weg zurücktransportieren soll!



boolean gefunden = false;

void main() { sucheGeradeAb(); }

void sucheGeradeAb() {

if (korn_da()) { gefunden = true; nimm(); }

if (!gefunden && links_frei()) {

links_um(); vor(); sucheGeradeAb(); vor(); links_um();

}

if (!gefunden && rechts_frei()) {

rechts_um(); vor(); sucheGeradeAb(); vor(); rechts_um();

}

if (!gefunden && vorn_frei()) {

vor(); sucheGeradeAb(); vor();

} else {

kehrt();

} }


Beispielprogramm 1

Berechnung der Fakultätsfunktion:

public int fakultaet(int n) { if (n <= 0) return 1; else return n * fakultaet(n-1);}

n! = 1 falls n = 0

n * (n-1)! sonst{

fak(3) = 3 * fak(2) 2 * fak(1)

1 * fak(0)

1

1 * 1

2 * 1 3 * 2

6


Beispielprogramm 2

Berechnung einer Fibonacci-Zahl:

public int fib(int n) { if (n <= 2) return 1; else return fib(n-1) + fib(n-2);}

1 falls n = 1

fib(n) = 1 falls n = 2

fib(n-1) + fib(n-2) sonst{


Beispielprogramm 3

McCarthy-Funktion:

es gilt übrigens: mc(n) = 91 für 1 <= n <= 101

public int mc(int n) {

if (n > 100)

return n - 10;

else

return mc(mc(n+11));

}

n-10 falls n > 100

mc(n) = mc(mc(n+11)) sonst{


Beispielprogramm 4

Ackermann-Funktion:

wächst sehr stark:

ack(4,2) besitzt 19729 Stellen

ack(4,4) ist größer als 10 hoch 10 hoch 10 hoch 19000

public int ack(int n, int m) {

if (n == 0) return m+1;

else if (m == 0) return ack(n-1, 1);

else return ack(n-1, ack(n,m-1));

}

m + 1 falls n = 0

ack(n,m) = ack(n-1,1) falls m = 0

ack(n-1,ack(n,m-1)) sonst{


Beispielprogramm 5Türme von Hanoi:

public class Hanoi { public static void main(String[] args) { int hoehe = Terminal.readInt(); verlegeTurm(hoehe, 1, 3, 2); } public static void verlegeTurm(int hoehe, int von, int nach, int ueber) { if (hoehe > 0) { verlegeTurm(hoehe-1, von, ueber, nach); Terminal.out.println(von + “-“ + nach); verlegeTurm(hoehe-1, ueber, nach, von);} } }

Gegeben: 3 Pfosten mit n ScheibenZiel: Lege alle n Scheiben von 1 nach 3Restriktion 1: immer nur eine Scheibe bewegenRestriktion 2: niemals größere auf kleinere Scheibe 1 2 3

Documents

Programmierkurs Java WS 98/99 Vorlesung 7 Dietrich Boles 02/12/98Seite 1 Programmierkurs Java Vorlesung im WS 1998/1999 am FB Informatik der Universität