Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
21 ошибка прогр... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Пример работы с... 65535
Содержание сайт... 65535
ТЕХНОЛОГИИ ДОСТ... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Создание отчето... 65535
Имитационное мо... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Реклама
Сейчас на сайте
Гостей: 21
На сайте нет зарегистрированных пользователей

Пользователей: 13,361
новичок: uehuat
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Лабораторная работа по динамическим спискам на Turbo Pascal (перемещение...
Моделирование процесса обработки заданий пакетным режимом работы с квант...
Моделирование станции технического обслуживания на GPSS + Отчет

12.5. Задачи
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 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
Рисование PopupMenu
Задача о 8ми ладьях
DragMe [Исходник ...
С. Г. Горнаков - ...
Preview
TmxOutlookBarPro
Основы программир...
Delphi. Учимся на...
Разработка клиент...
Delphi 6/7 базы д...
Генетический алго...
Использование Lis...
Animated Menus
MpegPlay
RbControls
Добавление басса ...
JanButtonsV
AntiRus
3D Октаэдр
Анекдоты с ostrie.ru

Топ загрузок
Приложение Клие... 100772
Delphi 7 Enterp... 97809
Converter AMR<-... 20260
GPSS World Stud... 17014
Borland C++Buil... 14189
Borland Delphi ... 10267
Turbo Pascal fo... 7372
Калькулятор [Ис... 5972
Visual Studio 2... 5206
Microsoft SQL S... 3661
Случайные статьи
Восходящий граммат...
Тестирование
Глава 17. Страт...
ПАММ счета Fx-Tren...
Приложения TCP/IP ...
Журналы протокола ...
Программирование с...
ClubGaminator
Как работает GZIP ...
Операции отношения...
Structure too large
Что писать в инфог...
Работа с базами да...
Обработка строк в ...
Спецификация EPON
Коллекция Charts, ...
Добавление медиафа...
Особенности игровы...
Интерфейсы USB и F...
Коньки для фигурно...
Популярные системы...
Существуют два осн...
Игровые автоматы д...
Вычисление произве...
Оконная сигнализация
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?