42
Rekursion Rekursion Klaus Becker (2002)

Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

Embed Size (px)

Citation preview

Page 1: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

RekursionRekursion

Klaus Becker(2002)

Page 2: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

2

KB

Reku

rsio

nTeil 1Teil 1

Rekursive Algorithmen

Page 3: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

3

KB

Reku

rsio

nTürme von HanoiTürme von Hanoi

1883 hatte der französische Mathematiker Edouard Lucas jene kleine Geschichte ersonnen, die fortan als die Geschichte der Türme von Hanoi selbst Geschichte machte:Im Großen Tempel von Benares, unter dem Dom, der die Mitte der Welt markiert, ruht eine Messingplatte, in der drei Diamantnadeln befestigt sind, jede eine Elle hoch und so stark wie der Körper einer Biene. Bei der Erschaffung der Welt hat Gott vierundsechzig Scheiben aus purem Gold auf eine der Nadeln gesteckt, wobei die größte Scheibe auf der Messingplatte ruht, und die übrigen, immer kleiner werdend, eine auf der anderen. Das ist der Turm von Brahma. Tag und Nacht sind die Priester unablässig damit beschäftigt, den festgeschriebenen und unveränderlichen Gesetzen von Brahma folgend, die Scheiben von einer Diamantnadel auf eine andere zu setzen, wobei der oberste Priester nur jeweils eine Scheibe auf einmal umsetzen darf, und zwar so, dass sich nie eine kleinere Scheibe unter einer größeren befindet. Sobald dereinst alle vierundsechzig Scheiben von der Nadel, auf die Gott sie bei der Erschaffung der Welt gesetzt hat, auf eine der anderen Nadeln gebracht sein werden, werden der Turm samt dem Tempel und allen Brahmanen zu Staub zerfallen, und die Welt wird mit einem Donnerschlag untergehen.

Page 4: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

4

KB

Reku

rsio

nTürme von HanoiTürme von Hanoi

Aufgabe:

Versuchen Sie, 4 (einfach) bzw. 5 oder 6 (schwieriger) Scheiben von Platz A nach Platz C nach den Regeln der Priester von Benares zu bringen. Benutzen Sie das Simulationsprogramm „Hanoi“.

Wenn Sie es geschafft haben, überlegen Sie sich, wie lang es dauert, einen Turm aus 64 Scheiben umzubauen, wenn man 1 Sekunde benötigt, um eine Scheibe zu bewegen.

A B C

Page 5: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

5

KB

Reku

rsio

nProblembeschreibungProblembeschreibung

Bringe n-Stapel von A über B nach C

A B C

A B C

AZ:

ZZ:

Page 6: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

6

KB

Reku

rsio

nLösungsideeLösungsidee

A B C

AZ:

ZZ:

A B C

A B C

A B C

...

...

Page 7: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

7

KB

Reku

rsio

nStruktur der LösungsideeStruktur der Lösungsidee

A B CBringe (n-1)-Stapel von A über C nach B

A B C

A B C

A B C

Bringe Scheibe von A nach C

Bringe (n-1)-Stapel von B über A nach C

Page 8: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

8

KB

Reku

rsio

nRekursive ProblemreduktionRekursive Problemreduktion

Bringe (n-1)-Stapel von A über C nach BBringe Scheibe von A nach C

Bringe (n-1)-Stapel von B über A nach C

Bringe n-Stapel von A über B nach CProblem:

Lösung:

Beachte:

Die Lösung reduziert das Problem auf ein strukturgleiches Problem in verkleinerter Form (rekursive Problemreduktion).

Page 9: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

9

KB

Reku

rsio

nRekursiver AlgorithmusRekursiver Algorithmus

Bringe (n-1)-Stapel von X über Z nach YBringe Scheibe von X nach Z

Bringe (n-1)-Stapel von Y über X nach Z

Bringe n-Stapel von X über Y nach Z

Algorithmus

wenn n> 1 dann

Beachte:

Der Algorithmus ruft sich selbst auf, er ist infolgedessen rekursiv.

sonst

Bringe Scheibe von X nach Z

Page 10: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

10

KB

Reku

rsio

nRekursiver AlgorithmusRekursiver Algorithmus

