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

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

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

Рекомендуем скачать другие рефераты по теме: исторические рефераты, куплю диплом.



1  2  3  4 | Следующая страница реферата

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