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

Есть широкий спектр алгоритмов когда вычисления идут не по фиксированным правилам, а методом проб и ошибок. Примером таких алгоритмов могут служить алгоритм игры чет-нечет; алгоритм поиска пути в лабиринте в задаче об Ариадне и Тезее.

ВНИМАНИЕ! Работа на этой странице представлена для Вашего ознакомления в текстовом (сокращенном) виде. Для того, чтобы получить полностью оформленную работу в формате Word, со всеми сносками, таблицами, рисунками (вместо pic), графиками, приложениями, списком литературы и т.д., необходимо скачать работу.

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

 Есть широкий спектр
алгоритмов когда вычисления идут не по фиксированным правилам, а методом проб и
ошибок. Примером таких алгоритмов могут служить алгоритм игры чет-нечет;
алгоритм поиска пути в лабиринте в задаче об Ариадне и Тезее. Теперь рассмотрим
применение рекурсии для решения таких задач.


 Применение рекурсии
рассматривается на примере задачи обхода шахматной доски ходом коня. Наряду с
демонстрацией применения рекурсии еще раз демон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.

Файлы и работа с ними.

  <описание файлового
типа>::= 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 опустить имя файла, то ввод/вывод будет осуществляться в
стандартные потоки.

Список литературы

Для подготовки данной работы были использованы материалы с сайта http://www.ergeal.ru/



Скачиваний: 1
Просмотров: 0
Скачать реферат Заказать реферат