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

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

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

Скачали данный реферат: Патрикия, Chizh, Суворин, Собачкин, Казакевич, Drugakov.
Последние просмотренные рефераты на тему: оформление доклада, скачать реферат, решебник 9 класс, конспект занятия.

Поделитесь этой записью или добавьте в закладки