Informatik II - Übung 10

Pascal Schärli

aacchpss@pascscha.ch

27.11.2020

Nachbesprechung

Pascal Schärli 27.11.2020

Pascal Schärli 27.11.2020

Pascal Schärli 27.11.2020

Pascal Schärli 27.11.2020

Vorlesung

Pascal Schärli 27.11.2020

Divide and conquer

  • Komplexe Probleme können auf einfache Teilprobleme reduziert werden
     
  • Diese Teilprobleme kann man weiter unterteilen, bis das Problem simpel genug ist
     
  • Teile und Herrsche
     
  • Heute:
    • Türme von Hanoi
    • Mergesort

Pascal Schärli 27.11.2020

Türme von Hanoi

Turm 1
Turm 2
Turm 3
  • Das Ziel ist es, alle Scheiben von Turm 1 nach Turm 3 zu verschieben.
     
  • Man darf immer nur eine Scheibe auf einmal verschieben
     
  • Es darf nie eine grössere Scheibe auf einer kleineren liegen.

Pascal Schärli 27.11.2020

  1. Wir wollen \(n\) Scheiben von Turm 1 nach Turm 3 verschieben:
     
  2. \(n-1\) Scheiben von Turm 1 nach Turm 2 verschieben
     
  3. Grosse Scheibe von Turm 1 nach Turm 3 verschieben
     
  4. \(n-1\) Scheiben von Turm 2 nach Turm 3 verschieben

\(n = 4\)

Turm 1
Turm 3
Turm 2
[1]
[2]
[3]
[4]

Türme von Hanoi

Pascal Schärli 27.11.2020

\(n = 4\)

Turm 1
Turm 3
Turm 2
[1]
[2]
[3]
[4]
  • Im Zug 2 und 4 verschieben wir mehr als eine Scheibe
     
  • Wir müssen einen Weg finden die \(n - 1\) Scheiben zu verschieben ohne die Regeln zu verletzen
     
  • Wir verwenden unseren divide and conquer Algorithmus für die \(n - 1\) Scheiben

Türme von Hanoi

Pascal Schärli 27.11.2020

  1. Wir wollen \(n-1\) Scheiben von Turm 1 nach Turm 2 verschieben:
     
  2. \(n-2\) Scheiben von Turm 1 nach Turm 3 verschieben
     
  3. Eine Scheibe von Turm 1 nach Turm 2 verschieben
     
  4. \(n-2\) Scheiben von Turm 3 nach Turm 2 verschieben

\(n = 4\)

Turm 1
Turm 3
Turm 2
[1]
[2]
[3]
[4]

Türme von Hanoi

Pascal Schärli 27.11.2020

\(n = 4\)

Turm 1
Turm 3
Turm 2
[1]
[2]
[3]
[4]

Dies können wir in einem Rekursiven Algorithmus festhalten:

hanoi(int n, int von, int nach){
    if(n == 1) movetop(von,nach);
    int other = 6 - von - nach;
    hanoi(n-1,von,other);         // [2]
    movetop(von,nach);            // [3]
    hanoi(n-1,other,nach);        // [4]
}

Türme von Hanoi

Pascal Schärli 27.11.2020

Mergesort

Mergesort ist ein Sortieralgorithmus, welcher ebenfalls durch divide and conquer funktioniert
 

  1. Teile die Liste in zwei halb so grosse Listen auf
  2. Sortiere die halb so grossen Listen
  3. Verbinde die beiden sortierten Listen zu einer einzigen sortierten Liste

3

8

6

5

2

7

4

1

1

2

3

4

5

6

7

8

3

8

6

5

2

7

4

1

3

8

6

5

2

7

4

1

1
2
3

Pascal Schärli 27.11.2020

Mergesort

3

8

6

5

2

7

4

1

1

2

3

4

5

6

7

8

3

8

6

5

2

7

4

1

3

8

6

5

2

7

4

1

1
2
3
  • Im Punkt 2 können wir die kleinen Teillisten wieder mit Mergesort sortieren
     
  • Dies wiederholen wir, bis die Liste nur noch ein Element beinhaltet

Pascal Schärli 27.11.2020

Mergesort

1

2

4

7

ptr1
ptr2

3

8

6

5

1

2

4

7

3

8

6

5

Um zwei Listen zu Mergen kann man:
 

• einen Zeiger auf den Anfang von beiden Teillisten setzen


• Das kleinere Element dem Resultat hinzufügen und diesen Zeiger vergrössern

Pascal Schärli 27.11.2020

Mergesort

1

2

4

7

ptr1
ptr2

3

8

6

5

1

2

4

7

3

8

6

5

Um zwei Listen zu Mergen kann man:
 

• einen Zeiger auf den Anfang von beiden Teillisten setzen


• Das kleinere Element dem Resultat hinzufügen und diesen Zeiger vergrössern

