Применение рекурсии в алгоритмах с возвратом. Файловый тип. Ввод/вывод

Есть широкий спектр алгоритмов когда вычисления идут не по фиксированным правилам, а методом проб и ошибок. Примером таких алгоритмов могут служить алгоритм игры чет-нечет; алгоритм поиска пути в лабиринте в задаче об Ариадне и Тезее. Теперь рассмотрим применение рекурсии для решения таких задач.
Применение рекурсии рассматривается на примере задачи обхода шахматной доски ходом коня. Наряду с демонстрацией применения рекурсии еще раз демонcтрируется пошаговая, структурная разработка программы.
procedure попытка следующего хода;
begin
repeat
if ход приемлем? then
begin
if доска не заполнена? then
begin
if неудача? then стирание предыдущего хода;
end
end
until (ход был удачным?) or (нет других возможных ходов)
end.
В итоге выписывается полный текст программы на Pascal.
program ChessHorse;
const Dim = 5;
PathLen = Dim*Dim;
var Field :Array[1..Dim,1..Dim] of integer; { h[x, y]=i => на клетку
(x, y) конь попал после i-того хода }
n :integer; { Текущая длина пути }
x, y :integer;
function TryMove (i, j :integer) :Boolean;
begin
if n>PathLen then TryMove := true { Путь найден }
else
begin
TryMove := false;
if (i>=1) AND (i<=Dim) AND (j>=1) AND (j<=Dim) AND (Field[i, j]=0) then
begin
Field[i, j] := n;
n := n+1;
if TryMove(i+1, j+2)=true then TryMove := true
else if TryMove(i+1, j-2)=true then TryMove := true
else if TryMove(i-1, j+2)=true then TryMove := true
else if TryMove(i-1, j-2)=true then TryMove := true
else if TryMove(i+2, j+1)=true then TryMove := true
else if TryMove(i+2, j-1)=true then TryMove := true
else if TryMove(i-2, j+1)=true then TryMove := true
else if TryMove(i-2, j-1)=true then TryMove := true;
Field[i, j] := 0;
n := n-1;
end;
end;
end;
Begin
for x:=1 to Dim do
for y:=1 to Dim do
Field[x, y]:=0;
WriteLn ('Поле ', Dim, 'x', Dim);
WriteLn ('Введите координаты коня.');
Write ('X='); ReadLn (x);
Write ('Y='); ReadLn (y);
if (x<1) OR (x>Dim) OR (y<1) OR (y>Dim) then
WriteLn ('Неправильный ответ. System halted...');
else
begin
n := 1;
WriteLn ('Поиск путей длины ', PathLen, ' ...');
case TryMove (x, y) of
true: WriteLn ('Нашел путь :-)');
false: WriteLn ('Нет путей :-(');
end;
end;
End.
Файловый тип. Ввод/вывод.
Все рассмотренные ранее типы данных обладали одним общим свойством - число их компонентов конечно и заранее фиксировано. Однако, существует достаточно широкий класс задач, когда количество компонент данных заранее не известно. Пример - задача кодирования текста поступающего на вход в реальном времени, ввод текста, длина которого заранее не известна и т.п.
В Pascal существует тип данных, множество элементов которого есть последовательности однотипных элементов, длина этих последовательностей не фиксируется заранее. Важной характеристикой этого типа, называемого файловым, является то, что доступ к его компонентам строго последовательный. Это означает, чтобы получить доступ к i-му компоненту, необходимо пройти i-1-ый.
Файловый тип - это единственный тип, обладающий тем свойством, что данные этого типа могут иметь время жизни более времени выполнения программы ! Поэтому этот тип часто используют, чтобы сохранить результаты работы программы для последующей обработки; либо ввести данные извне. Примеры файлового типа, с которыми мы уже много раз встречались много раз - input и output.