7.3. Порождение комбинаторных объектов, перебор

Рекурсивные программы являются удобным способом порождения комбинаторных объектов заданного вида. Мы решим заново несколько задач соответствующей главы.

7.3.1. Написать программу, которая печатает по одному разу все последовательности длины n, составленные из чисел 1..k (их количество равно k в степени n).

Решение. Программа будет оперировать с массивом a[1]..a[n] и числом t. Рекурсивная процедура generate печатает все последовательности, начинающиеся на a[1]..a[t]; после ее окончания t и a[1]..a[t] имеют то же значение, что и в начале:
procedure generate;
| var i,j : integer;
begin
| if t = n then begin
| | for i:=1 to n do begin
| | | write(a[i]);
| | end;
| | writeln;
| end else begin {t < n}
| | for j:=1 to k do begin
| | | t:=t+1;
| | | a[t]:=j;
| | | generate;
| | | t:=t-1;
| | end;
| end;
end;

Основная программа теперь состоит из двух операторов:
t:=0; generate;

Замечание. Команды t:=t+1 и t:-t-1 для экономии можно вынести из цикла for.

7.3.2. Написать программу, которая печатала бы все перестановки чисел 1..n по одному разу.

Решение. Программа оперирует с массивом a[1]..a[n], в котором хранится перестановка чисел 1..n. Рекурсивная процедура generate в такой ситуации печатает все перестановки, которые на первых t позициях совпадают с перестановкой a; по выходе из нее переменные t и a имеют те же значения, что и до входа. Основная программа такова:
for i:=1 to n do begin a[i]:=i; end;
t:=0;
generate;

вот описание процедуры:
procedure generate;
| var i,j : integer;
begin
| if t = n then begin
| | for i:=1 to n do begin
| | | write(a[i]);
| | end;
| | writeln;
| end else begin {t < n}
| | for j:=t+1 to n do begin
| | | поменять местами a[t+1] и a[j]
| | | t:=t+1;
| | | generate;
| | | t:=t-1;
| | | поменять местами a[t+1] и a[j]
| | end;
| end;
end;

7.3.3. Напечатать все возрастающие последовательности длины k, элементами которых являются натуральные числа от 1 до n. (Предполагается, что k не превосходит n - иначе таких последовательностей не существует.)

Решение. Программа оперирует с массивом a[1]..a[k] и целой переменной t. Предполагая, что a[1]..a[t] - возрастающая последовательность чисел натуральных чисел из отрезка 1..n, рекурсивно определенная процедура generate печатает все ее возрастающие продолжения длины k. (При этом t и a[1]..a[t] в конце такие же, как в начале.)
procedure generate;
| var i: integer;
begin
| if t = k then begin
| | печатать a[1]..a[k]
| end else begin
| | t:=t+1;
| | for i:=a[t-1]+1 to t-k+n do begin
| | | a[t]:=i;
| | | generate;
| | end;
| | t:=t-1;
| end;
end;

Замечание. Цикл for мог бы иметь верхней границей n (вместо t-k+n). Наш вариант экономит часть работы, учитывая тот факт, что предпоследний (k-1-ый) член не может превосходить n-1, k-2-ой член не может превосходить n-2 и т.п.

Основная программа теперь выглядит так:
t:=1;
for j:=1 to 1-k+n do begin
| a[1]:=j;
| generate;
end;

Можно было бы добавить к массиву a слева фиктивный элемент a[0]=0, положить t=0 и ограничиться единственным вызовом процедуры generate.

7.3.4. Перечислить все представления положительного целого числа n в виде суммы последовательности невозрастающих целых положительных слагаемых.

Решение. Программа оперирует с массивом a[1..n] (максимальное число слагаемых равно n) и с целой переменной t. Предполагая, что a[1],...,a[t] - невозрастающая последовательность целых чисел, сумма которых не превосходит n, процедура generate печатает все представления требуемого вида, продолжающие эту последовательность. Для экономии вычислений сумма a[1]+...+a[t] хранится в специальной переменной s.
procedure generate;
| var i: integer;
begin
| if s = n then begin
| | печатать последовательность a[1]..a[t]
| end else begin
| | for i:=1 to min(a[t], n-s) do begin
| | | t:=t+1;
| | | a[t]:=i;
| | | s:=s+i;
| | | generate;
| | | s:=s-i;
| | | t:=t-1;
| | end;
| end;
end;

Основная программа при этом может быть такой:
t:=1;
for j:=1 to n do begin
| a[1]:=j
| s:=j;
| generate;
end;

Замечание. Можно немного сэконмить, вынеся операции увеличения и уменьшения t из цикла, а также не возвращая s каждый раз к исходному значению (увеличивая его на 1 и возвращая к исходному значению в конце). Кроме того, добавив фиктивный элемент a[0]=n, можно упростить основную программу:
t:=0; s:=0; a[0]:=n; generate;

7.3.5. Написать рекурсивную программу обхода дерева (используя те же команды и проверки, что и в главе про обход дерева).

Решение. Процедура обработать_над обрабатывает все листья над текущей вершиной и заканчивает работу в той же вершине, что и начала. Вот ее рекурсивное описание:
procedure обработать_над;
begin
| if есть_сверху then begin
| | вверх_налево;
| | обработать_над;
| | while есть_справа do begin
| | | вправо;
| | | обработать_над;
| | end;
| | вниз;
| end else begin
| | обработать;
| end;
end;

Другие записи

10.06.2016. 7.1. Примеры рекурсивных программ.
   При анализе рекурсивной программы возникает, как обычно, два вопроса: (а) почему программа заканчивает работу? (б) почему она работает правильно, если заканчивает работу?…
10.06.2016. 7.4. Другие применения рекурсии
Топологическая сортировка. Представим себе n чиновников, каждый из которых выдает справки определенного вида. Мы хотим получить все эти справки, соблюдая установленные ограничения: у каждого чиновника…