Pascal Schärli 27.11.2020

Mergesort

1

2

4

7

ptr1
ptr2

3

8

6

5

1

2

4

7

3

8

6

5

Um zwei Listen zu Mergen kann man:
 

• einen Zeiger auf den Anfang von beiden Teillisten setzen


• Das kleinere Element dem Resultat hinzufügen und diesen Zeiger vergrössern

Pascal Schärli 27.11.2020

Mergesort

1

2

4

7

ptr1
ptr2

3

8

6

5

1

2

4

7

3

8

6

5

Um zwei Listen zu Mergen kann man:
 

• einen Zeiger auf den Anfang von beiden Teillisten setzen


• Das kleinere Element dem Resultat hinzufügen und diesen Zeiger vergrössern

Pascal Schärli 27.11.2020

Mergesort

1

2

4

7

ptr1
ptr2

3

8

6

5

1

2

4

7

3

8

6

5

Um zwei Listen zu Mergen kann man:
 

• einen Zeiger auf den Anfang von beiden Teillisten setzen


• Das kleinere Element dem Resultat hinzufügen und diesen Zeiger vergrössern

Pascal Schärli 27.11.2020

Mergesort

1

2

4

7

ptr1
ptr2

3

8

6

5

1

2

4

7

3

8

6

5

Um zwei Listen zu Mergen kann man:
 

• einen Zeiger auf den Anfang von beiden Teillisten setzen


• Das kleinere Element dem Resultat hinzufügen und diesen Zeiger vergrössern

Pascal Schärli 27.11.2020

Mergesort

1

2

4

7

ptr1
ptr2

3

8

6

5

1

2

4

7

3

8

6

5

Um zwei Listen zu Mergen kann man:
 

• einen Zeiger auf den Anfang von beiden Teillisten setzen


• Das kleinere Element dem Resultat hinzufügen und diesen Zeiger vergrössern

Pascal Schärli 27.11.2020

Mergesort

1

2

4

7

ptr1
ptr2

3

8

6

5

1

2

4

7

3

8

6

5

Um zwei Listen zu Mergen kann man:
 

• einen Zeiger auf den Anfang von beiden Teillisten setzen


• Das kleinere Element dem Resultat hinzufügen und diesen Zeiger vergrössern

Pascal Schärli 27.11.2020

Mergesort

1

2

4

7

ptr1
ptr2

3

8

6

5

1

2

4

7

3

8

6

5

Um zwei Listen zu Mergen kann man:
 

• einen Zeiger auf den Anfang von beiden Teillisten setzen


• Das kleinere Element dem Resultat hinzufügen und diesen Zeiger vergrössern

Pascal Schärli 27.11.2020

Mergesort

1

2

4

7

ptr1
ptr2

3

8

6

5

1

2

4

7

3

8

6

5

Um zwei Listen zu Mergen kann man:
 

• einen Zeiger auf den Anfang von beiden Teillisten setzen


• Das kleinere Element dem Resultat hinzufügen und diesen Zeiger vergrössern

Pascal Schärli 27.11.2020

Mergesort

3

8

6

5

2

7

4

1

3

8

6

5

2

7

4

1

Pascal Schärli 27.11.2020

Mergesort

3

8

6

5

2

7

4

1

3

8

6

5

2

7

4

1

3

8

6

5

2

7

4

1

Pascal Schärli 27.11.2020

Mergesort

3

8

6

5

2

7

4

1

3

8

6

5

2

7

4

1

3

8

6

5

3

8

6

5

2

7

4

1

Pascal Schärli 27.11.2020

Mergesort

3

8

6

5

2

7

4

1

3

8

6

5

2

7

4

1

3

8

6

5

3

8

3

8

6

5

2

7

4

1

Pascal Schärli 27.11.2020

Mergesort

3

8

6

5

2

7

4

1

3

8

6

5

2

7

4

1

3

8

6

5

3

8

3

8

3

8

6

5

2

7

4

1

Pascal Schärli 27.11.2020

Mergesort

3

8

6

5

2

7

4

1

3

8

6

5

2

7

4

1

3

8

6

5

3

8

3

8

6

5

3

8

6

5

2

7

4

1

Pascal Schärli 27.11.2020

Mergesort

3

8

6

5

2

7

4

1

3

8

6

5

2

7

4

1

3

8

6

5

3

8

3

8

6

5

5

6

3

8

6

5

2

7

4

1

Pascal Schärli 27.11.2020

Mergesort

3

8

6

5

2

7

4

1

3

8

6

5

2

7

4

1

3

8

6

5

3

8

3

8

6

5

5

6

3

5

6

8

3

8

6

5

2

7

4

1

Pascal Schärli 27.11.2020

Mergesort

3

8

6

5

2

7

4

1

3

8

6

5

2

7

4

1

3

8

6

5

3

8

3

8

6

5

5

6

3

5

6

8