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


Полнотекстовый поиск по базе:

Главная >> Реферат >> Математика


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




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

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

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

Похожие работы:

  • Алгоритмы и структуры данных. Программирование в Cи

    Реферат >> Информатика, программирование
    ... а также ввода и вывода данных. Необходимо преобразовывать алгоритм всегда таким ... вводить информацию с клавиатуры и выводить ее на экран. Ввод и вывод данных в C происходит через файловый ... C записывается следующим образом: Тип возврата (*Имя функции) (Аргументы ...
  • Распределенные алгоритмы

    Реферат >> Информатика, программирование
    ... машин (файловых серверов, принтеров ... возврат доступным ячеек. Алгоритм ... каналом. Вывод р1 буферизируется и становится вводом р2 ... типа сообщения. Обычно при применении волновых алгоритмов ... использованием рекурсии по t. В алгоритме Broadcast(N, 0) (Алгоритм 14 ...
  • SCADA системы

    Реферат >> Информатика, программирование
    ... Вначале - применение микропроцессоров, использование ... архитектуры алгоритмами, совокупность ... программе, должны иметь тип ввода/вывода (I/O). В эту ... ли рекурсия при обработке ... Остальные аргументы файловых функций не поддаются ... RETURN для возврата результата в ...
  • Предмет и объект прикладной информатики

    Шпаргалка >> Информатика, программирование
    ... Ввод-вывод Ввод-вывод в общем виде Пуск-останов Начало, конец алгоритма, Вход и выход в подпрограмму Стандартные типы ... файлового типа. Переменную файлового типа ... тип рекурсии, называемый «хвостовой рекурсией» ... в возврате к ... применения. Диапазон областей применения ...
  • Алгоритмический язык Паскаль

    Дипломная работа >> Информатика, программирование
    ... типов, т.е. всех простых типов, исключая REAL. 3.2 Операторы процедур. Ввод/вывод ... применением ... алгоритма ... тип компонент может быть любым, кроме файлового типа. Итак, в последнем примере определена F - переменная файлового типа ... поэтому идет возврат наверх. Циклы ...
  • Использование высоких технологий криминальной средой. Борьба с преступлениями в сфере компьютерной информации

    Учебное пособие >> Государство и право
    ... рекурсии. Рекурсия – важнейшее фундаментальное понятие теории алгоритмов. Под рекурсией ... вводом/выводом (драйверы устройств); - программы, управляющие файловой ... применение невозможно в глобальных сетях типа ... алгоритм их функционирования, способа ввода и вывода ...
  • Программирование на языке Турбо Паскаль

    Реферат >> Информатика, программирование
    ... разные типы. Вообще, процедуры ввода и вывода (т.е. ... типа. Для переменных перечисляемых типов возможно применение ... переменная специального файлового типа text: var ... а для возврата к началу ... применить рекурсию для ... следовательно, алгоритм работает быстрее ...
  • Язык С

    Реферат >> Информатика, программирование
    ... 4.10. Рекурсия 4.11. ... типа 7. Ввод и вывод 7.1. Обращение к стандартной библиотеке 7.2. Стандартный ввод и вывод - функции GETCHAR и PUTCHAR 7.3. Форматный вывод ... \B - для возврата на одну позицию, ... , и алгоритма сортировки, ... в применениях, подобных ... файловой ...
  • Язык С

    Дипломная работа >> Информатика, программирование
    ... возвратить значение какого-то другого типа ... \0). 4.10. Рекурсия. В языке ... порядок, и алгоритма сортировки, ... определенной файловой системы ... применение эта операция находит при связях с процедурами, подобным распределителям памяти, и в системах ввода- вывода ...
  • Администрирование локальных сетей

    Реферат >> Компьютерные науки
    ... ввода-вывода. Подсистема ввода-вывода обслуживает запросы файловой ... использовать в алгоритмах перебора с возвратом (backtracking): ... высокого уровня рекурсии в вызов ... типа файловой системы Если не указывать опцию –F то тип файловой ... для обоснования применения к ним ...