Применение рекурсии в алгоритмах с возвратом. Файловый тип. Ввод/вывод.
Есть широкий спектр алгоритмов когда вычисления идут не по фиксированным правилам, а методом проб и ошибок. Примером таких алгоритмов могут служить алгоритм игры чет-нечет; алгоритм поиска пути в лабиринте в задаче об Ариадне и Тезее. Теперь рассмотрим применение рекурсии для решения таких задач.
Применение рекурсии рассматривается на примере задачи обхода шахматной доски ходом коня. Наряду с демонстрацией применения рекурсии еще раз демон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=1) AND (j
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 (xDim) OR (yDim) 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.
Файлы и работа с ними.
::= file of
Тип компонент — любой, не содержащий файлового. Файлы бывают внутренние и внешние. Внутренние файлы имеют время жизни не больше, чем время выполнения программы. Внешние файлы описываются в заголовке программы, в скобках, после имени программы:
program ();
В списке внешних файлов указываются те файлы, чье время жизни больше времени выполнения программы. Если файл не указан в этом списке — он внутренний, т.е. время его жизни равно времени выполнения программы. Внутренние и внешние файлы следует описать как файловые переменные в разделе описания переменных программы:
:
Над файлами не определено никаких операций, для них не определен даже оператор присваивания.
Для доступа к компонентам файла в Pascal предопределены специальные процедуры: rewrite(f); reset(f); read(f, x);write(f, x); get(f); put(f); и специальная переменная, так называемая буферная переменная f^. На примерах излагаются правила работы и использования перечисленных выше средств работы с файлами. Также рассматривается текстовый файл.
Действия над файлами делятся на 2 группы:
Установка режима работы с файлом
Доступ к компонентам
К первой группе относятся 2 процедуры
rewrite(f) — открывает файл для записи и устанавливает окно на начало
reset(f) — открывает файл для чтения и устанавливает окно на начало
В каждый момент времени имеется доступ только к одной компоненте файла — окно файла или буферная переменная (обозначаемая символом f^, где f — имя файла). Эта переменная имеет тип компоненты файла.
Для последовательного доступа к компонентам файла в Pascal определены 2 процедуры:
read (f:file of , var x:) — читает компоненту из файла f, открытого для чтения, записывает эту компоненту в переменную x и передвигает окно файла на 1 компоненту.
write (f:file of , x:) — записывает компоненту x в файл f, открытый для записи и передвигает окно файла на 1 компоненту.
В качестве параметров для этих процедур можно вместо x: передавать список переменных этого типа. В этом случае несколько компонент файла будут прочитаны или записаны и окно файла сдвинется на соответствующее количество компонент.
Для сдвига окна без чтения или записи определены еще 2 процедуры:
get (f) — сдвигает окно файла f, открытого для чтения, на 1 компоненту
put (f) — сдвигает окно файла f, открытого для записи, на 1 компоненту
Функция eof(f) возвращает true, если окно файла находится на конце файла. В этом случае из него больше нельзя читать.
Текстовые файлы
Файловые переменные типа Text = file of char называются текстовыми. Над ними определены вышеперечисленные операции, как над файлами с типом компоненты char. Но кроме того, что read/write позволяют читать/писать компоненты типа char, можно также читать/писать переменные типов integer, real, а также записывать в файл строковые константы. Для этого надо просто перечислить эти переменные в списке параметров процедур read/write.
Например
var x :integer;
r :real;
fin, fout :Text;
Begin ...
Rewrite(fout); Reset (fin);
Read(fin, x, r);
Write(fout, ‘X=’, x, ‘ R=’, r);
End.
Текстовые файлы условно делятся на строки. Т.е. кроме признака конца файла определен признак конца строки (можно определить функцией eoln(f), аналогичной eof(f)). Определены 2 процедуры
Readln (f, x...) — аналог Read — читает строку из файла.
Writeln(f, x...) — выполняет действия процедуры Write, затем записывает в файл признак конца строки.
В Pascal предопределены 2 имени внешних текстовых файлов:
input — стандартный поток ввода (только чтение) — ввод с клавиатуры
output — стандартный поток вывода (только запись) — вывод на экран
Эти файла надо описывать в заголовке программы как внешние, однако не надо описывать как файловые переменные. Если в параметрах процедур Readln или Writeln опустить имя файла, то ввод/вывод будет осуществляться в стандартные потоки.
Список литературы
Для подготовки данной работы были использованы материалы с сайта www.ergeal.ru/