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 Комментариев ·
3187 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
