Trace:
Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revisionLast revisionBoth sides next revision | ||
repds15:hausaufgaben_loes [2015/09/26 10:47] – [Rekursive Programmierung] 95.222.28.8 | repds15:hausaufgaben_loes [2015/10/04 16:24] – mario | ||
---|---|---|---|
Line 72: | Line 72: | ||
- Gib eine rekursive Implementierung von '' | - Gib eine rekursive Implementierung von '' | ||
+ | < | ||
+ | lookupRek(int priority, int wo) | ||
+ | { | ||
+ | if(wo <= n) | ||
+ | { | ||
+ | if (H[wo] == priority ) | ||
+ | print priority | ||
+ | else if (H[wo] > priority ) | ||
+ | lookupRek( priority, 2*wo); | ||
+ | if (H[wo+1] == priority ) | ||
+ | print priority | ||
+ | else if (H[wo+1] > priority ) | ||
+ | lookupRek( priority, 2*wo+1); | ||
+ | } | ||
+ | } | ||
+ | </ | ||
- Erweiterung von Übungsblatt 3, Aufgabe 2 (Spielbäume): | - Erweiterung von Übungsblatt 3, Aufgabe 2 (Spielbäume): | ||
+ | '' | ||
+ | **Antwort**: | ||
+ | |||
- Erweitere die '' | - Erweitere die '' | ||
Line 78: | Line 97: | ||
- Eine Schwarz-Weiß-Pixelgrafik mit Länge n und Breite n soll abgespeichert werden. Jedes einzelne Pixel soll in konstanter Laufzeit O(1) auf schwarz bzw. weiß gesetzt werden. Wie viel Speicherplatz benötigen wir in Abhängigkeit von n? Du kannst davon ausgehen, dass die Datenstruktur bereits initialisiert vorliegt. | - Eine Schwarz-Weiß-Pixelgrafik mit Länge n und Breite n soll abgespeichert werden. Jedes einzelne Pixel soll in konstanter Laufzeit O(1) auf schwarz bzw. weiß gesetzt werden. Wie viel Speicherplatz benötigen wir in Abhängigkeit von n? Du kannst davon ausgehen, dass die Datenstruktur bereits initialisiert vorliegt. | ||
- Wir überlegen uns eine einfache Komprimierungsmöglichkeit: | - Wir überlegen uns eine einfache Komprimierungsmöglichkeit: | ||
+ | |||
+ | '' | ||
+ | |||
+ | '' | ||
===== Tag 1 ===== | ===== Tag 1 ===== | ||
==== Mathematische Grundlagen, Asymptotik, Landau-Notation ==== | ==== Mathematische Grundlagen, Asymptotik, Landau-Notation ==== | ||
Line 382: | Line 405: | ||
* Entwerfe eine Datenstruktur für einen ternären Baum. Wieso sind Eltern-Arrays nicht geeignet? | * Entwerfe eine Datenstruktur für einen ternären Baum. Wieso sind Eltern-Arrays nicht geeignet? | ||
+ | |||
+ | < | ||
+ | struct Knoten | ||
+ | { schluesseltyp schluessel; | ||
+ | | ||
+ | | ||
+ | ... }; | ||
+ | </ | ||
+ | |||
+ | Eltern-Arrays: | ||
+ | die Ermitllung des kompletten Pfades von der Wurzel aus O(1). | ||
+ | |||
* Gib eine rekursive Definition für Bäume an: Wie sieht ein Baum im Basisfall (Rekursionsanfang) aus? Wie sieht der Rekursionsfall (Rekursionsschritt) aus? | * Gib eine rekursive Definition für Bäume an: Wie sieht ein Baum im Basisfall (Rekursionsanfang) aus? Wie sieht der Rekursionsfall (Rekursionsschritt) aus? | ||
Basisfall: Der Baum ist ein Blatt | Basisfall: Der Baum ist ein Blatt | ||
Line 496: | Line 531: | ||
* Was ist eine Kollision? | * Was ist eine Kollision? | ||
* Welche Laufzeit haben '' | * Welche Laufzeit haben '' | ||
+ | |||
+ | **Insert** | ||
+ | |||
+ | ^ case: | best | average | worst | | ||
+ | ^ mit Verkettung | ||
+ | ^ lineare Adressierung | O(1) | O(1)+$\lambda$ | ||
+ | ^ doppeltes Hashing | ||
+ | |||
+ | **Remove** | ||
+ | |||
+ | ^ case: | best | average | worst | | ||
+ | ^ mit Verkettung | ||
+ | ^ lineare Adressierung | O(1) | O(1)+$\lambda$ | ||
+ | ^ doppeltes Hashing | ||
+ | |||
+ | **Lookup** | ||
+ | |||
+ | ^ case: | best | average | worst | | ||
+ | ^ mit Verkettung | ||
+ | ^ lineare Adressierung | O(1) | O(1) | O(1) | | ||
+ | ^ doppeltes Hashing | ||
+ | |||
* Berechne $3x \mod 5$ für alle $x \in \{0, 1, 4, 5, 10, 12\}$. | * Berechne $3x \mod 5$ für alle $x \in \{0, 1, 4, 5, 10, 12\}$. | ||
* Fülle eine Wertetabelle für $f(x) := 3x \mod 11$ | * Fülle eine Wertetabelle für $f(x) := 3x \mod 11$ | ||
Line 555: | Line 612: | ||
else | else | ||
if (v.links == NULL und v.rechts == NULL) | if (v.links == NULL und v.rechts == NULL) | ||
- | laufffähiger Code in C++ | ||
// Basisfall: v ist ein Blatt | // Basisfall: v ist ein Blatt | ||
return 1 | return 1 | ||
Line 648: | Line 704: | ||
} | } | ||
</ | </ | ||
+ | |||
+ | Der Code berücksichtigt nicht den Fall, daß es mehrere vollständige Teilbäume mit gleicher Knotenzahl geben kann. Hier wäre sinngemäß in der Rahmenprozedur zu ergänzen: | ||
+ | < | ||
+ | printMaxTree(Knoten) | ||
+ | if (Knoten == NULL) return | ||
+ | if (Knoten-> | ||
+ | else | ||
+ | if (zaehler = maximum) | ||
+ | printTree(Knoten) | ||
+ | else | ||
+ | printMaxTree(Knoten) | ||
+ | </ | ||
+ | |||
+ | |||
==== Datenstrukturen entwerfen ==== | ==== Datenstrukturen entwerfen ==== | ||
- Entwirf eine Wörterbuch-Datenstruktur, | - Entwirf eine Wörterbuch-Datenstruktur, |