Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Пример работы с... 65535
Содержание сайт... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Создание отчето... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Модуль Forms 65535
ТЕХНОЛОГИИ ДОСТ... 62908
Имитационное мо... 58289
Реклама
Сейчас на сайте
Гостей: 6
На сайте нет зарегистрированных пользователей

Пользователей: 13,091
новичок: avegraf
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Обратное размещение элементов ЭВС на Delphi + Пояснительная записка
Диплом - база данных поставщиков на Delphi (MS Sql Server)+ Пояснительна...
моделирование процесса поступления заявок в ЭВМ на GPSS + Пояснительная ...

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
Генерация всех подмножеств данного множества
При решении задач чаще всего заранее неизвестно, сколько именно элементов исходного множества должно входить в искомое подмножество, то есть необходим перебор всех подмножеств. Однако, если требуется найти минимальное подмножество, то есть состоящее как можно из меньшего числа элементов (или максимальное подмножество), то эффективнее всего организовать перебор так, чтобы сначала проверялись все подмножества, состоящие из одного элемента, затем из двух, трех и т. д. элементов (для максимального подмножества — в обратном порядке). В этом случае, первое же подмножество, удовлетворяющее условию задачи и будет искомым и дальнейший перебор следует прекратить. Для реализации такого перебора можно воспользоваться, например, процедурой cnk, описанной в предыдущем разделе. Введем в нее еще один параметр: логическую переменную flag, которая будет обозначать, удовлетворяет текущее сочетание элементов условию задачи или нет. При получении очередного сочетания вместо его печати обратимся к процедуре его проверки check, которая и будет определять значение флага. Тогда начало процедуры gen следует переписать так:
procedure gen(m,L:integer);
var i:integer;
begin
if m=0 then
begin
check(p,k,flag);
if flag then exit
end
else ...



Далее процедура дословно совпадает с предыдущей версией. В основной же программе единственное обращение к данной процедуре следует заменить следующим фрагментом:
k:=0;
flag:=false;
repeat
k:=k+1;
cnk(n,1,flag)
until flag or (k=n);
if flag then print(k)
else writeln('no solution');



Очевидно также, что в основной программе запрос значения переменной k теперь не производится.
Существует также альтернативный подход к перебору всех подмножеств того или иного множества. Каждое подмножество можно охарактеризовать, указав относительно каждого элемента исходного множества, принадлежит оно данному подмножеству или нет. Сделать это можно, поставив в соответствие каждому элементу множества 0 или 1. То есть каждому подмножеству соответствует n-значное число в двоичной системе счисления (строго говоря, так как числа могут начинаться с произвольного количества нулей, которые значащими цифрами не считаются, то следует заметить, что в соответствие ставятся n- или менее -значные числа). Отсюда следует, что полный перебор всех подмножеств данного множества соответствует перебору всех чисел в двоичной системе счисления от
Генерация всех подмножеств данного множества
Теперь легко подсчитать и количество различных подмножеств данного множества. Оно равно 2^n – 1 (или 2^n, с учетом пустого множества). Таким образом, сопоставляя два способа перебора всех подмножеств данного множества, мы получили следующую формулу:

То есть, в рамках сделанной выше оценки на количество допустимых вариантов в переборе, мы можем рассмотреть все подмножества исходного множества только при n <= 20.
Прежде, чем перейти к рассмотрению программ, соответствующих второму способу перебора, укажем, когда применение этих программ целесообразно. Во-первых, данные программы легко использовать, когда необходимо в любом случае перебрать все подмножества данного множества (например, требуется найти все решения удовлетворяющие тому или иному условию). Во-вторых, когда с точки зрения условия задачи не имеет значения, сколько именно элементов должно входить в искомое подмножество. На примере такой задачи мы и напишем программу генерации всех подмножеств исходного множества в лексикографическом порядке. Задача взята из книги [5].
Условие. Дан целочисленный массив a[1..N] (N <= 20) и число M. Найти подмножество элементов массива a[i1], a[i2], ...a[ik] такое, что 1 <= i1 < i2 < i3 < ... < ik <= N и a[i1] + a[i2] + ... + a[ik] = M.
Решение. В качестве решения приведем процедуру генерации всех подмножеств, которые можно составить из элементов массива и функцию проверки конкретного подмножества на соответствие условию задачи.
function check(j:longint):boolean;
var k:integer; s:longint;
begin
s:=0;
for k:=1 to n do
if ((j shr (k-1))and 1)=1 {данное условие означает, что в
k-й справа позиции числа j, в 2-й системе, стоит 1}
then s:=s+a[k];
if s=m then
begin
for k:=1 to n do
if ((j shr (k-1))and 1)=1 then write(a[k]:4);
writeln
end
end;

procedure subsets(n:integer);
var q,j:longint;
begin
q:=1 shl n; {таким образом мы помещаем в q число 2^n}
for j:=1 to q-1 do {цикл по всем подмножествам}
if check(j) then exit
end;



Заметим, что если все элементы в массиве положительные, то, изменив порядок рассмотрения подмножеств, решение приведенной выше задачи можно сделать более эффективным. Так, если сумма элементов какого-либо подмножества уже больше, чем M, то рассматривать подмножества, включающие его в себя уже не имеет смысла. Пересчет же сумм можно оптимизировать, если каждое следующее сгенерированное подмножество будет отличаться от предыдущего не более, чем на один элемент (такой способ перечисления подмножеств показан в [2]). Приведенная же программа черезвычайно проста, но обладает одним недостатком: мы не можем ни в каком случае с ее помощью перебирать все подмножества множеств, состоящих из более, чем 30 элементов, что обусловлено максимальным числом битов, отводимых на представление целых чисел в Турбо Паскале (32 бита). Но, как уже было сказано выше, на самом деле, перебор всех подмножеств у множеств большей размерности вряд ли возможен за время, отведенное для решения той или иной задачи.





Опубликовал Kest March 06 2010 19:45:07 · 0 Комментариев · 15368 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
Программа "AutoRu...
JanComp
BIOS
Пример клиента ФТ...
Tenis [Исходник н...
Prolog Interprete...
Ранги для форума
Blib [Исходник на...
FormShape [Исходн...
ADVstatusbar
Delphi Быстрый Ст...
Rss Parser
Pirc
Фильтры изображений
Форма в форме
Crypt32
Рисование PopupMenu
Delphi Russian Kn...
ScrollCredit
XPmenu

Топ загрузок
Приложение Клие... 100476
Delphi 7 Enterp... 87806
Converter AMR<-... 20082
GPSS World Stud... 13396
Borland C++Buil... 12041
Borland Delphi ... 8665
Turbo Pascal fo... 7048
Visual Studio 2... 5005
Калькулятор [Ис... 4894
FreeSMS v1.3.1 3545
Случайные статьи
FUNCTION (ФУНКЦИЯ)
Основная особеннос...
Более того, для ко...
Множественные инте...
Обзор уязвимостей ...
Duplicate Identifier
Про лудоманию
Таблицы (spreadshe...
Требование синхрон...
Руководство для ра...
Процедура LineTo -...
Сохранение и загру...
Directory
Алгоритм нахождени...
Сортировка массива
Стандартные числов...
Теперь давайте пос...
Флуоресцентный све...
соединении
Адаптация встроенн...
• Упрощается перех...
Анализ общей линей...
Интересный, но пот...
Описание абстрактн...
События - блокирую...
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?