[Pascal] obliczanie sumy w trójkącie...

[elu]

Witam serdecznie
Mam takie zadanie, w którym mam podany trójkąt liczb

      5
     3 4
    2 5 6
   5 6 7 8
  5 6 3 4 5

i mam napisać program który obliczy największą sumę liczb, przez które można przejść od wierzchołka do końca drzewa, idąc skośnie (w lewo, prawo) w dół..

proszę o jakieś wskazówki w jaki sposób mogę to napisać...

[Kokosek]

idź od dołu
w każdym wierzchołku na poziomie wyższym maksymalna suma jest większą z sum w wierzchołkach pod nim

[pejs]

No oczywiście, że do dołu Z trójkąta zrobić drzewo - węzły wspólne rozdzielić na 2. Proponowałby zrobić to dynamicznie - w sensie stworzyć sobie drzewo w tablicy dla przykładu (ilość elementów to ilość wierzchołków w drzewie i tak jak w kopcu:
korzeń ma indeks jeden
dzieci maja indeks 2*n i 2*n+1 (dla wierzchołka o numerze n) o i sprawdzać w liściu o największej wadze i iść do tyłu (dzieląc indeks przez 2 i brać część całkowitą), ewentualnie odtworzyć w kolejności od korzenia do liścia - jak wolisz.

[Kokosek]

aby zapisać drzewo w postaci binarnej, trzeba bedzie większość (wszystkie poza brzegowymi) elementów zapisywać podwójnie

[pejs]

Jeśli nie w postaci drzewa to dalej rozpatrywać to w postaci trójkąta. tylko wtedy odtwarzanie ścieżki wygląda tak: jesteśmy w węźle x, sprawdźmy czy węzeł lewy ma odpowiednią wartość, jeśli tak to idźmy w lewo, jeśli nit to w prawo (ku górze).