1. Библиотечная функция языка С rand() в типичной реализации возвращает 15 случайных битов. Используйте ее для реализации функции bigrand(), возвращающей по меньшей мере 30 случайных битов, и функции randint(l, и), возвращающей случайное целое в диапазоне [I, и].
2. В разделе 12.1 было отмечено, что вероятность выбора всех т-элементных наборов должна быть одинаковой. Это более сильное требование, чем просто требование выбора любого целого с вероятностью m/n. Опишите алгоритм, в котором вероятность выбора всех элементов одинакова, но при этом вероятности выбора разных наборов элементов различны.
3. Покажите, что если m < п/2, то ожидаемое количество проверок на принадлежность набору до нахождения отсутствующего элемента в алгоритме, использующем наборы, меньше двух.
4. Попытка подсчета количества проверок на принадлежность в программе с наборами порождает много новых интересных задач на комбинаторику и теорию вероятностей. Сколько проверок в среднем делается в зависимости от чисел m и п? Сколько их будет сделано, если m = п? В какой ситуации наиболее вероятно проведение более m проверок?
5. В этой главе приведено несколько алгоритмов решения одной задачи. Их реализации можно найти на сайте этой книги. Измерьте производительность этих алгоритмов в своей системе и сделайте выводы об условиях применимости того или иного алгоритма (ограничения на время выполнения, объем памяти и другие).
6. Я предлагал студентам задачу о формировании упорядоченных подмножеств в рамках курса теории алгоритмов, причем делал это два раза. Первый — когда они еще не изучали поиск и сортировку. Студенты должны были написать программу для m = 20 и п = 400. Главным критерием оценки была ясность и краткость кода — время его работы роли не играло. После курса сортировки и поиска им нужно было решить ту же задачу еще раз, но теперь m = 5 ООО ООО, a n = 1 ООО ООО ООО, причем оценка зависела в первую очередь от времени работы программы.
7. [V. A. Vyssotsky] Алгоритмы генерации комбинаторных объектов чаще всего выгодно выражать через рекурсивные функции. Алгоритм Кнута может быть записан следующим образом:
void randselect(m. n)
предусловие: 0 <= m <= n
постусловие: m неповторяющихся чисел от 0 до п-1 выводятся в порядке убывания
i f гл > О
if (bigrand() % n) < m print n-1
randselect(m-1. n-1) el se
randselect(m. n-1)
Эта программа выводит числа в порядке убывания. Как можно сделать, чтобы они выводились в порядке возрастания? Докажите правильность получившейся программы. Как можно использовать основную рекурсивную структуру программы для получения всех m-элементных подмножеств диапазона О..п-l?
8. Как бы вы реализовали случайный выбор m целых чисел из диапазона 0. .п-1, если нужно было бы их выводить в случайном порядке? Как бы вы получали отсортированный список, если бы было допустимо присутствие в нем повторяющихся чисел? Что, если бы нужно было одновременно получить случайный порядок элементов, и при этом допускалось бы их повторение?
9. [R, W. Floyd] Когда m близко к п, алгоритмы, основанные на использовании наборов, генерируют большое количество чисел, которые затем отбрасываются, поскольку уже имеются в наборе. Можете ли вы придумать алгоритм, использующий только m случайных чисел, даже в худшем случае?
10. Как можно выбрать один из п объектов случайным образом, если объекты предъявляются последовательно, но их количество п заранее неизвестно? Поставлю задачу конкретнее: нужно напечатать одну случайную строку текстового файла, прочитав его всего один раз, причем количество строк заранее неизвестно, а вероятность выбора должна быть одинакова для всех строк текста.
11. [М. I. Shamos] Лотерея проводится с помощью карты с шестнадцатью точками, под которыми случайным образом распределены числа 1. .16. Игрок стирает точки, открывая скрытые под ними числа. Если открывается число 3, карта проигрывает. Если открываются числа 1 и 2 (в любом порядке), карта выигрывает. Опишите, каким образом вы могли бы с помощью компьютера вычислить вероятность выигрыша при случайном выборе точек. На решение задачи вам отводится 1 час компьютерного времени.
12. Моя первая версия одной из программ этой главы содержала ошибку, приводившую к ее досрочному завершению при m ** 0. Для прочих значений m она выводила числа, казавшиеся случайными, но на деле таковыми не являвшиеся. Как бы вы проверили программу, выводящую некоторый набор случайных чисел, на случайность результата?
12.6. Дополнительная литература
Том 2 монографии Д. Кнута «Искусство программирования для ЭВМ» называется «Получисленные алгоритмы». Глава 3 (в первой половине книги) посвящена случайным числам, а глава 4 (во второй половине книги) — арифметике. Раздел 3.4.2 «Случайная выборка и перемешивание» имеет непосредственное отношение к предмету обсуждения данной главы. Если вам понадобится написать собственный генератор случайных чисел или функции для работы со сложной арифметикой, — эта книга окажется незаменимой.
Поиск
Задача поиска встречается во множестве приложений. Компилятор ищет имя переменной, чтобы определить ее тип и адрес. Программа проверки правописания должна найти слово в словаре, чтобы проверить его правильность. Программа, об* служивающая телефонный справочник, ищет в нем имя абонента, чтобы определить его номер. Сервер имен доменов Интернет ищет имя запрашиваемого узла в своей базе, определяя по этому имени IP-адрес. В этих примерах, как и во множестве других, приходится осуществлять поиск в наборе данных для получения информации, содержащейся в одном из элементов набора.
В этой главе подробно рассматривается одна из задач, связанных с поиском, а именно: каким образом следует хранить в памяти набор целых чисел без каких- либо дополнительных, связанных с этими числами, данных? Хотя эта проблема кажется не слишком значительной, ход ее решения во многом аналогичен решению задачи реализации произвольного типа данных. Мы начнем с точной формулировки задачи и с ее помощью исследуем наиболее общие способы представления множеств данных.
Опубликовал vovan666
April 17 2013 00:03:11 ·
0 Комментариев ·
3163 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.