Форум программистов, компьютерный форум CyberForum.ru

Кормен. Задача. Генератор случайных чисел - C++

Восстановить пароль Регистрация
 
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,340
08.08.2013, 10:53     Кормен. Задача. Генератор случайных чисел #1
Есть задача из Кормена, но я не знаю как к ней подступиться, расчитываю на помощь.

Есть генератор случайных чисел BiasedRandom который выдает 0 с вероятностью p, и 1 - с вероятностью 1 - p. Значение p не известно. Нужно сформулировать алгоритм, который будет использовать BiasedRandom и выдавать 0 либо 1 с вероятностью 1/2.

Как такое нужно делать? Мне только пришла в голову идея с накоплением статистики, чтобы с каждым вызовом все точнее вычислять число p и на основе это выдавать значения с нужной вероятностью. Но мне это кажется неверным, т.к. в задании также просят найти мат.ожидание времени работы этого алгоритма, а также зависимость его от p.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.08.2013, 10:53     Кормен. Задача. Генератор случайных чисел
Посмотрите здесь:

C++ Генератор случайных чисел
C++ генератор случайных чисел
C++ Генератор случайных чисел
C++ Генератор случайных чисел
Генератор случайных чисел C++
C++ Генератор случайных чисел
C++ Генератор случайных чисел
Генератор случайных чисел C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Fyret
184 / 170 / 13
Регистрация: 30.07.2013
Сообщений: 359
08.08.2013, 12:27     Кормен. Задача. Генератор случайных чисел #2
Я давно не имел дела с теорией вероятностей, но есть такая идея: вызывать BiasedRandom (запоминая предыдущий результат) пока он не выдаст 01 или 10. Вероятность обеих последовательнотей одинакова - p*(1-p), первой выпала 01 - возвращаем 0, если 10 - 1.
Yandex
Объявления
08.08.2013, 12:27     Кормен. Задача. Генератор случайных чисел
Ответ Создать тему
Опции темы

Текущее время: 19:34. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru