IfDown(i, j) then

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

Else

id:= -1;

 

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

Begin

Ifir < id then

Begin

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

BestPathRecoursive:= ir;

End

Else

Begin

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

BestPathRecoursive:= id;

end;

End

Else

if ir >=0 then

Begin

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

BestPathRecoursive:= ir;

End

Else

if id >= 0 then

Begin

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

BestPathRecoursive:= id;

end;

Else

// Halt;

end;

end;

 

procedure ShowPath(var C: MyArray);

 

Var

k, i, j: integer;

Begin

i:= 1;

j:= 1;

 

p:= 0;

 

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

Begin

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

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

Inc(j)

Else

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

Inc(i);

// else

// Halt;

 

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

end;

 

Writeln;

end;

Begin

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}

 

Uses

SysUtils;

 

Const

mMax = 20;

nMax = 20;

 

Type

MyRecord = record

CellPrice, PathPrice: integer;

Direction: char;

end;

 

MyArray = array [1.. mMax, 1.. nMax] of MyRecord;

 

Var

m, n, p: integer;

A: MyArray;

 

procedure InitArray(var C: MyArray);

Var

i, j: integer;

Begin

Randomize;

 

m:= 3 + Random(mMax – 2);

n:= 3 + Random(nMax – 2);

Writeln('m=', m, ' n=', n);

 

for i:= 1 to m do

for j:= 1 to n do

Begin

C[i][j].CellPrice:= Random(mMax + nMax);

C[i][j].PathPrice:= 0;

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

end;

end;

procedure ShowPrices(var C: MyArray);

Var

i, j: Integer;

Begin

Writeln('ShowPrices');

 

for i:= 1 to m do

Begin

for j:= 1 to n do

Write(C[i][j].CellPrice: 5);

 

Writeln;

end;

end;

 

procedure ShowDirections(var C: MyArray);

Var

i, j: integer;

Begin

Writeln('ShowDirections');

 

for i:= 1 to m do

Begin

for j:= 1 to n do

Write(C[i][j].Direction: 3);

 

Writeln;

end;

end;

 

function Right(i, j: integer): boolean;

Begin

if j < n then Right:= true else Right:= false;

end;

 

function Down(i, j: integer): boolean;

Begin

if i < m then Down:= true else Down:= false;

end;

 

 

procedure BestPathNonRecoursive(var C: MyArray);

Var

i, j, k, ir, id: integer;

 

Begin

C[m][n].PathPrice:= 0;

 

for k:= m + n - 1 downto 1 do

for i:= m downto 1 do

Begin

j:= k - i;

if j > n then break;

if j < 1 then continue;