Backtracking in Pascal: Finden des maximal gewichteten Asts

Question

Ich lerne seit einer Woche Pascal (mit dem Free Pascal Compiler) und bin auf eine scheinbar einfache Übung gestoßen. Bei einer Struktur, wie unten dargestellt, finden den maximalen gewichtete Zweig:

1 
    4 9 
    7 0 2 
4 8 6 3 

Ein Zweig ist ein beliebige Folge von Zahlen, beginnend von oben (in diesem Fall: 1), wenn für jede Zahl kann der Zweig erweitert entweder nach unten -links oder rechts unten. Zum Beispiel kann der Zweig 1-4-0 entweder zu 1-4-0-8 oder 1-4-0-6 expandieren. Alle Zweige müssen von oben beginnen und unten enden.

In diesem Beispiel ist die maximale Verzweigung 1-4-7-8, was uns 20 gibt. Um diese Frage zu lösen, habe ich versucht, Backtracking zu verwenden. Die dreieckige Struktur wurde in einem Array vom Typ ‚Dreieck‘ gespeichert:

type triangle = array[1..MAX_NUM_OF_ROWS, 1..MAX_NUM_OF_ROWS] of integer; 

meine Implementierung hier:

function findAux(data: triangle; dim: integer; i: integer; j:integer) : integer; 
begin 
if i = dim then 
    findAux := data[i][j] 
else 
    if findAux(data, dim, i + 1, j + 1) > findAux(data, dim, i + 1, j) then 
     findAux := data[i+1][j+1] + findAux(data, dim, i + 1, j + 1); 
    else 
     findAux := data[i+1][j] + findAux(data, dim, i + 1, j); 
end; 

function find_heaviest_path(data: triangle; dim: integer) : integer; 
begin 
    find_heaviest_path := findAux(data, dim, 1, 1); 
end; 

Wie Sie sehen können, habe ich eine Hilfsfunktion verwendet. Leider scheint es nicht das richtige Ergebnis zu geben. Für die oben gezeigte Struktur ist das Ergebnis, das ich bekomme, 27, was 7 Punkte entfernt ist. Was vermisse ich? Wie sieht die Implementierung insgesamt aus? Ich sollte hinzufügen, dass die maximale Anzahl der Zeilen für diese Übung 100 beträgt. Wenn eine Klärung erforderlich ist, zögern Sie nicht zu fragen.

Answer 1

Ihr findAux fügt dem rekursiv erhaltenen Ergebnis den falschen Wert hinzu. Nebenbei können Sie den Code ein wenig mit einigen lokalen Variablen verbessern. Eine korrigierte Version von findAux:

uses math; 

... 

function findAux(data: triangle; dim: integer; i: integer; j:integer) : integer; 
var 
    left, right: integer; 
begin 
    if i = dim then 
     findAux := data[i][j] 
    else begin 
     left := findAux(data, dim, i + 1, j); 
     right := findAux(data, dim, i + 1, j + 1); 
     findAux := data[i][j] + Max(left, right); 
    end; 
end;