1) они не повторялись;
2) количество элементов нового разбиения не было бы больше количества элементов n.
Итак, пусть мы имеем два начальных состояния: (*) и *. Для n=2 имеем только одно выходное понятие: (*)*. Для n=3 необходимо скомбинировать все известные ранее состояния с учётом условий 1)-2).
Условие 1) обеспечим из таких соображений: каждому элементу присвоить порядковый номер и комбинировать понятия так, чтобы порядковый номер следующего понятия не превосходил порядковый номер предыдущего понятия, а также следить, чтобы выполнялось условие 2). Отсюда видно, что повторений не будет, и мы перечислим все понятия.
Для реализации условия 2) необходимо каждому понятию присвоить число, которое будет показывать количество элементов этого состояния.
Также необходимо иметь некоторый массив, каждый элемент которого будет указывать на понятие, соответствующее номеру понятия в выходном понятии. Элементы этого массива будут меняться, в соответствии с перебором вариантов.
Для реализации алгоритмов был выбран язык программирования TurboPascal 7.0. В этом языке есть все необходимые средства для этих алгоритмов, и сам язык является простым для понимания. Поэтому выбор пал именно на него.
Для алгоритмов нам понадобятся понятия указателей и записей.
Запись в Pascal’е описывается так:
<имя_типа>=|<имя_переменной>:record
<список полей и их типов>
end;
Например,
Varpoint:record
x,y: integer;
color:byte
end;
Обращаются к полям записи так:
Nx:=point.x+point.y;
Point.color:=3;
Указатели описываются так:
<имя_типа>=|<имя_переменной>:^<имя типа>
Например, k:^integer– указатель на целое. Обращение к содержимому указателя: t:=k^, а запись значения в ячейку памяти, куда указывает k, выглядит так: k^:=10. Но, чтобі использовать указатели, необходимо сначала выделить память под них. Это делается с помощью команды new:
New(k);
Чтобы освободить память, если указатель уже не будет нужен, используют
Dispose(k);
Операторы присваивания, арифметических операций и циклов похожи во многих языках, поэтому их описывать не стоит.
В табл.1 представлены разбиения для n=4, генерируемые следующим алгоритмом:
program razbienie_mnozhestwa(input,output);
var i,j,k,n:byte;wper:array[1..255]of boolean;
sled,pred,blok:array[1..255]of byte;
procedure write_razbienie; {процедура, выписывающая разбиение на экран}
var
i,j:byte;
begin
j:=1; {номер первого блока}
repeat
write('( ');
for i:=j to n do if blok[i]=j then write(i, ' '); {есличислоіизблокаj, топишемэточисло}
j:=sled[j]; {следующий по номеру блок}
write(')');
until j=0;
WRITELN
end;
begin
write('input n:');
readln(n); {вводим количество элементов множества}
for i:=1 to n do begin {строимразбиение {{1, …, n}}}
blok[i]:=1;
wper[i]:=true
end;
sled[1]:=0;
write_razbienie; {выписатьразбиение}
j:=n; {активный элемент}
while j>1 do begin {задача цикла – перемещение «активного» элемента jв соседний блок – в предыдущий или последующий (в последнем случае может возникнуть необходимость создания нового блока вида {j}, а затем определение активного элемента во вновь образованном разбиении}
k:=blok[j]; {процесс переноса активного элемента; k– номер активного блока}
if wper[j] then begin {j движетсявперёд}
if sled[k]=0 then begin {k – последнийблок}
sled[k]:=j; {j – одноэлементный блок}
pred[j]:=k;
sled[j]:=0
end;
if sled[k]>j then begin {j образуетновыйблок}
pred[j]:=k; {все блоки справа от блока с номером kсодержат элементы,большие j. Отсюда следует, что jобразует новый одноэлементный блок}
sled[j]:=sled[k];
pred[sled[j]]:=j;
sled[k]:=j
end;
blok[j]:=sled[k] {переносим наш элемент в активный блок с номером k}
end
else begin {j движетсяназад}
blok[j]:=pred[k]; {помещаемj впредыдущийблок}
if k=j then if sled[k]=0 then sled[pred[k]]:=0 else begin
sled[pred[k]]:=sled[k];
pred[sled[k]]:=pred[k]
end
end;
write_razbienie;
j:=n;
while(j>1)and
((wper[j]and(blok[j]=j))or(not wper[j]and(blok[j]=1))) do begin
wper[j]:=not wper[j];
dec(j)
end
end
end.
Количество всех разбиений можно посчитать используя числа Белла и рекуррентную формулу (5).
Для реализации данной задачи на Pascal’е вводим следующие типы данных и переменных:
1)тип k – указатель на запись, поля которой: s – будет содержать понятие; p – количество элементов в понятии; next – ссылка на следующее понятие;
2) переменные f, pot типа k; f – указывает на первое понятие, то есть на простое понятие *; pot – текущее понятие;
3) массив str1 типа k – будет содержать ссылки на каждое понятие в составном понятии;
program dyscretics_optimisation(input,output);
uses crt;
const
max=12;
r:byte=0;
type
k=^el;
El=record
S: string;
P: 1..Max-1;
Next: k
End;
Label met;
Var
Pot, f, l: k;
Str1: array[1..Max]of k;
Pow: 2..Max;
K1, i, j, ll: 1..Max;
Sum: 0..Max;
Fil: text;
Ki: string[2];
begin
Readln(POW); {вводим количество простых понятий}
Str(POW, ki);
Assign(fil, ki+'.mvp'); {получившиеся понятия будем записывать в файл, содержащий в своём имени количество элементов множества и с расширением «.mvp»}
Rewrite(fil);
New(f); {выделяем память под первое понятие}
Pot:=f;
F^. S:='*'; {и инициализируем его}
F^. P:=1;
New(f^.next); {выделяем память под второе понятие}
Pot:=f^.next;
Pot^.s:='(*)'; {и также его инициализируем}
Pot^.p:=1;
Pot^.next:=nil;
for i:=2 to POW do begin {основнойциклпрограммы}
Forj:=1 toidostr1[j]:=f; {устанавливаем начальные указатели понятия, размерности і, на первое понятие}
Ifi=POWthenstr1[1]:=f^.next; {если і равно количеству элементов множества, то необходимо изменить указатель на первое подпонятие нашего понятия, так как уже отмечалось выше, понятие, состоящее только из простых подпонятий выводить не надо. Но, такие понятия оставляем для подзадач меньшей размерности, так как в комбинации с решениями других подзадач, получим уже понятие, содержащее не только простые понятия}
Whilestr1[1]<>nildobegin {пока указатель первого подпонятия не достигнет конца списка подпонятий выполнять}
New(pot^.next); { выделить память под очередное понятие}
Sum:=0; {эта переменная служит в качестве счётчика, который после следующего цикла будет содержать количество элементов в новом понятии}
K1:=1; {номер первого подпонятия. Первое подпонятие имеет всегда, если можно так выразиться, «более поздний адрес», или, точнее, все подпонятия, следующее за первым, получены раньше или одновременно с ним. Это также касается второго подпонятие относительно третьего, четвёртого и т. д., третьего относительно четвёртого, пятого и т. д., и т. д.}
Ifi=powthenpot^.next^.s:='' elsepot^.next^.s:='('; { если і равно количеству элементов множества, то нам не нужны скобки в начале (их договорились опустить)}
Whilesum<idobegin {покаколичество элементов в новом понятии меньше размерности подзадачи, выполнить}
Pot^.next^.s:=pot^.next^.s+str1[k1]^.s;{добавить в понятие подпонятие с номером k1}
Sum:=sum+str1[k1]^.p; {добавить размерность, добавленного подпонятия}
Inc(k1); {увеличить k1 на 1}
End;
If(sum>i)or(k1=2) thenbegin {если количество элементов полученного понятия больше размерности задачи или k1=2, то есть добавлено только одно понятие в подпонятие, то, чтобы избежать лишних скобок и неправильных решений выполнить}
Dispose(pot^.next); {освободить память, занимаемую этим «неправильным» понятием}
Pot^.next:=nil;{указать, что предыдущее понятие было последним}
Ifk1=2 thenbreak {если k1=2, то выйти из основного цикла программы}
End
Elsebegin
Ifi=POWthenbegin {если размерность текущей подзадачи равна размерности основной задачи, то}
Writeln(fil, pot^.next^.s); {записать понятие в файл}
Writeln(pot^.next^.s); {и вывести на экран}
Dispose(pot^.next); {освободить память, занимаемую понятием, так как понятия размерности задачи нам більше не понадобятся}
Pot^.next:=nil
End
Elsebegin {иначе инициализируем понятие до конца}
Pot:=pot^.next;
Pot^.s:=pot^.s+')'; {закрываемскобку}