Метод динамического программирования

Begin

Else

Begin

Begin

Var

Else

Begin

Else

End

Begin

Else

End

Begin

Else

End

Begin

Begin

Else

IfDown(i, j) then

Else

ir:= -1;

id:= C[i + 1][j].CellPrice + BestPathRecoursive(i + 1, j, C)

id:= -1;

if (ir >= 0) and (id >= 0) then

if ir < id then

C[i][j].Direction:= 'r';

BestPathRecoursive:= ir;

C[i][j].Direction:= 'd';

BestPathRecoursive:= id;

end;

if ir >=0 then

C[i][j].Direction:= 'r';

BestPathRecoursive:= ir;

if id >= 0 then

C[i][j].Direction:= 'd';

BestPathRecoursive:= id;

end;

// Halt;

end;

end;

procedure ShowPath(var C: MyArray);

k, i, j: integer;

i:= 1;

j:= 1;

p:= 0;

for k:= 1 to m + n - 2 do

Write(' ', C[i][j].Direction);

if C[i][j].Direction = 'r' then

Inc(j)

if C[i][j].Direction = 'd' then

Inc(i);

// else

// Halt;

p:= p + C[i][j].CellPrice;

end;

Writeln;

end;

InitArray(A);

ShowPrices(A);

q:= BestPathRecoursive(1, 1, A);

Writeln('Price of best path = ', q);

ShowPath(A);

Writeln('Price of best path = ', p);

ShowDirections(A);

ShowFrequencies(A);

Readln;

end.

Пример. Найти наиболее «дешевый» путь от элемента матрицы размера до элемента . Второй способ решения задачи.

program Project3B;

{$APPTYPE CONSOLE}

Дата добавления: 2014-01-06