 |
Теоретические сведения
|
|
|
|
Лабораторная работа № 3
РЕКУРСИЯ и ИТЕРАЦИЯ
Цель работы: ознакомиться с понятием рекурсии, ее видами и формами; выработать умения применения рекурсии при решении различных типов задач, закрепить знания и умения по применению итерационных алгоритмов.
Теоретические сведения
Для решения задач рекурсивными методами разрабатывают следующие этапы, образующие рекурсивную триаду:
· параметризация – выделяют параметры, которые используются для описания условия задачи, а затем в решении;
· база рекурсии – определяют тривиальный случай, при котором решение очевидно, то есть не требуется обращение функции к себе;
· декомпозиция – выражают общий случай через более простые подзадачи с измененными параметрами.
Целесообразность применения рекурсии в программировании обусловлена спецификой задач, в постановке которых явно или опосредовано указывается на возможность сведения задачи к подзадачам, аналогичным самой задаче. При этом эффективность рекурсивного или итерационного способов решения одной и той же задачи определяется в ходе анализа работоспособности программы на различных наборах данных. Таким образом, рекурсия не является универсальным способом в программировании. Ее следует рассматривать как альтернативный вариант при разработке алгоритмов решения задач.
Повысить эффективность рекурсивных алгоритмов часто представляется возможным за счет пересмотра этапов триады. Например, введение дополнительных параметров, не оговоренных в условии задачи, в реализации декомпозиции могут быть применены другие соотношения, а также можно организовать расширение базовых случаев с сохранением промежуточных результатов.
|
|
|
Таблица 3.1 Понятия и термины, связанные с рекурсией
| № | Понятие, термин | Неформальное определение, пояснение |
| 1. | Рекурсия | 1. Введение в определение объекта ссылку на сам объект. 2. Прием сведения решения некоторой задачи к решению серии задач, подобных исходной. |
| 2. | Рекурсивный алгоритм (процедура, функция) | 1. Алгоритм (функция, процедура) называется рекурсивным, если в его определении содержится прямой или косвенный вызов этого же алгоритма. 2. Рекурсивная функция - одно из математических уточнений интуитивного понятия вычислимой функции. |
| 3. | Рекуррентное соотношение (рекуррентная формула) | Формула вида an+p=F(an, an+1,…, an+p-1) (p>=1), позволяющая вычислять любой член бесконечной последовательности a1, a2,…, если заданы её первые p членов. Определяемая рекуррентной формулой последовательность называется возвратной. |
| 4. | Глубина рекурсивных вызовов | Количество элементов полной рекурсивной траектории в пространстве параметров. |
| 5. | Рекурсивные вычисления Прямой и обратный ход вычислений | Прямой ход соответствует совокупности всех предвычислений, реализуемых до входа рекурсивной траектории в базу. Обратный ход - совокупности отложенных вычислений, производимым после встречи с индикатором завершения рекурсивных вызовов. |
| 6. | Рекурсивный стек | Область памяти, в которую заносятся значения всех локальных переменных алгоритма (программы) в момент рекурсивного обращения. Каждое такое обращение формирует один слой данных стека. При завершении вычислений по конкретному обращению а из стека считывается соответствующий ему слой данных, и локальные переменные восстанавливаются, снова принимая значения, которые они имели в момент обращения |
| 7. | Адаптивный рекурсивный алгоритм | Алгоритм, который благодаря рекурсивности учитывает те или иные индивидуальные характеристики решаемой задачи из области своего определения |
Существуют три разных формы рекурсивных подпрограмм:
|
|
|
| 1) Форма с выполнением действий до рекурсивного вызова (с выполнением действий на рекурсивном спуске). | 2) Форма с выполнением действий после рекурсивного вызова (с выполнением действий на рекурсивном возврате). | 3) Форма с выполнением действий как до, так и после рекурсивного вызова (с выполнением действий как на рекурсивном спуске так и на рекурсивном возврате. |
| procedure Rec; begin S; if условие then Rec; end; | procedure Rec; begin if условие then Rec; S; end; | procedure Rec; begin S1; if условие then Rec; S2; end; |
Все формы рекурсивных процедур находят применение на практике. Многие задачи, в том числе вычисление факториала, безразличны к тому, какая используется форма рекурсивной процедуры.
Пример 1. Рассмотрим функцию вычисления факториала.
Разработаем рекурсивную триаду.
Параметризация: n – неотрицательное целое число.
База рекурсии: для n =0 факториал равен 1.
Декомпозиция: n!=(n-1)!xn.
Program Factorial;
var
n, b: Integer;
Function Fact (a: Integer): Integer;
{Рекурсивая функция, вычисляющая а! }
begin {Fact}
if a < 0 then
WriteLn (Ошибка в задании а')
else
if a = 0 then
Fact:= 1
else Fact:= a * Fact(a-1)
end {Fac};
{---------------}
begin {main}
WriteLn ('Введите число');
ReadLn (b);
WriteLn ('b!= ',Fact(b))
end {main}.
В результате первого рекурсивного обращения к функции Fact (т.е. обращения к самой себе) в памяти компьютера создается копия этой функции (с собственными локальными переменными), которой передается параметр со значением b-1. В результате второго рекурсивного обращения к функции Fact создается еще одна копия этой функции (как бы вложенная в первую и тоже с собственными локальными переменными), которой передается параметр со значением b-2. Затем функция Fact будет обращаться к самой себе до тех пор, пока она в последней своей копии не возвратит значение 1 (и при этом будут создаваться все новые ее копии, существующие независимо одна от другой).
«Движение вглубь» продолжается до тех пор, пока параметр, с использованием которого в очередной раз будет иметь место обращение к функции Fact, не окажется равным 0. К моменту завершения рекурсии в программе будут созданы B копий функции Fact, в поледеней из которых ее значение окажется равным 1. После этого будет иметь место «движение изнутри наружу», т.е. значение функции Fact из очередной «внутренней» ее копии будет умножаться на значение а из «внешней» копии, и при этом «внутренняя» копия функции ликвидируется. По завершении этого процесса окажется вычислен факториал числа B.
|
|
|
Алгоритмы с возвратом. Еще один класс задач, которые целесообразно решать рекурсивными методами, - это задачи, для решения которых не существует определенного алгоритма. В этом случае приходится искать решение методом проб и ошибок, подобно поиску выхода из лабиринта.
Аналогия тут прямая, поскольку, блуждая в лабиринте, мы регулярно забредаем в тупик и вынуждены возвращаться обратно и искать другой путь. При этом, если мы не хотим кружить в нем вечно, нам следует помечать уже обследованные ветви, чтобы не возвращаться к ним вновь.
Итак последовательность действий: обследовать лабиринт - значит обследовать каждую из его ветвей. Дойдя до развилки, повторять алгоритм рекурсивно, возвращаясь из тупиковых ветвей. Если лабиринт не содержит циклов, рано или поздно вы найдете путь на волю. Если содержит, алгоритм немного усложняется, но все рано приводит к цели.
Реальные задачи, конечно, обычно сложнее, чем просто хождение по лабиринту. Однако в целом поиск решения практически такой же:
· мы делаем очередной шаг в поиске решения,
· фиксируем его и пытаемся на его основе сделать следующий.
· Не найдя решение, мы должны попробовать другой допустимый шаг.
· Если все возможные шаги уже перебраны, а решение так и не найдено, следует отступить на шаг назад и повторить процедуру поиска.
Примеры
ВСЕ ПРИМЕРЫ ВЫПОЛНЯТЬ ПО ШАГАМ, ПРОСЛЕЖИВАЯ ИЗМЕНЕНИЕ ЗНАЧЕНИЙ В ОКНЕ ОТЛАДКИ.
Пример 2. Вычислить количество цифр в заданном натуральном числе a.
var n:longint;
Function K(a: longint): byte;
Begin
If a < 10 Then k:= 1
Else K:= 1 + K(a Div 10)
End;
begin
writeln ('vvedite chislo');
readln (n);
writeln ('v chisle ',n,' ', K(n),' chisel');
end.
Пример 3. Составить программу для расчета n-го члена заданной арифметической прогрессии.
program progres;
var a1, d: real; n:byte;
Function Ar_n(a1, d: real; n:byte): real;
Begin
If n = 1 Then Ar_n:= a1
Else Ar_n:= Ar_n(a1, d, n-1) + d
|
|
|
End;
BEGIN
Writeln ('введите первый член прогрессии ');
readln (a1);
Writeln ('введите разность прогрессии ');
readln (d);
Writeln ('введите № члена прогрессии ');
readln (n);
Writeln ('значение ',Ar_n(a1, d, n));
END.
Пример 4. Вычислить k-й член последовательности Фибоначчи, первые два члена которой равны 1, каждый последующий есть сумма двух предыдущих (1, 1, 3, 5, 8, …).
var n:longint;
Function F(k: byte): longint;
Begin
If (k = 1) Or (k = 2) Then F:= 1
Else
F:= F(k - 1) + F(k - 2)
End;
begin
writeln ('vvedite ¹ chisla progressii ');
readln (n);
writeln ('chislo Fibonachi s nomerom ',n,' = ', F(n));
end.
Пример 5. Рекурсивный и нерекурсивный поиск наибольшего общего делителя двух чисел.
PROGRAM NOD;
var X,Y: Integer;
{ ------------------------------------------------ }
FUNCTION RecursiveNOD (n,m: Integer): Integer;
BEGIN { Рекурсивное вычисление НОД чисел n и m }
If n=m
then RecursiveNOD:=n
else If n>m
then RecursiveNOD:=RecursiveNOD (n-m,m)
else RecursiveNOD:=RecursiveNOD (n,m-n)
END;
{ ------------------------------------------------ }
FUNCTION NonRecursiveNOD (n,m: Integer): Integer;
BEGIN { Алгоритм, использующий вместо рекурсии повторение }
While n<>m do
If n>m
then n:=n-m
else m:=m-n;
NonRecursiveNOD:=n
END;
{ ---- }
BEGIN
Write ('Введите два целых числа, отличных от 0: '); Read (X); ReadLn (Y);
Write ('Результат, полученный рекурсивно: ');
WriteLn (RecursiveNOD(Abs(X),Abs(Y)));
Write ('Результат, полученный нерекурсивно: ');
WriteLn (NonRecursiveNOD(Abs(X),Abs(Y)))
END.
Пример 6. Определить сумму элементов заданного числового массива a, элементами которого являются целые числа.
Комментарии: Параметр функции: k — количество элементов массива, сумма которых рассчитывается при каждом вызове функции. Когда k = 1, то значение функции равно единственному элементу такого массива, иначе — сумме последнего элемента и значения этой же функции для массива без учета последнего элемента.
Задание: В приведенном виде функция может быть использована для решения задачи только применительно к массиву с именем a. Создайте функцию, которая может “обрабатывать” любые массивы одного типа (следует обрабатываемый массив сделать параметром функции).
var a: array [1..10] of integer;
n:longint; i:integer;
Function S(k: byte): longint;
Begin
If k = 1 Then S:= a[k]
Else S:= a[k] + S(k - 1)
End;
begin
writeln ('vvedite kolichestvo elementov massiva');
readln (n);
writeln ('vvedite elementy massiva');
for i:=1 to n do
readln (a[i]);
write (' massiv imeet vid: ');
for i:=1 to n do
write(a[i]:5); writeln;
writeln ('summa elementov massiva = ', S(n));
end.
Пример 7. Процедура вывода цифр p-ичного представления заданного десятичного натурального числа (2≤p≤9).
Решение: Необходимо вспомнить, как происходит перевод целых десятичных чисел в систему счисления с другим основанием.
Обозначим заданное десятичное число — n. Для его перевода в p-ичную систему счисления требуется определение остатка от деления на p числа n и затем промежуточных частных до тех пор, пока не получится частное, меньшее p. Но если процедуру, обеспечивающую определение и вывод остатков (имя величины — remin), оформить в виде:
|
|
|
Procedure From10(a: longint; p: byte);
Var remin: byte;
Begin
{Определяем остаток}
remin:= a mod p;
{Выводим его}
write(remin);
{Если нужно, делаем то же самое для промежуточного частного}
If a >= p Then From10(a div p, p)
End;
— то цифры будут выведены, начиная с последней. Для получения требуемого результата необходимо определение и вывод остатков проводить после рекурсивного вызова процедуры:
Procedure From10(a: longint; p: byte);
Var remin: byte;
Begin
{Если нужно, вызываем процедуру From10 для промежуточного частного}
If a >= p Then From10(a div p, p);
{Определяем остаток для текущих значений параметров процедуры}
remin:= a mod p;
{Выводим его}
write(remin)
End;
Примечание: Последний вариант рекурсивной процедуры называется “Форма с выполнением действий после рекурсивного вызова (или с выполнением действий на рекурсивном возврате)”.
var
n:longint; i:integer;
Procedure From10(a: longint; p: byte);
Var remin: byte;
Begin
{Если нужно, вызываем процедуру From10 для промежуточного частного}
If a >= p Then From10(a div p, p);
{Определяем остаток для текущих значений параметров процедуры}
remin:= a mod p;
{Выводим его}
write(remin)
End;
begin
writeln ('vvedite chislo');
readln (n);
writeln ('vvedite sistemu schisleniya');
readln (i); write ('chislo ',n,' v ',i,' ichnoy sisteme schisleniya = ');
From10(n,i);
writeln
end.
Пример 8. Мой богатый дядюшка подарил мне один доллар в мой первый день рождения. В каждый следующий день рождения он удваивал свой подарок и прибавлял к нему столько долларов, сколько лет мне исполнилось. Написать программу, подсчитывающую общую сумму денег, подаренных к N-му дню рождения и указывающую, к какому дню рождения сумма подарка превысит 100$.
Решение: Вначале напишем программу, сколько денег получит племянник к n-му дню рождения.
Введем обозначения: k - число лет племянника, p - количество денег, которые дает дядя на каждом дне рождения, s - общая сумма денег, полученных племянником за все годы, n - счетчик числа дней рождения, который считает в обратном порядке от n (введенного пользователем) до 1.
Задаются первоначальные значения формальным параметрам процедуры: n - вводится пользователем из основной программы (вы обратили внимание, что в этой, как и в предыдущей процедуре нет выходных параметров и нет переменных в самой процедуре, хотя возможны и другие варианты).
Увеличивается число лет: k:= k + 1; вычисляется подарок к k-тому дню рождения: p:= 2*p + k; вызывается процедура, в которой увеличивается на p общая сумма полученных денег s и уменьшается на 1 число дней рождения:
uncle(k, p, s + p, n - 1)
Далее весь процесс повторяется, до тех пор, пока n не станет равным 1.
program Rich_man1; { rich man - богатый}
uses Crt;
var
n: integer;
{-----------------------------------------------}
Procedure uncle(k, p, s, n: longint); {uncle - дядя}
begin
if n = 1
then write(s)
else
begin
k:= k + 1;
p:= 2*p + k;
uncle(k, p, s + p, n - 1)
end
end;
{----------------------------------------------------------}
begin
write(' Введите число лет племянника '); readln(n);
write(' Я получу к ', n, ' -ому дню рождения ');
uncle(1, 1, 1, n);
writeln(' долларов ')
end.
Во второй части условия требуется определить число лет, когда сумма полученных денег будет равна или превысит 100 долларов. Для этого в процедуре меняется опорное условие: if s >= 100 then write(n), а все остальное остается без изменений.
Program Rich_man2;
uses Crt;
var
n: integer;
{-------------------------------------------------------}
Procedure uncle1(k, p, s, n: longint);
begin
if s >= 100
then write(n)
else
begin
k:= k + 1;
p:= 2*p + k;
uncle1(k, p, s + p, n + 1)
end
end;
{---------------------------------------------------------}
begin
write(' Сумма подарка превысит 100 долларов к ');
uncle1(1, 1, 1, 1);
writeln(' -ому дню рождения')
end.
Пример 9. Над цепью озер летела стая белых гусей. На каждом озере садилось половина гусей и еще полгуся, а остальные летели дальше. Все гуси сели на семи озерах. Сколько гусей было в стае?
Решение:Математически задача решается устно очень остроумным способом.
Пусть вместе со стаей белых гусей все время летит еще один, Серый гусь. Если к некоторому озеру подлетит m белых гусей и Серый, то на этом озере садится - ровно половина всех гусей вместе с серым. Поэтому после каждого озера число летящих гусей уменьшается ровно вдвое. После семи озер оно уменьшится в 27 = 128 раз, а остается летящим один Серый гусь. Значит, вначале было 128 гусей, из них 127 - белых.
А теперь выполним, образно говоря, прямые рассуждения для решения задачи.
Обозначим через xk количество летящих белых гусей, когда впереди еще k озер.
В процедуру вводятся всего две переменные: x - искомое число гусей; k - число озер. Процедура устроена с расчетом, что гуси уже пролетели все 7 озер, значит надо вводить значение для x - один (1), а для k - семь (7). В процедуре устроено, что число k уменьшается на 1 и тогда опорным условием ("якорем") завершения процедуры является условие равенства 1 значений k и после этого на экран надо выдать значение числа гусей:
if k = 1 then writeln(x)
Опорное условие может быть и другим, если первоначальным значением k будет 1, тогда при повторном обращении к процедуре значение k надо не уменьшать, а увеличивать на 1 (k + 1), опорным условием, в этом случае, будет k = 7.
Program Problem11;
uses Crt;
var
k: integer;
{---------------------------------------------------------}
Procedure goose(x, k: integer);
begin
if k = 1 then write(x)
else goose(2*x + 1, k - 1)
end;
{---------------------------------------------------------}
begin
write(' Введите число озер'); readln(k);
write(' В стае было ');
goose(1, k);
writeln(' гусей')
end.
Пример 10. Перемножая большие числа, можно быстро получить переполнение. Поэтому, для того чтобы напечатать произведение, превышающее наибольшее допустимое для данного целого типа (integer или longint) числа, надо применить искусственные средства.
Составим программу для печати произведения двух чисел, которое может превышать максимально допустимое целое число.
Решение: Процедура multiplication умножает число a на каждую цифру числа b, начиная с цифры единиц. Последняя цифра полученного произведения, сложенная с последней цифрой имеющегося в памяти частичного произведения, печатается, а все прочие цифры запоминаются - передаются как параметры при рекурсивном обращении к процедуре multiplication. В самом конце производится умножение на первую (левую) цифру числа b. На этом умножение заканчивается. Тогда печатается начало результата - накопившееся частичное произведение без последней цифры (s div 10), а после него при возвращении из рекурсии - все остальные цифры произведения (s mod 10) в обратном порядке по сравнению с тем, как они вычислялись при входе в рекурсию.
Program Problem13; { Большое произведение}
uses Crt;
var
x, y: longint;
{---------------------------------------------------------}
Procedure multiplication(a, b, s: longint);
begin
if b <> 0
then
begin
s:= s+a*(b mod 10);
multiplication(a, b div 10, s div 10);
write(s mod 10:1)
end
else if s <> 0 then write(s)
end;
{-------------------------------------------------------}
begin
write(' Введите первый множитель '); readln(x);
write(' Введите второй множитель '); readln(y);
write(x,'*',y:1,' = ');
if ((x < 0) and (y > 0)) or ((x > 0) and (y < 0)) then write('-');
multiplication(abs(x), abs(y), 0);
writeln
end.
Пример 11. Имеется некоторая сумма денег S и набор монет с номиналами a1, …, an. Монета каждого номинала имеется в единственном экземпляре. Необходимо найти все возможные способы разменять сумму S при помощи этих монет.
const n = 6; {число монет}
s = 33; {требуемая сумма}
a: array[1..n]of integer =(1,2,3,5,10,15); {номиналы монет}
var kol: array[1..n] of integer; {сколько взято таких монет -0 или 1}
found: boolean; { признак, что хотя бы одно решение найдено}
s:integer; {сумма денег}
procedure rec(k,s1:integer);
{k – число уже использовавшихся монет, s1 – набранная сумма}
var i: integer;
begin
if s=s1 then begin {вывод найденного решения}
found:=true;
for i:=1 to n do
if kol[i]>0 then write(a[i],' ');
writeln; exit
end;
for i:=k+1 to n do {цикл по всем еще неиспользовавшимся монетам}
begin
{самое критичное место рекурсивного перебора –
«взять-проверить-вернуть обратно, чтобы взять следующую»}
kol[i]:=1; {взять i-ю монету}
rec(i,s1+a[i]); {проверить, годится ли}
kol[i]:=0; {вернуть i-ю обратно, чтобы взять следующую}
end;
end;
begin
writeln ('введите сумму денег'); readln (s);
found:=false;
rec(0,0);
if not found then writeln(‘Разменять невозможно’)
end.
Пример 12. В одной из древних легенд говорится следующее. «В храме Бенареса находится бронзовая плита с тремя алмазными стержнями. На один из стержней бог при сотворении мира нанизал 64 диска разного диаметра из чистого золота так, что наибольший диск лежит на бронзовой плите, а остальные образуют пирамиду, сужающуюся кверху. Это – башня Брамы. Работая день и ночь, жрецы переносят диски с одного стержня на другой, следуя законам Брамы:
1. диски можно перемещать с одного стержня на другой только по одному;
2. нельзя класть больший диск на меньший.
Когда все 64 диска будут перенесены с одного стержня на другой, и башня, и храмы, и жрецы-брамины превратятся в прах, и наступит конец света».
Эта древняя легенда породила задачу о Ханойской башне: переместить m дисков с одного из трех стержней на другой, соблюдая «законы Брамы».
Назовем стержни левым (left), средним (middle) и правым (right). Задача состоит в переносе m дисков с левого стержня на правый.
Задача может быть решена одним перемещением только для одного (m = 1) диска. В общем случае потребуется 2m-1 перемещений.
Построим рекурсивное решение задачи, состоящее из трех этапов:
a) перенести башню, состоящую из m – 1 диска, с левого стержня на средний;
b) перенести один оставшийся диск с левого стержня на правый;
c) перенести башню, состоящую из m – 1 диска, со среднего стержня на правый.
Таким образом, задача о перемещении m дисков сводится к задаче о перемещении m – 1 диска. Обращаясь опять к этому же алгоритму, сведем задачу к перемещению m – 2 дисков. Продолжая этот процесс, получим, в конце концов, задачу о перемещении одного диска. Эта задача решается за один ход. Таким образом, в процессе решения возникают промежуточные задачи: переместить башню из нескольких n дисков с одного стержня на другой.
Обозначим тот стержень, с которого следует снять диски, через s1, на который надеть – через sk, а вспомогательный стержень через sw.
Оформим алгоритм решения задачи о переносе башни из n дисков с s1 на sk в виде процедуры move с 4-мя параметрами: n, s1, sw, sk; алгоритм для n = 1 выделим в отдельную процедуру step, которая перемещает один диск со стержня s1 на sk.
1 вариант
type
st = (left, middle, right);
nat = 1..maxint;
var
m: nat; {m – число дисков}
procedure move(n: nat; s1, sw, sk: st);
{перемещение n дисков с s1 на sk}
procedure step;
{перемещение одного диска с s1 на sk}
procedure print(s: st);
begin
case s of
left: write(' лев. ');
middle: write(' средн. ');
right: write(' прав. ')
end;
end;
begin {step}
write(' снять диск с ');
print(s1);
write(' надеть на ');
print(sk);
writeln
end;
begin {move}
if n = 1 then
step
else begin
move(n - 1, s1, sk, sw);
step;
move(n-1, sw, s1, sk)
end
end;
begin
writeln('введите число дисков')
read(m); {число дисков}
writeln('для ', m:3, ' дисков следует произвести ',
'следующие действия:');
move(m, left, middle, right);
end.
2 вариант
Procedure Towers(n:byte; A, C, B: char)
{переложить N колец с А на С, используя В как промежуточный}
begin
if n=1 then writeln(A, ‘ ® ’, C)
else begin
Towers(n-1, A, B, C);
writeln(A, ‘ ® ‘, C);
Towers(n-1, B, C, A)
end
end;
begin
Towers(4, ‘A’, ‘C’, ‘B’) { решаем задачу при N = 4 }
end.
Пример 13. Задача о "восьми ферзях" — хорошо известный пример использования метода проб и ошибок и алгоритмов с возвратом. Этой задачей в 1780 г. занимался К. Ф. Гаусс, но полного ее решения не дал, и это не удивительно. Для подобного класса задач характерно отсутствие аналитического решения, но они требуют большого объема изнурительных вычислений, терпения, аккуратности. Поэтому такие задачи отдают для решения вычислительным машинам, обладающим вышеперечисленными достоинствами в полной мере.
Задача о восьми ферзях формулируется так: нужно расставить восемь ферзей на шахматной доске размером 8×8 таким образом, чтобы ни один ферзь не угрожал другому, то есть чтобы ни один из них не находился на одной и той же горизонтали, вертикали или диагонали, что и любой другой.
Грубый вариант решения задачи:
PROCEDURE Try(i: INTEGER);
BEGIN
инициация выбора положения i-гo ферзя;
REPEAT выбор очередного положения;
IF безопасно THEN поставить ферзя;
IF i < 8 THEN Try(i+1);
IF неудача THEN убрать ферзя END
END
END
UNTIL удача OR мест больше нет
END Try;
Чтобы идти дальше, нужно остановиться на каком-либо представлении для данных. Поскольку из шахматных правил мы знаем, что ферзь бьет все фигуры, находящиеся на той же самой вертикали, горизонтали или диагонали, то заключаем, что на каждой вертикали может находиться один и только один ферзь, поэтому при поиске места для i-го ферзя можно ограничить себя лишь i-й вертикалью. Таким образом, параметр i становится индексом вертикали, а процесс выбора возможного местоположения ограничивается восемью допустимыми значениями для индекса горизонтали j.
Остается решить вопрос: как представлять на доске эти восемь ферзей? Очевидно, доску вновь можно было бы представить в виде квадратной матрицы, но после небольших размышлений мы обнаруживаем, что это значительно усложнило бы проверку безопасности поля. Конечно, подобное решение нежелательно, поскольку такая операция выполняется очень часто. Поэтому хотелось бы остановиться на таком представлении данных, которое, насколько это возможно, упростило бы проверку. В этой ситуации лучше всего делать непосредственно доступной именно ту информацию, которая действительно важна и чаще всего используется. В нашем случае это не поля, занятые ферзями, а сведения о том, находится ли уже ферзь на данной горизонтали или диагонали. (Мы уже знаем, что на каждой k-й вертикали (1 <= k <= i) стоит только один ферзь.) Эти соображения приводят к таким описаниям переменных:
VAR x: ARRAY [1..8] OF INTEGER;
a: ARRAY [1..8] OF BOOLEAN;
b: ARRAY [b1..b2] OF BOOLEAN;
c: ARRAY [c1..c2] OF BOOLEAN;
где
xi обозначает местоположение ферзя на i-й вертикали;
aj указывает, что на j-й горизонтали ферзя нет;
bk указывает, что на k-й /-диагонали ферзя нет;
сk указывает, что на k-й \-диагонали ферзя нет.
Выбор границ индексов b1, b2, с1, с2 определяется исходя из способа вычисления индексов для b и с. На /-диагонали у всех полей постоянна сумма координат i и j, а на \-диагонали постоянна их разность. Оператор поставить ферзя превращается в такие операторы:
х[i]:= j; a[j]:= FALSE; b[i+j]:= FALSE; c[i-j]:= FALSE;
а оператор убрать ферзя — в такие:
a[j]:= TRUE; b[i+j]:= TRUE; c[i-j]:= TRUE;
Условие безопасно выполняется, если поле с координатами i, j лежит на горизонтали и вертикали, которые еще не заняты. Следовательно, ему соответствует логическое выражение
а[j] & b[i+j] & c[i-j];
program ferz;
uses crt;
var s,i:integer;
a:array[1..8] of boolean;
b:array[2..16] of boolean;
c:array[-7..7] of boolean;
x:array[1..8]of integer;
procedure print;
var k:integer;
begin
s:=s+1;
write('Решение номер ',s:2,': ');
for k:=1 to 8 do write(x[k]:4);
writeln;
write('Press <Enter>');
readln;
end;{of print}
procedure tr (i:integer);
var j:integer;
begin
for j:=1 to 8 do
if a[j]and b[i+j]and c[i-j] then
begin
x[i]:=j;
a[j]:=false;b[i+j]:=false;c[i-j]:=false;
if i<8 then tr(i+1) else print;
a[j]:=true;b[i+j]:=true;c[i-j]:=true;
end;
end;{of try}
begin{of main}
clrscr;
for i:=1 to 8 do a[i]:=true;
for i:=2 to 16 do b[i]:=true;
for i:=-7 to 7 do c[i]:=true;
s:=0;
tr(1)
end.
Контрольные вопросы
1. Что такое рекурсия?
2. Перечислите этапы, образующие рекурсивную триаду.
3. Что такое параметризация?
4. Что такое база рекурсии?
5. Что такое декомпозиция?
6. За счет чего можно повысить эффективность рекурсивных алгоритмов?
7. Дайте определение рекурсивного алгоритма.
8. Дайте определение рекуррентного соотношения.
9. Что такое глубина рекурсивных вызовов?
10. Что такое рекурсивный стек?
11. Дайте определение адаптивного рекурсивного алгоритма.
12. Перечислите формы рекурсивных подпрограмм.
13. Как выглядит форма с выполнением действий на рекурсивном спуске?
14. Как выглядит форма с выполнением действий на рекурсивном возврате?
15. Как выглядит форма с выполнением действий как на рекурсивном спуске так и на рекурсивном возврате?
16. Назовите шаги, которые необходимо осуществить при использовании алгоритма с возвратом.
17. Написать пояснения к каждой переменной и каждой строке программы о 8 ферзях.
Содержание отчета:
1. Лабораторная работа № 3
2. Тема лабораторной работы.
3. Цель работы.
4. Краткие теоретические сведения (в виде ответов на контрольные вопросы).
5. Решение задач.
6. Вывод о проделанной работе.
|
|
|
