Aus ProgrammingWiki
Übungsaufgaben
Um sich die einzelnen Verfahren zu verdeutlichen, sind folgende Aufgaben zu lösen.
1. Sortieren Sie die folgende Menge mit Quicksort Schritt für Schritt auf Papier:
Quicksort.pdf (0.1 MB) |
2. Sortieren Sie die folgende Menge mit Mergesort Schritt für Schritt auf Papier:
Mergesort.pdf (0.1 MB) |
3.
a) Suchen Sie mit Hilfe der binären Suche (schriftlich auf Papier) das Element aus folgender sortierter Liste:
Binäre1.pdf (0.2 MB) |
b) Suchen Sie mit Hilfe der sequenziellen Suche (schriftlich auf Papier) das Element aus folgender sortierter Liste:
Seq_Suche.pdf (0.2 MB) |
4. Zu Beginn unserer Vorlesung wiesen wir die Effizienz von Teile-und-Herrsche-Algorithmen mit der Meister-Methode nach. Aufgabe ist es nun, die Effizienz iterativ nachzuweisen. Folgende Aufwandsbeziehungen gelten:
Lösung:
5. Multiplizieren Sie schriftlich und ohne Taschenrechner die Zahlen und nach der Methode von Karatsuba. Als Basis verwenden Sie .
Lösung: