Informatik II - Übung 10
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
- Wir wollen \(n\) Scheiben von Turm 1 nach Turm 3 verschieben:
- \(n-1\) Scheiben von Turm 1 nach Turm 2 verschieben
- Grosse Scheibe von Turm 1 nach Turm 3 verschieben
- \(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
- Wir wollen \(n-1\) Scheiben von Turm 1 nach Turm 2 verschieben:
- \(n-2\) Scheiben von Turm 1 nach Turm 3 verschieben
- Eine Scheibe von Turm 1 nach Turm 2 verschieben
- \(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
- Teile die Liste in zwei halb so grosse Listen auf
- Sortiere die halb so grossen Listen
- 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