3

Скажем есть некая программа, симулирующая подброс монетки. Нужно сделать так, чтобы в 95 случаях подброса монетки из ста выпадал орел, а не решка. Как можно этого добиться?

15
  • 7
    а почему в метках указан С++ 11? Думаете, эту архисложную задачу можно решить только с привлечением средств последнего стандарта С++?
    – DreamChild
    4 мар 2013 в 15:35
  • Конечно, именно так
    – PaulD
    4 мар 2013 в 15:50
  • 1
    Страуструп, наверное, подавился бы, узнав, об этом
    – DreamChild
    4 мар 2013 в 16:01
  • Что ж, жаль его
    – PaulD
    4 мар 2013 в 16:02
  • 1
    @SoloMio: тогда пользуйтесь не резервуаром, а rand.
    – VladD
    4 мар 2013 в 16:44

5 ответов 5

7

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;
}
10
  • Спасибо, именно то что и нужно было
    – PaulD
    4 мар 2013 в 16:09
  • <мелкие_придирки>вероятность как раз правильная в случае простого rand. вероятность того, что из 100 бросков выпадет ровно 95 орлов равна в точности C^5_100/2^100 = 75287520 / 1267650600228229401496703205376 ~= 6*10^{-23}</мелкие_придирки>
    – VladD
    4 мар 2013 в 16:43
  • а оно нам нужно? задача то была не в этом.
    – KoVadim
    4 мар 2013 в 17:29
  • @KoVadim: Да, согласен, вычисления не верны, т.к. они отталкиваются от равных вероятностей выпадения орла и решки, чего априори нет. Но: ваша последовательность не случайна! Например, если сначала выпало 5 решек подряд, гарантированно дальше выпадет 95 орлов, что в случае монеты не так: вероятность выпадения орла не имеет права зависеть от предыдущих результатов.
    – VladD
    4 мар 2013 в 17:41
  • Ваши рассуждения не имеют ничего общего с задачей.
    – KoVadim
    4 мар 2013 в 17:49
6

Генерируй случайное число. От одного до ста. Потом пишешь: если число меньше 95, тогда орёл, иначе решка. Вот и будет вероятность 0,95

8
  • это если распределение равномерное, если же нет, то у нас орел будет в куда меньшем количестве чем нужно.
    – PaulD
    4 мар 2013 в 14:58
  • случайное число и подразумевает, что любое число выпадет с одинаковой вероятностью.
    – sinedsem
    4 мар 2013 в 15:00
  • 6
    мамой клянусъ!
    – sinedsem
    4 мар 2013 в 15:40
  • 3
    >Ха-ха, как смешно любезнейший, а откуда такая дуболомная серьезность? Вам дали очевиднейший ответ на более чем элементарный вопрос, а вы нос воротите. Хоть бы спасибо сказали ответившим. Не нравится алгоритм генерации случайных числел в С++? Напишите свой с блэкджеком и барышнями, вероятно, он будет куда как лучше тех, что уже реализованы в языке
    – DreamChild
    4 мар 2013 в 16:11
  • 2
    Спасибо-то спасибо, но зачем при даче ответа язвить и что-то там еще делать? Ну ответили бы просто: "функция Rand() возвращает число в соответствии с равномерным законом распределения вероятности", и никаких проблем. К чему этот сарказм, "мамой клянусь"? Мне эта информация нужна для написания тестового задания, это приложение для казино. И если в итоге распределение будет не равномерным, а экспоненциальным к примеру, кто-то потеряет много денег. Не сложно догадаться кому будет плохо после этого.
    – PaulD
    4 мар 2013 в 16:22
4

Давайте вспоминать математику школьного курса за 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;
10
  • так по сути, что я и предложил. естественно, что оптимальнее будет сократить.
    – sinedsem
    4 мар 2013 в 15:41
  • Не оптимальнее - вернее. При генерации чисел от 1 до 100 вероятность генерации чисел от 95 до 100 может быть несколько меньше. Обусловлено это может быть тем, что процессор генерирует псевдослучайные числа в соответствии с заданным "зерном". Поправьте кто-нибудь, если я ошибаюсь.
    – AseN
    4 мар 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 попыток, процент стает правильным.
    – KoVadim
    4 мар 2013 в 16:06
  • @KoVadim: по такой логике, для вероятности 0.5 надо, чтобы всегда попеременно генерировался орёл и решка?
    – VladD
    4 мар 2013 в 17:14
  • 1
    в случае 1/2 резервуар может быть равен двум, но не обязательно. >> последовательность с резервуаром не случайна: вы всегда можете предсказать, каким будет последний результат в резервуаре логично. Но это будет известно только тогда, когда будут проанализированы все предыдущие элементы. Приведу контрпример. Представьте себе колоду карт. Если ее перетасовать, то карты там будут в случайном порядке, но после того, как все, кроме последней будут извлечены, всегда можно предсказать последнюю карту. Но от этого она менее случайной не станет. Это как с котом Шрёдингера.
    – KoVadim
    4 мар 2013 в 17:46
3

Если нужно гарантировано 95% орел, то нужно делать список например из 100 (нужно точно знать количество подбросов), 5 любых (допустим первых) делать true, остальные false, а потом выдёргивать рандомно их поодному из списка, чтоб они не повторялись, получится, что к концу списка отношение стопро будет 95/5

3

Тема конечно старая, но никто так и предложил с++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;
}

Попробовать на ideone

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.