Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Переборные задачи >> Номер 3

[Назад]    [Содержание ]    [Вперед]

  


Номер 3


  Условие: Номер 3


Задача 3. Сгенерировать все k-элементные подмножества множества A из N чисел, A={1, 2, ..., N}. Пример: N=3, k=2, подмножества {1,2}, {1,3}, {2,3}.

  Решение задачи: Номер 3


Решение задачи 3. Воспользуемся следующим алгоритмом генерации сочетаний по k элементов из множества A: В массиве B будут находиться индексы используемых на данном шаге элементов из A (общее их число k). В качестве начальной конфигурацией возьмем следующую: B[j]=j, j=1,...,k. Ищем B[j] с максимальным индексом j такое, что B[j]<n+j-k, увеличиваем это B[j] на 1, а для всех m>j полагаем B[m]=B[m-1]+1 (B[j] растут с ростом j, и мы ищем и увеличиваем на 1 такое B[j] с максимальным номером j, чтобы при заполнении возрастающими значениями элементов массива B[m], m>j, последний элемент B[k] не превосходил бы n). Если такого B[j] не существует, то генерация сочетаний для данного k закончена.

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017