74
правки
Изменения
→Доказательство корректности
|proof=Докажем по [[Математическая индукция|индукции]]:
'''База:''' Заметим, что любой комбинаторный объект имеет пустой перфикс (<tex> \varnothing </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> P </tex> некоторый префикс <tex> P' </tex> длины <tex> l+1 </tex> равна <tex> S(P')\over{S(P)} </tex> , следовательно вероятность получить префикс <tex> P' </tex> равна <tex> S(P)\over{C(n)} </tex><tex>\cdot</tex><tex> S(P')\over{S(P)} </tex> что равно <tex> S(P')\over{C(n)} </tex> .
Следовательно предположение индукции верно для всех возможных префиксов любой длины.
}}
Результат работы алгоритма является префиксом размера <tex> n </tex> и для любого такого префикса существует только один комбинаторный объект размера размера <tex> n </tex> {{---}} совпадающий с этим префиксом (т.е. <tex> S(result)=1 </tex>). Из чего по доказанной лемме следует, что вероятность получения одинакова для всех различных результатов и равна <tex> 1\over{C(n)} </tex>.
== Примеры решения задач ==
