Реферат: Применение рекурсии в алгоритмах с возвратом. Файловый тип. Ввод/вывод
Название: Применение рекурсии в алгоритмах с возвратом. Файловый тип. Ввод/вывод Раздел: Рефераты по математике Тип: реферат |
. Есть широкий спектр алгоритмов когда вычисления идут не по фиксированным правилам, а методом проб и ошибок. Примером таких алгоритмов могут служить алгоритм игры чет-нечет; алгоритм поиска пути в лабиринте в задаче об Ариадне и Тезее. Теперь рассмотрим применение рекурсии для решения таких задач. Применение рекурсии рассматривается на примере задачи обхода шахматной доски ходом коня. Наряду с демонстрацией применения рекурсии еще раз демонcтрируется пошаговая, структурная разработка программы. procedure попытка следующего хода; В итоге выписывается полный текст программы на 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 опустить имя файла, то ввод/вывод будет осуществляться в стандартные потоки. |