Как только мы выяснили детали задачи, которую предстояло решить, я побежал за томом «Получисленных алгоритмов» Кнута (иметь дубликаты всех трех томов Кнута дома и на работе стоит затраченных денег). Поскольку за некоторое время до того я изучил эту книгу весьма внимательно, мне смутно припоминались алгоритмы для решения подобных задач. Потратив несколько минут на изучение нескольких подходящих алгоритмов решения задачи, я понял, что алгоритм S в разделе 3.4.2 был идеальным для решения моей задачи.
В алгоритме последовательно рассматривается каждое из чисел 0, 1, 2,п-1, и каждое из них может быть выбрано, если оно случайным образом пройдет некоторую проверку. Последовательным перебором чисел мы гарантируем, что результат окажется отсортирован.
Чтобы понять критерий отбора, рассмотрим пример с m = 2 и п = 5. Мы выбираем первое число 0 с вероятностью 2/5. Программно это реализуется следующим оператором:
if (bigrand() % 5) < 2
К сожалению, мы не можем установить ту же вероятность для числа 1, потому что в этом случае мы можем и не получить 2 числа из пяти (а можем и получить). Поэтому мы несколько изменим ситуацию, установив для единицы вероятность выбора 1 /4, если 0 был выбран, и 2/4, если 0 не был выбран. В общем, чтобы получить s элементов из г оставшихся, мы будем выбирать очередной элемент с вероятностью s/r. Вот программа на псевдокоде:
select = m remaining = n for i = [0. n)
if (bigrand() % remaining) < select print i select - - remaini ng - -
Пока m <= n программа всегда выбирает ровно m чисел. Большее количество выбрано быть не может, поскольку вероятность выбора очередного элемента становится нулевой, как только m чисел уже набрано. Меньше их тоже оказаться не может, потому что когда отношение требуемых к оставшимся становится равным
1, все оставшиеся числа однозначно проходят тест. Оператор for гарантирует, что числа будут выводиться в нужном порядке. Моего описания вам должно быть до- статочно, чтобы поверить в равновероятность выбора любого набора чисел. Кнут доказывает это с помощью теории вероятностей.
Второй том Кнута очень облегчил мне задачу. Даже вместе с заголовком, вводом, выводом, проверкой ограничений и тому подобное, конечный вариант программы занимал всего 13 строк на языке BASIC. Он был готов спустя полчаса после постановки задачи и использовался много лет без каких-либо проблем. Вот эта программа на языке C++:
Листинг 12.1 Программа 1
void genknuth(int m. int n)
{ for (int i = 0. i < n. i ++)
/* выбор m из оставшихся n - i */ if ((bi grand() % (n-i)) < m) { cout << i << " \n": m- - ;}}Программе требовалось всего несколько десятков байт памяти, и она была быстрой как молния (с учетом задач фирмы). Однако этот код может показаться медленным, если п будет слишком велико. Получение нескольких случайных 32-раз- рядных целых чисел (n « 232) требует на моем компьютере около 12 минут. Задачка на предварительные оценки: сколько времени потребуется на получение одного 48- или 64-разрядного целого с помощью этого алгоритма?
Опубликовал vovan666
April 17 2013 00:02:55 ·
0 Комментариев ·
2476 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
