Лекция 5
Рекурсивные алгоритмы (продолжение)
Пример. Дана
матрица A,
состоящая из m
строк и n
столбцов. Элементы матрицы – неотрицательные
числа. Пошаговое движение по элементам
матрицы начинается от левого верхнего
элемента
и завершается правым нижним элементом
.
Каждый шаг движения должен быть сделан
либо вправо (если текущий столбец – не
последний), либо вниз (если текущая
строка – не последняя). Постановка на
очередной элемент матрицы оплачивается
числом рублей, равным значению этого
элемента.
Найти «самый дешёвый» из путей. Назвать его цену.
Решение будет построено двумя способами. Первый из них (Project3A) основан на рекурсии. Во втором (Project3B) применяется т.н. метод динамического программирования.
program Project3A;
{$APPTYPE CONSOLE}
uses
SysUtils;
const
mMax = 20;
nMax = 20;
type
MyRecord = record
CellPrice, Frequency: integer;
Direction: char;
end;
MyArray = array[1 .. mMax, 1 .. nMax] of MyRecord;
var
m, n, p, q: 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].Frequency := 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 ShowFrequencies(var C: MyArray);
var
I, j: integer;
begin
Writeln('ShowFrequencies');
for i := 1 to m do
begin
for j := 1 to n do
Write(C[i][j].Frequency : 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;
function BestPathRecoursive(i, j: integer; var C: MyArray): integer;
var
id, ir: integer;
begin
Inc(C[i][j].Frequency);
if (i = m) and (j = n) then
BestPathRecoursive := 0
else
begin
if Right(i, j) then
ir := C[i][j + 1].CellPrice + BestPathRecoursive(i, j + 1, C)
else
ir := -1;
if Down(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
if ir < 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.