DokuWiki - fricklers.org

Trace:

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
Last revisionBoth sides next revision
repds15:hausaufgaben_loes [2015/09/26 17:48] – [Datenstrukturen entwerfen] 95.222.28.112repds15:hausaufgaben_loes [2015/10/04 16:24] – mario
Line 75: Line 75:
 lookupRek(int priority, int wo) lookupRek(int priority, int wo)
 { {
- if(2*wo <= n)+ if(wo <= n)
  {  {
- if (H[2*wo] == priority )+ if (H[wo] == priority )
  print priority  print priority
- else if (H[2*wo] >  priority )+ else if (H[wo] >  priority )
  lookupRek( priority, 2*wo);  lookupRek( priority, 2*wo);
- if (H[2*wo+1] == priority )+ if (H[wo+1] == priority )
  print priority  print priority
- else if (H[2*wo+1] > priority )+ else if (H[wo+1] > priority )
  lookupRek( priority, 2*wo+1);  lookupRek( priority, 2*wo+1);
  }  }
Line 90: Line 90:
   - Erweiterung von Übungsblatt 3, Aufgabe 2 (Spielbäume): Statt einem Feld ''Gewinner g'' speichert ein Knoten nun eine Zahl ''int gewinn''. Es gilt: ''gewinn'' > 0, wenn Alice gewinnt und ''gewinn'' < 0, wenn Bob gewinnt. Anfänglich sind nur die Blätter mit den ''gewinn''-Werten markiert. Für alle inneren Knoten ist ''gewinn = 0''. Wer gewinnt das Spiel und wie hoch ist der Gewinn, wenn jeder Spieler nach einem betragsmäßig großen Gewinn strebt?   - Erweiterung von Übungsblatt 3, Aufgabe 2 (Spielbäume): Statt einem Feld ''Gewinner g'' speichert ein Knoten nun eine Zahl ''int gewinn''. Es gilt: ''gewinn'' > 0, wenn Alice gewinnt und ''gewinn'' < 0, wenn Bob gewinnt. Anfänglich sind nur die Blätter mit den ''gewinn''-Werten markiert. Für alle inneren Knoten ist ''gewinn = 0''. Wer gewinnt das Spiel und wie hoch ist der Gewinn, wenn jeder Spieler nach einem betragsmäßig großen Gewinn strebt?
 '' Der MinMax-Algorithmus bleibt erhalten. Nur Details der Implementierung (Datentyp für gewinn) ändern sich. Was ist daran interessant?'' '' Der MinMax-Algorithmus bleibt erhalten. Nur Details der Implementierung (Datentyp für gewinn) ändern sich. Was ist daran interessant?''
 +**Antwort**: Der Name "MinMax-Algorithmus" stammt eigentlich aus diesem Modell. Die Frage, ob eine Gewinnstrategie existiert, ist nur ein Spezialfall. Interessant ist, dass man über die Gewinnfunktion für jeden Spieler den lokal optimalen Zug bestimmen kann und letztlich für denjenigen mit der Gewinnstrategie auch exakt angeben kann, welchen Zug er spielen soll, um möglichst hoch zu gewinnen.
  
   - Erweitere die ''lookup(x)''-Funktion eines binären Suchbaums, sodass sie den Pfad von der Wurzel zum Schlüssel zurück gibt, sofern er existiert.   - Erweitere die ''lookup(x)''-Funktion eines binären Suchbaums, sodass sie den Pfad von der Wurzel zum Schlüssel zurück gibt, sofern er existiert.
Line 611: 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 704: Line 704:
 } }
 </code> </code>
 +
 +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:
 +<code>
 +printMaxTree(Knoten)
 + if (Knoten == NULL) return
 + if (Knoten->links == NULL ) || (Knoten->rechts == NULL) return
 + else
 + if (zaehler = maximum)
 + printTree(Knoten)
 + else
 + printMaxTree(Knoten)
 +</code>
 +
 +
 ==== Datenstrukturen entwerfen ==== ==== Datenstrukturen entwerfen ====
   - Entwirf eine Wörterbuch-Datenstruktur, die für die gegebene Menge M := {0, 1,..., n-1} folgende Laufzeiten ermöglicht:   - Entwirf eine Wörterbuch-Datenstruktur, die für die gegebene Menge M := {0, 1,..., n-1} folgende Laufzeiten ermöglicht: