Можно рассматривать набор S как множество из п изначально пустых корзин
4. Можно рассматривать набор S как множество из п изначально пустых корзин. Каждый вызов randint позволяет выбрать корзину, в которую будет помещен шар. Если она уже занята, функция member вернет значение true. Задача о количестве шаров, гарантирующая отсутствие пустых корзин, называется у статистиков «задачей коллекционера» (сколько нужно собрать карточек, чтобы получить все п разных типов?); результат приблизительно равен п Inn. Когда все шары попадают в разные корзины, программа делает m проверок. Задача о количестве шаров, при котором в какой-нибудь корзине их окажется два, называется «парадоксом дней рождений» (в любой группе из 23 и более человек двое почти наверняка родились в один и тот же день года). В какой-либо из корзин окажется два шара, если шаров будет 0(у/п).
7. Чтобы вывести значения в порядке возрастания, можно поместить оператор вывода print после рекурсивного вызова или выводить значение n+1-i, а не само i.
8. Чтобы выводить различные целые числа в случайном порядке, нужно выводить их сразу после того, как они порождаются. См. также решение 1.4. Чтобы вывести числа с повторениями в порядке возрастания, нужно убрать проверку наличия чисел в наборе. Чтобы выводить числа с повторениями в случайном порядке, нужно написать тривиальную программу
for 1 = [0. m)
pn nt bi grand() % n
9. Когда Боб Флойд изучил алгоритм, основанный на наборах, его не удовлетворил тот факт, что часть порождаемых чисел отбрасывается. Поэтому он написал другой алгоритм с наборами, реализацию которого на C++ мы и приводим здесь.
void genfloyd(int m. int n)
{ set<int> S, set<int> iterator i . for (int j = n-m. j<n, j++) { int t = bigrand() % (j + 1) if (S find(t) == S endO)
S insert (t) // t нет в S el se
S insert(j). // t уже есть в S for (i - 5 begin(), i '= S end(). ++i) cout << *i << " \n " .}
В решении задачи 1 из главы 13 реализован тот же алгоритм с альтернативным интерфейсом наборов. Алгоритм Флойда был впервые опубликован в колонке «Programming Pearls» журнала Communications of the ACM в 1986 году и был вынесен в отдельную главу книги «More Programming Pearls» в 1988 году. Там же вы можете прочитать простое доказательство его правильности.
10. Первую строку мы выбираем всегда, вторую — с вероятностью 1/2, третью — с вероятностью 1/3 и так далее. К концу процесса вероятность выбора всех строк окажется одинаковой (1/п, где п — полное число строк в файле).
1 - О
пока на входе есть строки с вероятностью 1 0/++1 choice - текущая строка print choice
Опубликовал vovan666
April 17 2013 00:07:02 ·
0 Комментариев ·
3644 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
