4.4. Порождение подмножеств множества

Порождение подмножеств множества эквивалентно порождению -разрядных двоичных наборов принадлежащих подмножеству, если и только если разряд равен единице. Таким образом, задача порождения всех подмножеств множества сводится к задаче порождения всех возможных двоичных последовательностей длины Очевидно, что наиболее прямым способом порождения всех двоичных наборов длины является счет в системе счисления с основанием 2, как показано в алгоритме 4.7.

Перевод этого алгоритма на язык подмножеств множества осуществляется согласно алгоритму 4.8, где добавлен фиктивный элемент

Алгоритм 4.7. Счет в системе счисления с основанием 2 для порождения всех —разрядных наборов

(см. скан)

Алгоритм 4.8. Порождение подмножеств счетом в двоичной системе счисления

(см. скан)

Задача «Счастливый билет». Дано произвольных цифр: где и произвольное целое число Написать программу, которая расставляла бы между каждой парой цифр записанных именно в таком порядке, знаки -так, чтобы значением получившегося выражения было число Например, если соответственно равны то подойдет следующая расстановка знаков: Если требуемая расстановка невозможна, то сообщить об этом.

Исходные данные вводятся из текстового файла, имеющего следующую структуру.

Первая строка — целое число

Вторая строка — целое число

Третья строка — цифры через пробелы.

Результаты расчетов сохранить в текстовом файле.

Пример файла исходных данных:

Пример файла выходных данных:

Время счета .

Ясно, что для решения данной задачи достаточно выполнить полный перебор всех возможных вариантов расстановки знаков между каждой парой цифр и выбрать те расстановки знаков которые удовлетворяют условию равенства суммы величине Всего позиций для расстановки равно значит для полного перебора необходимо проверить двоичных наборов, если будет соответствовать 1, а

Программа решения задачи «счастливый билет» представлена алгоритмом 4.9. Процедура (подмножество) этой программы реализует рассмотренный выше алгоритм 4.7 счета в системе счисления с основанием 2 для порождения всех -разрядных наборов. Порожденные двоичные наборы используются в процедуре (сумма) для формирования суммы, соответствующей данному набору знаков где соответствует 1, а

Алгоритм 4.9. Программа на Pascal'е решения задачи «Счастливый билет»

(см. скан)

(см. скан)