Var I:integer;

begin

while a[1]<4 do {условие "сброса" счетчика}

begin for i:=1 to 4 do write(a[i],' '); writeln; {вывод комбинации}

a[4]:=a[4]+1; {добавление 1 в последний разряд}

for i:=4 downto 2 do { анализ и осуществление переносов}

if a[i]>3 then

begin a[i]:=1; a[i-1]:=a[i-1]+1; end;

end

end.

Этот прием можно использовать и для решения других задач данного класса.

Пример 3.Задача о расстановке ферзей.

Разработка программы решения начинается с выявления некоторых деталей.

1. 

   Определим форму представления данных задачи. С первого взгляда кажется, что доска должна представляться матрицей, а местоположение ферзей - индексами в матрице. Однако при некотором размышлении можно заменить, что доска может быть представлена вектором, в котором индекс соответствует номеру столбца доски, а значение - номеру строки.

   Рис.8.

2. Определим, что для векторного представления означает "бьет". Ферзь "бьет" другую фигуру, если она расположена на той же диагонали, вертикали или горизонтали, т.е. если

pole[ j ]=pole[ i ] или| pole[ j ]-pole[ i ] | =| j- i |

Полностью решение выглядит следующим образом:

program ex;

type p=array[1..100] of integer;

Var pole:p; I,m:integer;

function new_r(m:integer;pole:p):boolean; {функция проверки комбинации}

Var I,j:integer;

begin new_r:=true;

for i:=1 to m-1 do

for j:=i+1 to m do

if (pole[i]=pole[j]) or (abs(pole[j]-pole[i])=j-i) then

begin new_r:=false;

exit;

end;

end;

function Variant(m:integer; var pole:p):boolean; {генератор вариантов}

Var I:integer;

begin

pole[m]:=pole[m]+1; {добавление единицы в младший разряд счетчика}

for i:=m downto 2 do {обработка переносов}

if pole[i]>m then

begin pole[i]:=1;

pole[i-1]:=pole[i-1]+1;

end;

if pole[1]<=m then Variant:=true {фиксируем наличие ранее не рассмотренных}

else Variant:=false; {вариантов}

end;

begin writeln('Введите размер доски'); readln(m);

for i:=1 to m do pole[i]:=1; {исходная комбинация}

repeat

If New_r(m,pole) then

begin for i:=1 to m do write(pole[i]:2); writeln; end;

until not Variant(m,pole);

end.

Недостаток примененного метода, как уже говорилось, заключается в m^m-ой зависимости времени выполнения от значенияm.

2.2. Использование рекурсии при реализации ограниченного перебора.

Попробуем сократить количество рассматриваемых вариантов за счет как можно более раннего отбрасывания неперспективных комбинаций. На рис.9 представлена часть дерева промежуточных и завершенных вариантов.

Рис. 9.

Крестиками отмечены комбинации, уже содержащие комбинации при которых ферзи "бьют" друг друга. Генерацию таких вариантов можно не продолжать, существенно уменьшая общее количество просматриваемых вариантов. В принципе возможна не рекурсивная реализация данного подхода, но рассмотрим вариант с использованием рекурсии.

Рис. 10.

program ex;

type p=array[1..100] of integer;