Übung 4

Übung
Algorithmen & Datenstrukturen
SS 2016
Kim Völlinger
1
Vorbereitung heute…
…zum 3. Übungsblatt
• Skip-Listen
• Listen
• Dynamische Programmierung
• Suchen
2
Vorbereitung heute…
…zum 3. Übungsblatt
• Skip-Listen
• Listen
• Dynamische Programmierung
• Suchen
3
Doppelt verkettete sortierte Liste
4
Knoten: ListNode
prev
next
value
public class ListNode {
// Der Wert des Knoten
public int value;
// Zeiger auf den Nachfolger
// und den Vorgänger
public ListNode next;
public ListNode prev;
ListNode
}
5
Doppelt verkettete sortierte Liste: SortedList
−∞
∞
FIRST
LAST
ListNode
ListNode
• Die leere Liste enthält
den Start- und
Endknoten.
SortedList
6
Skip-Liste: SkipList
FIRST
LAST
−∞
∞
SortedList
−∞
FIRST
20
SortedList
∞
LAST
• Jede Ebene
repräsentiert eine
sortierte doppelt
verkettete Liste.
• Kommt ein Knoten
auf einer oberen
Ebene vor, so kommt
er auch auf allen
darunter liegenden
Ebenen vor.
• Alle Knoten kommen
auf der untersten
Ebene vor.
7
Knoten: ListNode
up
prev
next
public class ListNode {
// Der Wert des Knoten
public int value;
value
// Zeiger auf den Nachfolger
// und den Vorgänger
public ListNode next;
public ListNode prev;
down
ListNode
// Zeiger auf die obere
// und untere Ebene
public ListNode up;
public ListNode down;
}
8
Skip-Listen: Suchen
9
Skip-Listen: Einfügen
10
Vorbereitung heute…
…zum 3. Übungsblatt
• Skip-Listen
• Listen
• Dynamische Programmierung
• Suchen
11
Existiert ein Kreis?
Gegeben sei eine einfach verkettete Liste.
Gibt es einen Kreis?
12
Vorbereitung heute…
…zum 3. Übungsblatt
• Skip-Listen
• Listen
• Dynamische Programmierung
• Suchen
13
Dynamische Programmierung
Problem hat optimale Substruktur.
Teilprobleme überlappen.
Teillösungen merken und wiederverwenden.
zerlegen
Problem
rechnen
zusammenführen
Teilproblem
Teillösung
…
…
Teilproblem
Teillösung
Teilproblem
Teillösung
Beispiel:
Fibonacci-Zahlen
Lösung
14
Vorbereitung heute…
…zum 3. Übungsblatt
• Skip-Listen
• Listen
• Dynamische Programmierung
• Suchen
15
Suche
• Redakteur einer Handy-Zeitschrift testet neues Smartphone auf
Bruchtauglichkeit
• Er hat 𝑘 Smartphones und eine Leiter mit 𝑛 Sprossen
• In jedem Versuch steigt er auf eine Sprosse und lässt ein Smartphone
fallen.
• Entweder das Smartphone bleibt unbeschadet oder es bricht auseinander.
Er möchte die höchste Sprosse ermitteln, bei der das Smartphone nicht
bricht und dabei außerdem die Anzahl der Versuche minimieren.
Gib einen Algorithmus an, der die Anzahl der Testversuche im Worst-Case
minimiert und höchstens 𝑘 Smartphones verwendet:
a) 𝑘 = 1
b) 𝑘 = ∞
c) 𝑘 = 2
16

Download Report