Hanoi(n-1, X,Z,Y)

Bringe Scheibe von X nach Z

Hanoi(n-1, Y, X, Z)

Hanoi(n: integer; X, ,Y, Z: char)Algorithmus

wenn n> 1 dann

Beachte:

Der Algorithmus ruft sich selbst auf, er ist infolgedessen rekursiv.

sonst

Bringe Scheibe von X nach Z

Page 11: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

11

KB

Reku

rsio

nAbarbeitung rekursiver AlgorithmenAbarbeitung rekursiver Algorithmen

ALG. Hanoi(n: integer; X, ,Y, Z: char)

WENN n> 1 DANN

Hanoi(n-1, X,Z,Y)

Bringe Scheibe von X nach Z

Hanoi(n-1, Y, X, Z)

SONST

Bringe Scheibe von X nach Z

Hanoi(3, A, B, C)

Hanoi(2, A, C, B)

Hanoi(1, A, B, C)

Bringe Scheibe von A nach C

Bringe Scheibe von A nach B

Hanoi(1, C, A, B)

Bringe Scheibe von C nach B

Bringe Scheibe von A nach C

Hanoi(2, B, A, C)

Hanoi(1, B, C, A)

Bringe Scheibe von B nach A

Bringe Scheibe von B nach C

Hanoi(1, A, B, C)

Bringe Scheibe von A nach C

Wiederholte Ausführung des Algorithmus, bis die Abbruchbedingung erfüllt ist.

Page 12: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

12

KB

Reku

rsio

nÜbungÜbung

Sie sollen einen Turm mit 4 Scheiben umschichten. Gehen Sie dabei nach dem entwickelten rekursiven Algorithmus vor. Notieren Sie sich zunächst sämtliche Scheibenbewegungen. Testen Sie sie anschließend mit dem Simulationsprogramm.

ALG. Hanoi(n: integer; X, ,Y, Z: char)

WENN n> 1 DANN

Hanoi(n-1, X,Z,Y)

Bringe Scheibe von X nach Z

Hanoi(n-1, Y, X, Z)

SONST

Bringe Scheibe von X nach Z

Page 13: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

13

KB

Reku

rsio

nZusammenfassungZusammenfassung

Wird vom System übernommen.

Entwurf: Ausführung:Muss vom Entwickler geleistet werden.

Entwurfsstrategie:

Reduziere das Problem auf ein strukturgleiches Problem in „verkleinerter Form“, sofern das Problem nicht direkt lösbar ist.

ALG. Hanoi(n: integer; X, ,Y, Z: char)

WENN n> 1 DANN

Hanoi(n-1, X,Z,Y)

Bringe Scheibe von X nach Z

Hanoi(n-1, Y, X, Z)

SONST

Bringe Scheibe von X nach Z

Hanoi(3, A, B, C)

Hanoi(2, A, C, B)

Hanoi(1, A, B, C)

Bringe Scheibe von A nach C

Bringe Scheibe von A nach B

Hanoi(1, C, A, B)

Bringe Scheibe von C nach B

Bringe Scheibe von A nach C

Hanoi(2, B, A, C)

Hanoi(1, B, C, A)

Bringe Scheibe von B nach A

Bringe Scheibe von B nach C

Hanoi(1, A, B, C)

Bringe Scheibe von A nach C

Page 14: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

14

KB

Reku

rsio

nQuicksortQuicksort

27

Zahlen: 13

80

82

6 44anfan

g

26

15

16

39

90

53ende

6Zahlen: 13

15

16

26

27anfan

g

39

44

53

80

82

90ende

Quicksort(anfang, ende)

ZZ:

AZ:

Eine Reihung von Zahlen / ... soll der Größe nach sortiert werden.

Page 15: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

15

KB

Reku

rsio

nQuicksortQuicksort

27

Zahlen: 13

80

82

6 44anfan

g

26

15

16

39

90

53ende

ALGORITHMUS Quicksort(anfang, ende: tIndex)

27

Zahlen: 13

39

16

6 15anfan

g

26

44

82

80

90

53ende

zerlege(links, rechts)

links rechtsp

rechts links

6Zahlen: 13

15

16

26

