Backtracking in Pascal: ricerca del ramo massimo ponderato

Question

Ho imparato Pascal (usando il compilatore Free Pascal) per una settimana e mi sono imbattuto in un esercizio apparentemente facile. Data una struttura come mostrato di seguito, per il ramo pesata massima:

1 
    4 9 
    7 0 2 
4 8 6 3 

Un ramo è una sequenza di numeri, partendo dall'alto (in questo caso: 1), in cui per ogni numero del ramo può espandersi o giù -left o down-right. Ad esempio, il ramo 1-4-0 può espandersi in 1-4-0-8 o 1-4-0-6. Tutti i rami devono iniziare dall'alto e terminare in basso.

In questo esempio, il ramo massimo è 1-4-7-8, il che ci dà 20. Per risolvere questa domanda, ho provato a utilizzare il backtracking. La struttura triangolare è stato immagazzinato in una matrice di tipo 'triangolo':

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

Ecco la mia realizzazione:

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; 

Come potete vedere, ho usato una funzione ausiliaria. Sfortunatamente, non sembra dare il risultato giusto. Per la struttura vista sopra, il risultato che ottengo è 27, che è 7 punti fuori. Cosa mi manca? In che modo l'implementazione ha un aspetto generale? Dovrei aggiungere che il numero massimo di righe è 100, per questo esercizio. Se è necessario un chiarimento, non esitate a chiedere.

Answer 1

Il numero findAux aggiunge il valore errato al risultato ottenuto in modo ricorsivo. Per inciso, puoi un po 'ordinare il codice usando alcune variabili locali. Una versione corretta di 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;