Вторник, 24.11.2020, 12:44
Информатика и ИКТ
Приветствую Вас Гость | RSS
Главная Регистрация Вход
Меню сайта

Yandex_tech

Хабр-news

mail_news

Rambler

Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0

oszone.net

IT-N-образование

Главная » 2020 » Октябрь » 30 » Рекурсия в программировании (язык C). Статья 8 (генерация подмножеств)
19:46
Рекурсия в программировании (язык C). Статья 8 (генерация подмножеств)

Рекурсия в программировании (язык C). Статья 8 (генерация подмножеств)

Данная статья относится к разделу моего канала о рекурсивных алгоритмах. Среди них особенно интересны (по-крайней мере для меня) задачки из комбинаторики. Ранее мы разобрали: генерацию перестановок, генерацию размещений, генерацию сочетаний. Сегодня разберем алгоритм генерации всех подмножеств множества. Если количество элементов во множестве N, то количество всех подмножеств множества равно 2 в степени N, если подмножеством считать и пустое множество. Например, множество состоит из двух элементов (1 и 2). Подмножества: {пустое}, {1}, {2}, {1,2}, т.е. 4, что как раз равно 2 в степени 2. Поскольку множество порядка не имеет, то легко понять, что генерацию можно свести к генерации сочетаний из N по 1, из N по 2, и т.д. до сочетаний из N по N.

Поскольку алгоритм для количества сочетаний ранее был нами показан, то программа по генерации подмножеств в сущности сведется к программе по генерации количества сочетаний (см. main220.c). Цикл вида for(g=1, g<=n; g++) как раз и перебирает значения для генерации сочетаний. В программе также ко всем множествам добавляется пустое множество, которое также, согласно математике, является подмножеством любого множества.

Просмотров: 12 | Добавил: niko | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Поиск

Календарь
«  Октябрь 2020  »
ПнВтСрЧтПтСбВс
   1234
567891011
12131415161718
19202122232425
262728293031

Форма входа

nixp.ru

OpenNet

Новые программы

SLO.ru

Погода
Яндекс.Погода

Друзья сайта
  • Официальный блог
  • Сообщество uCoz
  • FAQ по системе
  • Инструкции для uCoz

  • Архив записей

    Copyright MyCorp © 2020