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

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

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

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

В каждый момент времени имеется дос

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать
Рефераты по математике Есть широкий спектр алгоритмов когда вычисления идут не по фиксированным правилам, а методом проб и ошибок. Примером таких алгоритмов могут служить
Оценок: 1000 (Средняя 5 из 5)

Наверняка у вас есть товары или услуги, продажа которых приносит вам максимальную прибыль. Для быстрого старта в сети вам необходимо создание посадочной страницы (одностраничного сайта), на которой будет размещена информация о маржинальных товарах/услугах интернет магазина. За 8 лет опыта разработки конверсионных страниц мы выработали оптимальную структуру, которая позволит привлекать через landing page больше продаж. На такую структуру «одевается» ваш контент — фирменный стиль, тексты, фотографии, уникальные торговые предложения, после чего страница выходит в свет. Разработка лендинга и запуск в сети — до 7 рабочих дней. Стоит отметить, что в разработку самой посадочной страницы входит и написание копирайтером продающих текстов для вашего бизнеса, чтобы каждый посетитель страницы захотел совершить покупку именно у вас. Результат: качественно разработаная продающая посадочная страница, которая готова приносить вам новых клиентов.

© 2016 - 2022 BigEdu.ru