Метод дихотомии: различия между версиями
Содержимое удалено Содержимое добавлено
Строка 21:
Искушённый читатель, должно быть, уже заметил, что в данном случае в ответ закрадываются степени двойки. И он не ошибся. Для того, чтобы передать один из двух возможных вариантов, требуется один бит. Два бита могут передать один из <math>2 \cdot 2 = 4</math> вариантов. Три бита — один из <math>2 \cdot 2 \cdot 2 = 8</math> вариантов. С помощью <math>n</math> бит можно передать один из <math>2^n</math> вариантов.
Мы не будем подробно останавливаться на философском вопросе «А как же быть, если число вариантов не является степенью двойки?» Дотошного читателя не устраивает метод полутора землекопов<ref>А ведь звучит — «Ответь мне честно „да“ или „нет“ на полтора вопроса!»? Вообще говоря, «количество информации», которое мы измеряем, в общем случае может не выражаться целым числом бит. Но, так как в данном случае мы говорим о числе вопросов, то будем для простоты считать, что мы ищем ту степень двойки, где она в первый раз будет больше либо равна данному числу. Если число вариантов представляет собой степень двойки, будет иметь место равенство, для не степеней двойки мы найдём первую превосходящую степень
Ну дык, ебать спартак ебаб
</ref>.
== Отгадаем число ==
| |||