Итак, у меня есть проблема вероятности, которую (из чистой скуки) я решил попробовать и решить с помощью симуляций.
Проблема: Какова вероятность вытянуть ровно одну старшую карту из 6-карточной руки.
Теперь эта проблема, в частности, касается какой-то игры, в которую играют в моей стране, поэтому по какой-то странной причине есть 21 старшая карта, но это не важно.
Решая эту проблему вручную, используя базовую комбинаторику, я получил:
А теперь, вот как я смоделировал это в C:
Основная функция:
int main(void)
{
srand(time(0));
int deck[52];
int i;
for(i = 0; i<21; i++) deck[i] = 1;
for(i = 21; i<52; i++) deck[i] = 0;
int n;
printf("# of simulations: ");
scanf("%d", &n);
int memo[52];
int hits = 0;
for(i = 0; i<n; i++){
clear_memo(memo);
hits += simulate(deck, memo);
}
printf("Result: %lf\n", (double)hits/n);
}
Таким образом, колода представляет собой массив из 52 чисел, где первые 21 имеют значение 1 (старшие карты), а остальные 31 элемент имеют значение 0 (младшие карточки).
Памятка будет отправляться в функцию симуляции каждый раз, чтобы отслеживать, какие карты уже были извлечены. Памятку также сбрасывают каждый раз, используя функцию clear_memo , которая ничего не делает, но устанавливает все значения в ноль.
Затем он вызывает функции симуляции и подсчитывает попадания.
Вот функция симуляции:
int simulate(int * deck, int * memo){
//I draw the first card separetly in order to initialize the had_high variable
int index = ( rand() % 52 );
int card = deck[index];
int had_high = (card == 1);
memo[index] = 1;
//printf("%d ", index);
int i = 1;
while(i < 6){
int draw = (rand() % 52);
//printf("%d ", draw);
if(memo[draw]) continue;
index = draw;
card = deck[index];
memo[index] = 1;
if(card){
if(had_high) { //meaning there are 2 high cards, no hit
//printf("\n");
return 0;
}
had_high = 1; //if not, then this is the first high card
}
i++;
}
printf("\n");
return had_high; //the function would've reached this point even if all the cards had been low
//therefore I return had_high instead of just 1
}
Сама функция симуляции работает, я много раз тестировал ее отдельно, и, похоже, с этим проблем не было.
Однако, когда я запускаю программу с большим количеством симуляций (100k или 1m), результат всегда составляет ок. 0,175 - это не то, что я получил при расчете вручную.
Я достаточно уверен, что мои расчеты вручную верны (но поправьте меня, если я тоже ошибаюсь).
Если я прав насчет ручных вычислений, то должно быть что-то не так с тем, как я смоделировал это событие. Одна из моих мыслей заключалась в том, что она как-то связана с функцией rand и с ее псевдослучайностью, но я действительно не знаю, так как очень сложно протестировать что-либо, работающее со случайными числами.
Есть идеи?
Спасибо.
EDIT:
Согласно запросу klutt:
void clear_memo(int * memo){
int i = 0;
for(;i<52;i++) memo[i] = 0;
}