O'rallY - So 13.04.03 10:44
Titel: Problem Kombinatorik? Anzahl Ebenen in Baumdiagramm Knoten n
Gegeben ist ein Baumdiagramm, wobei jeder Knoten zwei Unterknoten besitz. Außerdem gegeben ist Anzahl der Knoten. Jede Ebende besitz 2^L Knoten, wobei erste Ebene L = 0 ist.
Wie finde ich heraus, wieviele Ebenen gegeben sein müssen, bei der Anzahl der Knoten n?
Bin ich mit dieser Formel überhaupt auf dem richtigen weg?
Quelltext
1:
2:
3:
4:
| n: Anzahl Knoten
L+1: Anzahl Ebenen
n = 2^L |
(Das ganze soll auch funktionieren, wenn der Baum nicht vollständig gefüllt ist, doch gehen wir erstmal davon aus, dass er es ist.)
Bitte einfach den ungefüllten Bereich erstmal übersehen und davon ausgehen, dass der Baum vollständig ist!
CenBells - So 13.04.03 12:20
hallo,
du kannst eine schleife programmieren
so ähnlich wie folgendes
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
| function wievieleEbenen(VorhandeneKnoten: Integer): Integer;
var
LZaehler: Integer;
LExp: Integer;
begin
LExp := 0;
LZaehler := power(2, LExp);
repeat
inc(LExp);
inc(LZaehler, trunc(power(2, LExp)));
until LZaehler >= VorhandeneKnoten;
result := LZaehler;
end; |
dass müsste sogar funktionieren, wenn der baum nicht vollständig gefüllt ist.
Gruß
Ken
O'rallY - So 13.04.03 13:43
Jo, das hab ich mir auch schon überlegt gehabt, war aber nicht besonders glücklich. Deswegen hab ich das Netz ein wenig durchforstet und meine Schwester genervt bis ich schließlich diese Formel hatte:
Quelltext
1:
| n := trunc(log2(knot_count)) + 1; |
Trotzdem Danke!