Навигация
Главная
Поиск
Форум
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
ТЕХНОЛОГИИ ДОСТ... 63004
Имитационное мо... 58330
Реклама
Сейчас на сайте
Гостей: 6
На сайте нет зарегистрированных пользователей

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

Моделирование работы участка термической обработки шестерен на GPSS + По...
Двунаправленный динамический список на Delphi + Блок схемы
Моделирование интернет магазина (Apache, Php, Html) на GPSS + Блок схема

Реклама



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

ПОДПИСЫВАЙСЯ на канал о программировании
Генерация k-элементных подмножеств
В комбинаторике такие подмножества называют сочетаниями из n элементов по k элементов и обозначают . Их количество выражается следующей формулой:
Генерация k-элементных подмножеств
Однако при программировании гораздо удобнее использовать следующие рекуррентные соотношения:

Объясняется это тем, что в формуле (1) числитель и знаменатель растут очень быстро, поэтому в силу особенностей компьютерной арифметики не всегда возможно точно вычислить значение Cnk, даже когда последнее не превосходит максимально представимое целое число.
При фиксированном значении n максимального значения число сочетаний достигает при k = n/2 (вернее, для четного n максимум один и он указан, а для нечетного — максимум достигается на двух соседних значениях k: [n/2] и [n/2]+1). Поэтому особенно полезной оказывается следующая оценка для четных n [4] (очевидно, что при нечетных n отличия будут минимальными), основанная на формуле Стирлинга:

Если допустить, что за время, отведенное для решения задачи, мы можем перебрать около 106 вариантов, то из формулы (3) следует, что генерацию всех сочетаний из n элементов для любого фиксированного k можно проводить для n <= 24.
Обычно генерацию всех k-элементных подмножеств проводят в лексикографическом порядке, тем более что в данном случае это не приводит ни к усложнению алгоритма, ни к увеличению его вычислительной трудоемкости. Напомним, что порядок подмножеств называется лексикографическим, если для любых двух подмножеств справедливо, что раннее должно быть сгенерировано то из них, из индексов элементов которого можно составить меньшее k-значное число в n-ричной системе счисления (или в десятичной, для n < 10). Так, для n = 6 и k = 3 сочетание из третьего, первого и пятого элемента должно быть сгенерировано раньше, чем из второго, третьего и четвертого, так как 135 < 234.
Рассмотрим рекурсивный алгоритм решения данной задачи. Идея сведения данной задачи к задаче меньшей размерности следующая. Первым элементом подмножества может быть любой элемент, начиная с первого и заканчивая (n – k + 1)-м элементом. После того, как индекс первого элемента подмножества зафиксирован, осталось выбрать k – 1 элемент из элементов с индексами, большими, чем у первого. Далее поступаем аналогично. Когда выбран последний элемент, то мы достигли конечного уровня рекурсии и выбранное подмножество можно обработать (проанализировать или распечатать). В предлагаемой ниже программе массив a содержит значения элементов исходного множества и может быть заполнен произвольным образом. В массиве p будем формировать очередное сочетание из k элементов.
const nmax = 24;
type list = array[1..nmax] of integer; var k,i,j,n,q : integer; a,p : list; procedure print(k : integer);
var i:integer; begin for j:=1 to k do write(p[j]:4); writeln end;{print}

procedure cnk(n,k : integer); procedure gen(m,L : integer); var i:integer; begin if m=0 then print(k) else for i:=L to n-m+1 do begin
p[k-m+1]:=a[i];
gen(m-1,i+1)
end
end;{gen}

begin {cnk} gen(k,1) end;{cnk} begin {main} readln(n,k); for i:=1 to n do a[i]:=i;{заполнить массив можно и по-другому}
cnk(n,k)
end.



Заметим, что собственно генерация сочетаний производится в рекурсивной подпрограмме gen. Она имеет следующие параметры: m - сколько элементов из множества нам еще осталось выбрать и L - начиная с какого элемента исходного множества, следует выбирать эти m элементов. Обратите внимание, что именно вложенная структура описания процедур cnk и gen позволяет не передавать при рекурсивных вызовах значения n и k, а из основной программы обращаться к процедуре cnk с параметрами, соответствующими постановке задачи, не вдаваясь в подробности ее решения. Такой способ будем применять и в дальнейшем.





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

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
BDEPack
DFileDeleter
RxLIB
Программирование ...
Gold Submitter II...
Dbgridpack
Система баннеро...
ICQ
Панель Наша Кнопка
GPSS World Studen...
isoCanvas (Редакт...
Х. М. Дейтел, П. ...
Заставка. Изображ...
Шаблон для новост...
начисление процен...
Изучаем Ассемблер
45 уроков по дельфи
Программирование ...
Autorunner
IPAddresseEdit

Топ загрузок
Приложение Клие... 100479
Delphi 7 Enterp... 87859
Converter AMR<-... 20082
GPSS World Stud... 13492
Borland C++Buil... 12055
Borland Delphi ... 8668
Turbo Pascal fo... 7048
Visual Studio 2... 5005
Калькулятор [Ис... 4908
FreeSMS v1.3.1 3545
Случайные статьи
Программист
2.3. СПОСОБЫ РАСПО...
Анализ результатов...
Естественный отбор...
Абстрактные классы
Что имеет маску 25...
Ввод-вывод потока
REALLOCATE (ПЕРЕРА...
Добавить объект P...
Новостройки Тюмени
Invalid @ argument
Какие делать ставк...
для проведения сов...
Прежде чем перейти...
Алгоритм шифровани...
Смена пользователя
Шаблоны классов
Архитектура Ethern...
Понижение цветовой...
Насколько она слож...
Игровые автоматы. ...
ТРАНЗАКТЫ
Работаем с файлами...
е. можно включить ...
лучший онлайн-кази...
Статистика



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


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