Скажем есть некая программа, симулирующая подброс монетки. Нужно сделать так, чтобы в 95 случаях подброса монетки из ста выпадал орел, а не решка. Как можно этого добиться?
-
7а почему в метках указан С++ 11? Думаете, эту архисложную задачу можно решить только с привлечением средств последнего стандарта С++?– DreamChild4 мар 2013 в 15:35
-
Конечно, именно так– PaulD4 мар 2013 в 15:50
-
1Страуструп, наверное, подавился бы, узнав, об этом– DreamChild4 мар 2013 в 16:01
-
Что ж, жаль его– PaulD4 мар 2013 в 16:02
-
1@SoloMio: тогда пользуйтесь не резервуаром, а rand.– VladD4 мар 2013 в 16:44
5 ответов
rand - это хорошее решение и на больших объемах данных он даст достаточно равномерное распределение. Но на не очень больших будет небольшой разброс (несколько процентов). Если же нужна 100% гарантия, что будет правильная вероятность, тогда нужно использовать другой подход. Смотрите мой пример, если Ваш компилятор не поддерживает последний стандарт, то просто посмотрите, как реализована shuffle.
#include <iostream>
#include <algorithm>
#include <random>
#include <chrono>
using namespace std;
int main() {
vector<int> a(100); // массив на 100 бросков
fill_n(a.begin(), 95, 1); // 1 - это орлы
fill_n(a.begin() + 95, 5, 0); // 0 - это решки
// теперь магия. получаем сид и перемешиваем массив
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
shuffle(a.begin(), a.end(), std::default_random_engine(seed));
// делаем подсчет
int orel = count_if (a.begin(), a.end(), [](int i){return (i==1);} );
int reshka = count_if (a.begin(), a.end(), [](int i){return (i==0);} );
// выведем соотношение
cout << "орлов/решек " << orel << "/" << reshka << endl;
// выведем набор
for_each (a.begin(), a.end(), [](int i) {cout << i << " ";});
cout << endl;
return 0;
}
-
-
<мелкие_придирки>вероятность как раз правильная в случае простого rand. вероятность того, что из 100 бросков выпадет ровно 95 орлов равна в точности
C^5_100/2^100 = 75287520 / 1267650600228229401496703205376 ~= 6*10^{-23}
</мелкие_придирки>– VladD4 мар 2013 в 16:43 -
-
@KoVadim: Да, согласен, вычисления не верны, т.к. они отталкиваются от равных вероятностей выпадения орла и решки, чего априори нет. Но: ваша последовательность не случайна! Например, если сначала выпало 5 решек подряд, гарантированно дальше выпадет 95 орлов, что в случае монеты не так: вероятность выпадения орла не имеет права зависеть от предыдущих результатов.– VladD4 мар 2013 в 17:41
-
Генерируй случайное число. От одного до ста. Потом пишешь: если число меньше 95, тогда орёл, иначе решка. Вот и будет вероятность 0,95
-
это если распределение равномерное, если же нет, то у нас орел будет в куда меньшем количестве чем нужно.– PaulD4 мар 2013 в 14:58
-
случайное число и подразумевает, что любое число выпадет с одинаковой вероятностью.– sinedsem4 мар 2013 в 15:00
-
6
-
3>Ха-ха, как смешно любезнейший, а откуда такая дуболомная серьезность? Вам дали очевиднейший ответ на более чем элементарный вопрос, а вы нос воротите. Хоть бы спасибо сказали ответившим. Не нравится алгоритм генерации случайных числел в С++? Напишите свой с блэкджеком и барышнями, вероятно, он будет куда как лучше тех, что уже реализованы в языке 4 мар 2013 в 16:11
-
2Спасибо-то спасибо, но зачем при даче ответа язвить и что-то там еще делать? Ну ответили бы просто: "функция Rand() возвращает число в соответствии с равномерным законом распределения вероятности", и никаких проблем. К чему этот сарказм, "мамой клянусь"? Мне эта информация нужна для написания тестового задания, это приложение для казино. И если в итоге распределение будет не равномерным, а экспоненциальным к примеру, кто-то потеряет много денег. Не сложно догадаться кому будет плохо после этого.– PaulD4 мар 2013 в 16:22
Давайте вспоминать математику школьного курса за 5 класс :) Тема: "правильные дроби".
95 из 100( вероятность выпадения орла --- 95/100 ) => 95/100 = 19/20 => вам нужно подбирать число в диапазоне от 1 до 20 :
srand(time(NULL));
int res = rand()%20+1;
cout<<res<<endl;
if(res==20) cout<<"Решка!"; else cout<<"Орел!";
cout<<endl;
-
так по сути, что я и предложил. естественно, что оптимальнее будет сократить.– sinedsem4 мар 2013 в 15:41
-
Не оптимальнее - вернее. При генерации чисел от 1 до 100 вероятность генерации чисел от 95 до 100 может быть несколько меньше. Обусловлено это может быть тем, что процессор генерирует псевдослучайные числа в соответствии с заданным "зерном". Поправьте кто-нибудь, если я ошибаюсь.– AseN4 мар 2013 в 15:49
-
позапускайте такой код и поудивляйтесь #include <iostream> #include <cstdlib> using namespace std; int main() { const int range = 10000; int q = 0; for (int i = 0; i < range; i++) { int t = rand() % 100; if (t >= 95) q++; } cout << q*100.0/range << endl; return 0; } Только при 100000-1000000 попыток, процент стает правильным.– KoVadim4 мар 2013 в 16:06
-
@KoVadim: по такой логике, для вероятности 0.5 надо, чтобы всегда попеременно генерировался орёл и решка?– VladD4 мар 2013 в 17:14
-
1в случае 1/2 резервуар может быть равен двум, но не обязательно. >> последовательность с резервуаром не случайна: вы всегда можете предсказать, каким будет последний результат в резервуаре логично. Но это будет известно только тогда, когда будут проанализированы все предыдущие элементы. Приведу контрпример. Представьте себе колоду карт. Если ее перетасовать, то карты там будут в случайном порядке, но после того, как все, кроме последней будут извлечены, всегда можно предсказать последнюю карту. Но от этого она менее случайной не станет. Это как с котом Шрёдингера.– KoVadim4 мар 2013 в 17:46
Если нужно гарантировано 95% орел, то нужно делать список например из 100 (нужно точно знать количество подбросов), 5 любых (допустим первых) делать true, остальные false, а потом выдёргивать рандомно их поодному из списка, чтоб они не повторялись, получится, что к концу списка отношение стопро будет 95/5
Тема конечно старая, но никто так и предложил с++11 way. Поэтому на правах просвящения народных масс:
// bernoulli_distribution
#include <iostream>
#include <random>
int main()
{
const int nrolls=10000;
std::default_random_engine generator;
std::bernoulli_distribution distribution(0.95);
int count=0; // count number of trues
for (int i=0; i<nrolls; ++i) if (distribution(generator)) ++count;
std::cout << "bernoulli_distribution (0.95) x 10000:" << std::endl;
std::cout << "true: " << count << std::endl;
std::cout << "false: " << nrolls-count << std::endl;
return 0;
}