Hallo,
eine scheinbar einfache Aufgabe, die aber doch zwickt: es soll eine baumartige Struktur von Zweigen bis zum Stamm in der korrekten Reihenfolge abgearbeitet werden. Die Grundregel lautet: bevor ein Ast berechnet wird, müssen alle Zweige, die zu diesem Ast führen berechnet werden. Der "Stamm" bleibt also immer über und muss zuletzt berechnet werden. Davor all jene Äste, die zum Stamm führen. Davor jene, die zu diesen Ästen führen.
Alle Zweige/Äste/Stämme haben eine fortlaufende Nummer, die in keinem Zusammenhang mit der Struktur stehen. Jeder Zweig kennt aber die Nummer jenes Zweiges, auf den er trifft. Dazu noch eine Positionsangabe, um zwei Zweige, die nacheinander auf einen Ast treffen, zu unterscheiden.
Gesucht ist die Reihenfolge, in der die Zweige abgearbeitet werden sollen. Um das zu veranschaulichen, ein paar Beispiele anbei. Streng genommen ist im letzten Beispiel die Reihenfolge von 7 und 1 egal. 7 muss vor 6 berechnet werden und 1 vor 2. Ob aber 7 zuerst oder 1 zuerst, macht keinen Unterschied.
Als Startidee muss man wohl alle Zweige durchgehen und den Stamm finden. Jenen Zweig also, der keinen weiteren Zweig als Ziel hat. Dann muss man jene Zweige finden, die auf diesen Zweig führen. Dann jene, die auf diese Zweige führen. Dazu müsste man aber alle Zweige so oft durchgehen, wie es Anzahl an Zweigen gibt. Das müsste doch effizienter gehen?
Alternativ könnte man jeden Zweig durchgehen und den Pfad notieren. Das würde eine Liste von Pfaden ergeben, die letztlich alle im Stamm münden. Es würde aber natürlich nicht reichen, diese Pfade rückwarts durchzugehen.
Ich hab noch keine Idee.
Ein wenig Pseudo-Code, der aber nur die Struktur skizziert.
Delphi-Quellcode:
Type
TBranch = record
BranchID : integer;
TargetBranchID : integer;
TargetBranchPosition: integer;
end;
Type
TTree = record
Branches : array[0..MaxBranches] of TBranch;
end;
Type
TCalculationOrder = array[0..MaxBranches] of integer;
procedure GetBranchOrder(Tree : TTree; var CalculationOrder : TCalculationOrder);
var
i : integer;
begin
for i:=MaxBranches-1 downto 0 do
begin
end;
end;