Halden < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:57 Do 15.11.2007 | | Autor: | Dani7 |
| Aufgabe | Wie groß ist die maximale Tiefe einer Halde mit d Nachfolgern mit n Elementen (falls Sie es
benötigen: Die Formel fürr die geometrische Reihe können Sie recherchieren)? |
Eine Halde ist ja so aufgebaut, dass ein Vater immer zwei Söhne hat, dann ist ja wegen der Summenformel der geometrischen Reihe:
Summe [mm] =(2^n)-1
[/mm]
laut Vorlesung ergibt sich aber [mm] (2^n)-1+1, [/mm] und daraus kann man dann die maximale Höhe einer Halde errechnen mit:
[mm] 2^n<=n [/mm] und daraus ergibt sich dann n<= |ld(n)|
obwohl ich jetzt nicht genau weiß, woher die +1 kommt, kann ich das Beispiel noch nachvollziehen.
Wenn man nun aber d Nachfolger anstatt von zweien hat, dann ergibt sich laut geometrischer Reihe ja:
s (n)= [mm] 1*((d^n)-1)/(d-1)
[/mm]
Ich weiß nun nicht ob ich hier auch die +1 dazuzählen muß, wenn ja, dann lautet meine weitere Berechnung:
[mm] (((d^n)-1) [/mm] /(d-1) )+1<=n
aber hier weiß ich nicht mehr weiter, wie kann man oder soll man hier weiterrechnen?
es wäre nett wenn mir jemand antworten würde.
Ich danke euch im voraus.
lg daniela
|
|
| |
|
Hallo,
ich glaube, der Variablenname n wird hier etwas überstrapaziert.
Nennen wir $n$ die Gesamtzahl der Elemente, $d$ die Anzahl der Nachfolger pro Element und $t$ die maximale Tiefe (warum eigentlich maximal, ist sie bei gegebener Anzahl der Nachfolger nicht fest?).
Dann erhalten wir für $d=2$, wie du richtig festgestellt hast:
$n = [mm] 2^t [/mm] - 1$
Das +1 aus der Vorlesung kann ich mir gar nicht erklären.
Dann gilt für die (maximale) Tiefe:
$t = [mm] ld\left(n+1\right)$
[/mm]
Für andere $d$ kann man genauso nach der Summenformel rechnen:
$n = [mm] \bruch{d^t-1}{d-1}$
[/mm]
Hier bekommst du für die Tiefe $t$:
$t = [mm] \log_d\left(n*(d-1)+1\right)$
[/mm]
Gruß
Martin
|
|
|
|
