Problem Kombinatorik? Anzahl Ebenen in Baumdiagramm Knoten n

O'rallY · Beiträge: 563

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?

markieren

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!
user defined image

_________________
.oO'rallY
Linux is like a tipi: No gates, no windows and a gnu-eating apache inside...

CenBells · Beiträge: 1547 Win 7 Delphi XE5 Pro

hallo,

du kannst eine schleife programmieren
so ähnlich wie folgendes

markieren

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 · Beiträge: 563

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:

markieren

Quelltext

1:	n := trunc(log2(knot_count)) + 1;

Trotzdem Danke!

_________________
.oO'rallY
Linux is like a tipi: No gates, no windows and a gnu-eating apache inside...

CenBells · Beiträge: 1547 Win 7 Delphi XE5 Pro

jop, damit geht es natürlich schneller *g*

Gruß Ken

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme