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

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


$\scriptstyle{\blacktriangleright}$ 7.3.1. Написать программу, которая печатает по одному разу все последовательности длины n, составленные из чисел ${\hbox{\tt 1}}\ldots{\hbox{\tt k}}$ (их количество равно ${\hbox{\tt k}}^{{\hbox{\tt n}}}$).

 

Решение. Программа будет оперировать с массивом \begin{displaymath} {\hbox{\tt a[1]}}\ldots{\hbox{\tt a[n]}}\end{displaymath}и числом t. Рекурсивная процедура generate печатает все последовательности, начинающиеся на ${\hbox{\tt a[1]}}\ldots{\hbox{\tt a[t]}}$; после ее окончания t и ${\hbox{\tt a[1]}}\ldots{\hbox{\tt 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.


$\scriptstyle{\blacktriangleright}$ 7.3.2. Написать программу, которая печатала бы все перестановки чисел ${\hbox{\tt 1}}\ldots{\hbox{\tt n}}$ по одному разу.

 

Решение. Программа оперирует с массивом ${\hbox{\tt a[1]}}\ldots{\hbox{\tt a[n]}}$, в котором хранится перестановка чисел ${\hbox{\tt 1}}\ldots{\hbox{\tt 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;`


$\scriptstyle{\blacktriangleright}$ 7.3.3. Напечатать все возрастающие последовательности длины k, элементами которых являются натуральные числа от 1 до n. (Предполагается, что ${\hbox{\tt k}}\leqslant{\hbox{\tt n}}$, иначе таких последовательностей не существует.)

 

Решение. Программа оперирует с массивом ${\hbox{\tt a[1]}}\ldots{\hbox{\tt a[k]}}$ и целой переменной t. Предполагая, что ${\hbox{\tt a[1]}}\ldots{\hbox{\tt a[t]}}$ -- возрастающая последовательность натуральных чисел из отрезка ${\hbox{\tt 1}}\ldots{\hbox{\tt n}}$, рекурсивно определенная процедура generate печатает все ее возрастающие продолжения длины k. (При этом t и ${\hbox{\tt a[1]}}\ldots{\hbox{\tt 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 (вместо ${\hbox{\tt t}}-{\hbox{\tt k}}+{\hbox{\tt n}}$). Наш вариант экономит часть работы, учитывая тот факт, что предпоследний (${\hbox{\tt k-1}}$-ый) член не может превосходить ${\hbox{\tt n-1}}$, ${\hbox{\tt k-2}}$-ой член не может превосходить ${\hbox{\tt n-2}}$ и т. п.

Основная программа теперь выглядит так: 

        t:=1;
        for j:=1 to 1-k+n do begin
        | a[1]:=j;
        | generate;
        end;
Можно было бы добавить к массиву a слева фиктивный элемент ${\hbox{\tt a[0]}}={\hbox{\tt 0}}$, положить ${\hbox{\tt t}}={\hbox{\tt 0}}$ и ограничиться единственным вызовом процедуры generate.$\scriptstyle\blacktriangleleft$


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

 

Решение. Программа оперирует с массивом a[1..n] (максимальное число слагаемых равно n) и с целой переменной t. Предполагая, что ${\hbox{\tt a[1]}}\ldots{\hbox{\tt a[t]}}$-невозрастающая последовательность целых чисел, сумма которых не превосходит n, процедура generate печатает все представления требуемого вида, продолжающие эту последовательность. Для экономии вычислений сумма ${\hbox{\tt a[1]}}+\ldots+{\hbox{\tt 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;`

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


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

   

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


pvv
1/8/1999