Задача
Є функція 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; }
Недолік методу – існує теоретична імовірність (хоча і дуже мала) входження у нескінченний цикл.