Книга является наиболее полным руководством по разработке эффективных ал

Глава 1. Введение в разработку алгоритмов 
43 
— Один вопрос напоследок. Если с помощью вашей программы люди могут натрени-
роваться выбирать выигрышные лотерейные билеты, то почему вы сами не пользуетесь 
ею, чтобы выигрывать в лотерею? 
— Надеюсь встретиться с Вами в ближайшее время, профессор Скиена. Благодарю за 
помощь. 
Я повесил трубку и начал обдумывать дальнейшие действия. Задача выглядела, как 
идеальный проект для какого-либо смышленого студента. После моделирования задачи 
посредством множеств и подмножеств основные компоненты решения выглядели до-
вольно просто. 
Нам было нужна возможность генерировать все подмножества 
k
номеров из потен-
циального множества 
S
.
Алгоритмы генерирования и ранжирования подмножеств 
представлены в 
разделе 14.5
. 
Нам была нужна правильная формулировка, что именно означает требование иметь 
покрывающее множество приобретенных билетов. Очевидным критерием того, что 
требование выполнено, мог быть наименьший набор билетов, включающий, по 
крайней мере, один билет, содержащий каждое из 
( )
n
l
l
-подмножеств множества 
S
, 
за которое может выдаваться приз. 
Нам нужно было отслеживать уже рассмотренные призовые комбинации. Нам нуж-
ны такие комбинации номеров билетов, чтобы покрыть как можно больше еще не 
охваченных призовых комбинаций. Текущие охваченные комбинации являются 
подмножеством всех возможных комбинаций. Структуры данных для подмножеств 
рассматриваются в 
разделе 12.5
. Наилучшим кандидатом выглядел вектор битов, 
который бы за постоянное время давал ответ, охвачена ли уже данная комбинация. 
Нужен был механизм поиска, чтобы решить, какой следующий билет покупать. Для 
небольших множеств можно было проверить все возможные подмножества комби-
наций и выбрать из них самую меньшую. Для множеств большего размера выиг-
рышные комбинации номеров билетов для покупки можно было выбирать с по- 
мощью какого-либо процесса рандомизированного поиска наподобие имитации от-
жига (см.