27anfan

g

39

44

82

80

90

53ende

WENN anfang < rechts Quicksort(anfang, rechts)

rechts links

6Zahlen: 13

15

16

26

27anfan

g

39

44

53

80

82

90ende

WENN links < ende Quicksort(links, ende)

rechts links

links := anfang; rechts := ende;

Page 16: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

16

KB

Reku

rsio

nQuicksortQuicksort

ALGORITHMUS Quicksort(anfang, ende: tIndex)

zerlege(links, rechts);

WENN anfang < rechts Quicksort(anfang, rechts);

WENN links < ende Quicksort(links, ende);

links := anfang; rechts := ende; Vorbereitung

Rekursive Reduktions

-schritte

Abbruch-bedingung

Bemerkung:

Kurzer Algorithmus, der einen komplexen Ablauf festlegt.

Entwurfsstrategie:

Reduziere das Problem auf ein strukturgleiches Problem in „verkleinerter Form“, sofern das Problem nicht direkt lösbar ist.

Page 17: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

17

KB

Reku

rsio

nTeil 2Teil 2

Turtle-Grafik

Page 18: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

18

KB

Reku

rsio

nTurtle-GrafikTurtle-Grafik

Die Turtle lebt auf einer Zeichenfläche.

Die Turtle kann sich bewegen, drehen und – zum Zeichnen – eine Spur hinterlassen.

Zeichen-fläche

Turtlespur

Turtle

Page 19: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

19

KB

Reku

rsio

nTurtle-GrafikTurtle-Grafik

Die Turtle agiert auf Befehle / führt Anweisungen aus.

Draw(100)

Page 20: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

20

KB

Reku

rsio

nTurtle-GrafikTurtle-Grafik

Die Turtle kann „neue Befehle“ lernen. Diese werden in Turtle-Programmen festgelegt.

Quadrat

procedure Quadrat;beginwith Turtle do begin Draw(100); Turn(90); Draw(100); Turn(90); Draw(100); Turn(90); Draw(100); Turn(90);end;end;

Page 21: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

21

KB

Reku

rsio

nDie Turtle als ObjektDie Turtle als Objekt

Turtle

TTurtleAttribute

XPos : double // x-Position

YPos : double // y-Position

Angle : double // Richtung

Color : TColor // Zeichenfarbe

...Ereignisse

...Methoden

...

(0|0) (688|0)

(0|452) (688|452)

Die Turtle wird als ein Objekt der Klasse TTurtle erzeugt.

Sie besitzt infolgedessen charakteristische Eigenschaften ( Attribute) und kann charakteristische Operationen ausführen ( Methoden).

Page 22: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

22

KB

Reku

rsio

nDie Turtle als ObjektDie Turtle als Objekt

TTurtleAttribute

...Ereignisse

...Methoden

Init // Die Turtle wird in die Mitte der Zeichenfläche mit Blickrichtung nach rechts gesetzt.

Draw(d: double) // Die Turtle zeichnet in der aktuell. Blickrichtung eine Strecke der Länge d.

DrawTo(x,y: double) // Die Turtle zeichnet eine Strecke zum Punkt (x|y).

Turn(a: double) // Die Turtle dreht sich um den Winkel a (a > 0: Linksdr.; a < 0: Rechtsdr.).

TurnTo(a: double) // Die Turtle setzt ihre Blickricht. nach a (a = 0: rechts; a = 90: oben; ...).

Move(d: double) // Die Turtle bewegt sich – ohne zu zeichnen – um d in Blickrichtung.

MoveTo(x,y: double) // Die Turtle bewegt sich – ohne zu zeichnen – zum Punkt (x|y).

Clear // Die Zeichenfläche der Turtle wird gelöscht.

...

Page 23: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

23

KB

Reku

rsio

nZeichnen mit der TurtleZeichnen mit der Turtle

procedure Quadrat(x: real);

var i: integer;

beginfor i := 1 to 4 do begin Turtle.Draw(x); Turtle.Turn(90); end;end;

AZ:

ZZ:

Al: Quadrat(200);

Page 24: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

24

KB

Reku

rsio

nZeichnen mit der TurtleZeichnen mit der Turtle

procedure Quadrat(x: real);

