Как будут записываться в программе элементы множества (тип элемент множества)?
В каком порядке мы будем перебирать их (инструкция x:=следующий за x;)?
Рассмотрим пример. Подсчитать число счастливых билетов, т. е. таких наборов из шести цифр А,B,C,D,E,F, что A+B+C=D+E+F. Будем решать задачу путем перебора всех комбинаций из шести цифр (это решение далеко не самое эффективное). Таким образом, элемент множества задается последовательно из шести цифр, каждая из которых принимает значения от 0 до 9. Для хранения этой последовательности используем шесть отдельных переменных. В данном случае можно, не следуя буквально введенным выше схемам, организовать перебор с помощью шести вложенных циклов FOR:
Program Happy_Ticket ;
Var A,B,C,D,E,F,k :Integer;{ k – число найденных счастливых билетов}
Begin
k:=0;
For A:=0 To 9 Do
For B:=0 To 9 Do
For C:=0 To 9 Do
For D:=0 To 9 Do
For E:=0 To 9 Do
For F:=0 To 9 Do
If A+B+C = D+E+F Then k:=k+1;
Writeln(‘ЧИСЛО СЧАСТЛИВЫХ БИЛЕТОВ=’,k);
End.
Кстати сказать, счастливых билетов 55252 (если считать и 000000), что составляет примерно 1/18 общего числа билетов.
7.2. Последовательности.
Важно научиться строить алгоритмы перебора различных комбинаторных объектов - последовательностей, перестановок, подмножеств и т.д.
Схема перебора всегда будет одинакова:
во-первых, надо установить порядок на элементах, подлежащих перечислению (в частности, определить, какой из них будет первым, а какой последним);
во-вторых, научиться переходить от произвольного элемента к непосредственно следующему за ним (т.е. для заданного элемента x1 строить такой элемент x2, что x1<x2 и между x1 и x2 нет других элементов).
Hаиболее естественным способом упорядочения составных объектов является лексикографический порядок, принятый в любом словаре (сначала сравниваются первые буквы слов, потом вторые и т.д.) - именно его мы и будем чаще всего использовать. А вот процедуру получения следующего элемента придется каждый раз изобретать заново. Пока запишем схему перебора в таком виде:
x:=First;
While x<>Last Do Next(x);
где First - первый элемент; Last - последний элемент; Next - процедура получения следующего элемента.
Hапечатать все последовательности длины N из чисел 1,2,...,M.
First = (1,1,...,1), Last = (M,M,...,M).
Всего таких последовательностей будет MN. Чтобы понять. как должна действовать процедура Next, начнем с примеров.
Пусть N=4, M=3. Тогда:
Next(1,1,1,1) -> (1,1,1,2) Next(1,1,1,3) -> (1,1,2,1) Next(3,1,3,3) -> (3,2,1,1)
Теперь можно написать общую процедуру Next:
Procedure Next;
Begin
{ найти i: X[i]<M, X[i+1]=M,..., X[N]=M };
X[i]:=X[i]+1;
X[i+1]:=...:=X[N]:=1
End;
Если такого i найти не удается, то следующей последовательности нет - мы добрались до последней (M,M,...,M). Заметим также, что если бы членами последовательности были числа не от 1 до M, а от 0 до M-1, то переход к следующей означал бы прибавление 1 в M-ичной системе счисления. Полная программа выглядит так:
Program Posled;
Const N=4; M=3;
Var x :Array[1..N] Of Byte; i :Byte;
Procedure PrintX;
Var i :Byte;
Begin
For i:=1 To N Do Write(X[i]);
Writeln;
End;
Function Next :Boolean;
Var i :Byte;
Begin
i:=N;
While (i>0) And (x[ i ] = M) Do Begin
x[ i ]:=1;
Dec(i)
End;
If i>0 Then Begin Inc(x[ i ]); Next:=True; End
Else Next:=False;
End;
Begin
For i:=1 To N Do X[ i ]:=1;
PrintX;
While Next Do PrintX;
End.
Опишем рекурсивную процедуру GPosl(k), генерирующую все последовательности длины N из чисел 1,...,M, у которых фиксировано начало X[1],X[2],...,X[k]. Понятно, что при k=N мы имеем тривиальное решение: есть только одна такая последовательность - это она сама. При k<N будем сводить задачу к k+1:
Procedure GPosl (k :Byte);
Var i, j :Byte;
Begin
If k=N Then PrintX(N)
Else For i:=1 To M Do Begin
X[k+1]:=i;
GPosl(k+1);
End;
End;
Вызов: …. GPosl(0); ….