74
правки
Изменения
Нет описания правки
=== Доказательство корректности ===
Докажем по индукции, что вероятность получить любой перфикс <tex> P </tex> равна <tex> S(P)\over{C(n)} </tex>, где <tex> C(n) </tex> - число различных комбинаторных объектов данного типа длины <tex> n </tex>, а <tex> S(P) </tex> - число различных комбинаторных обьектов с таким префиксом.
*Любой комбинаторный объеут имеет пустой перфикс, следовательно <tex> S(\varnothing)=C(n) </tex>. Вероятность получить любой префикс <tex> P </tex> длины <tex> 1 </tex> равна <tex> S(P)\over{S(\varnothing)} </tex>, что равно <tex> S(P)\over{C(n)} </tex>.
*Пусть вероятность получить префикс <tex> P </tex> длины <tex> l </tex> равна <tex> S(P)\over{C(n)} </tex>
== Битовые вектора ==
Рассмотрим алгоритм получения случайного битового вектора. В битовом векторе может находиться только два типа элементов: <tex> 0 </tex> и <tex> 1 </tex>, следовательно <tex> k = 2 </tex>. Заметим что для любого префикса длины <tex> l </tex> число возможных комбинаторных объектов длины <tex> n </tex> одинаково и равно<tex> 2^{n-l} </tex>, следовательно на каждом шаге алгоритма небходмо выбирать с равной вероятностью <tex> 0 </tex> или <tex> 1 </tex>
'''vector<int>''' randomBitVector(n: '''int'''): <font color = green> // <tex> n </tex> {{---}} размер битового вектора.</font>
