Табл.1.
Последовательность разбиений множества {1,2,3,4}
Опишем
теперь алгоритм решения задачи о перечислении всех понятий.
Рекурсивный алгоритм использовать нельзя, так как все решения
подзадачи меньшей размерности необходимо скомбинировать со всеми решениями
подзадачи оставшейся размерности. Поэтому, будем просто перебирать все
варианты.
Идея такова: сохраняем все разбиения меньшей размерности и
комбинируем их так, чтобы
1)
они не повторялись;
2)
количество элементов
нового разбиения не было бы больше количества элементов n.
Итак, пусть мы имеем два начальных состояния:
(*) и *. Для n=2 имеем только одно выходное понятие: (*)*. Для n=3
необходимо скомбинировать все известные ранее состояния с учётом условий 1)-2).
Условие 1) обеспечим из таких соображений:
каждому элементу присвоить порядковый номер и комбинировать понятия так, чтобы
порядковый номер следующего понятия не превосходил порядковый номер предыдущего
понятия, а также следить, чтобы выполнялось условие 2). Отсюда видно, что
повторений не будет, и мы перечислим все понятия.
Для реализации условия 2) необходимо каждому понятию присвоить
число, которое будет показывать количество элементов этого состояния.
Также необходимо иметь некоторый массив, каждый элемент
которого будет указывать на понятие, соответствующее номеру понятия в выходном
понятии. Элементы этого массива будут меняться, в соответствии с перебором
вариантов.
Язык программирования
Для реализации алгоритмов был выбран язык программирования Turbo Pascal
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: