Випадкове число від 0 до 2

Задача

Є функція random2() яка з рівною імовірністю повертає 0 або 1. Треба на її основі написати функцію яка з рівною імовірністю повертає 0,1 або 2.

Рішення

Треба якось привести результати виклику random2() до трьох рівноможливих варіантів. Побудуємо таку таблицю:

1-й виклик random2() 2-й виклик random2() Результат
0 0 0
0 1 1
1 0 2
1 1 ?

 

Бачимо що у нас 4 рівноможливі варанти. Якщо четвертий результат замінити на рекурсивний виклик цієї ж функції то матимемо три рівноімовірні варіанти.

int random3() { int result = random2() * 2 + random2(); if (result == 3) result = random3(); return result; }

Недолік методу – існує теоретична імовірність (хоча і дуже мала) входження у нескінченний цикл.

Залишити відповідь

Зайти з допомогою: