IfDown(i, j) thenid:= 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;
|