74
правки
Изменения
→Доказательство корректности
== Доказательство корректности ==
Докажем, что с помощью данного алгоритма действительно можно получать случайный комбинаторный размера <tex> n </tex>, причем вероятность получения одинакова для каждого результата.
{{Лемма
|statement=Вероятность получить некоторый перфикс <tex> P </tex> равна <tex> S(P)\over{C(n)} </tex>, где <tex> C(n) </tex> {{---}} число различных комбинаторных объектов данного типа длины <tex> n </tex>, а <tex> S(P) </tex> {{---}} число различных комбинаторных обьектов длины <tex> n </tex> с таким префиксом.
}}
Результат работы алгоритма является префиксом размера <tex> n </tex> и , а для любого такого префикса существует только один комбинаторный объект размера размера <tex> n </tex> {{---}} совпадающий с этим префиксом (т.е. <tex> S(result)=1 </tex>). Из чего по доказанной лемме следует, что вероятность получения одинакова для всех различных результатов и равна <tex> 1\over{C(n)} </tex>.
== Примеры решения задач ==