var i: integer;

beginwith Turtle do begin for i := 1 to 4 do begin Draw(x); Turn(90); end; end;end;

AZ:

ZZ:

Al: Quadrat(200);

Quadrat

Page 25: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

25

KB

Reku

rsio

nÜbungenÜbungen

Entwickeln Sie ein Turtle-Programm, mit dem man einen (primitiven) Tannenbaum zeichnen kann.

Gehen Sie wie folgt vor:

Überlegen Sie sich zunächst, aus welchen Bestandteilen der Tannenbaum besteht.

Formulieren Sie anschließend die Algorithmen für die Bestandteile.

Implementieren und testen Sie die Algorithmen abschließend mit Hilfe der Turtle-Komponente.

Page 26: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

26

KB

Reku

rsio

nÜbungenÜbungen

Entwickeln Sie ein Turtle-Programm, mit dem man einen Quadratturm (beliebiger) Höhe zeichnen kann.

Formulieren Sie zunächst die benutzten Algorithmen.

Implementieren und testen Sie die Algorithmen abschließend mit Hilfe der Turtle-Komponente.

Page 27: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

27

KB

Reku

rsio

nTeil 3Teil 3

Selbstähnliche Figuren

Page 28: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

28

KB

Reku

rsio

nSelbstähnlichkeitSelbstähnlichkeit

Page 29: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

29

KB

Reku

rsio

nSelbstähnlichkeitSelbstähnlichkeit

Eine Figur ist selbstähnlich, wenn sie sich in Teile zerlegen lässt, die zur ihr ähnlich sind.

Page 30: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

30

KB

Reku

rsio

nRekursive ProblemreduktionRekursive Problemreduktion

Baum(200)

Turtle.Draw(200);

Turtle.Turn(45);

Baum(100);

Turtle.Turn(-90);

Baum(100);

Turtle.Turn(45);

Turtle.Move(-200);

Baum(200)

Baum(100)Baum(100)

Rekursive Problemreduktion:

Draw(200)

Baum(x) // falls x < 2

// keine Operationen

Trivialer Fall:

Page 31: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

31

KB

Reku

rsio

nRekursiver AlgorithmusRekursiver Algorithmus

Algorithmus Baum(Stamm: real)

WENN Stamm >= 2 DANN

Turtle.Draw(Stamm);

Turtle.Turn(45);

Baum(Stamm/2);

Turtle.Turn(-90);

Baum(Stamm/2);

TurtleTurn(45);

Turtle.Move(-Stamm);

Page 32: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

32

KB

Reku

rsio

nÜbungenÜbungen

Suchen Sie sich auf den folgenden Seiten eine selbstähnliche Figur aus und entwickeln Sie für diese ein Turtle-Zeichenprogramm.

Gehen Sie wie folgt vor:

Machen Sie sich (exemplarisch) einen rekursiven Problemreduktionsschritt klar.

Überlegen Sie sich, was im trivialen Fall erfolgen soll (nichts / ...).

Formulieren Sie einen rekursiven Algorithmus und implementieren ihn mit Hilfe der Turtle-Komponente.

Page 33: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

33

KB

Reku

rsio

nSchachtelhalmSchachtelhalm

Page 34: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

34

KB

Reku

rsio

nBuschBusch

Page 35: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

35

KB

Reku

rsio

nTeufelsgabelTeufelsgabel

Page 36: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

36

KB

Reku

rsio

nTreppe ins NirgendwoTreppe ins Nirgendwo

Page 37: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

37

KB

Reku

rsio

nQuadratpflanzeQuadratpflanze

Page 38: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

38

KB

Reku

rsio

nSierpinski-DreieckSierpinski-Dreieck

Page 39: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

39

KB

Reku

rsio

nPythagoras-BaumPythagoras-Baum

Page 40: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

40

KB

Reku

rsio

nFarnFarn

Page 41: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

41

KB

Reku

rsio

nKoch-KurveKoch-Kurve

Page 42: Rekursion Klaus Becker (2002). KB Rekursion 2 Teil 1 Rekursive Algorithmen

42

KB

Reku

rsio

nVariationen der Koch-KurveVariationen der Koch-Kurve