Читайте также:
|
|
Два кода, второй из которых также должен быть извлечен
end;
end;
end;
end;
end;
Begin
for n:= 1 to 8 do x[n]:=0;
for n:= 1 to 8 do mG[n]:= true;
for n:= 2 to 16 do mDP[n]:= true;
for n:= -7 to 7 do mDM[n]:= true;
n:= 0;
PutNextQueen(1);
writeln(‘n=’, n);
end.
Рекурсивные алгоритмы (продолжение)
Пример. Дана матрица A, состоящая из m строк и n столбцов. Элементы матрицы – неотрицательные числа. Пошаговое движение по элементам матрицы начинается от левого верхнего элемента и завершается правым нижним элементом . Каждый шаг движения должен быть сделан либо вправо (если текущий столбец – не последний), либо вниз (если текущая строка – не последняя). Постановка на очередной элемент матрицы оплачивается числом рублей, равным значению этого элемента.
Найти «самый дешёвый» из путей. Назвать его цену.
Решение будет построено двумя способами. Первый из них (Project3A) основан на рекурсии. Во втором (Project3B) применяется т.н. метод динамического программирования.
program Project3A;
{$APPTYPE CONSOLE}
Uses
SysUtils;
Const
mMax = 20;
nMax = 20;
Type
MyRecord = record
CellPrice, Frequency: integer;
Dyrection: 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].Dyrection:= '?';
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 ShowDyrections(var C: MyArray);
Var
i, j: integer;
Begin
Writeln('ShowDyrections');
for i:= 1 to m do
Begin
for j:= 1 to n do
Write(C[i][j].Dyrection: 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
Дата добавления: 2014-12-15; просмотров: 105 | Поможем написать вашу работу | Нарушение авторских прав |