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