Задача к ЕГЭ по информатике на тему «измерение информации» №3

Просмотров 13 Комментарии 0

Ваш друг предложил вам угадать число, которое он задумал. За какое наименьшее число вопросов (на эти вопросы он может ответить либо да, либо нет) можно гарантированно угадать число? Известно, что число натуральное и не превосходит $128$ .

В данной ситуации бессмысленно просто угадывать число так как пришлось бы задать максимум $128$ вопросов, а это слишком много. Значит, нужно как-то делить эти числа между собой. При этом лучше их делить пополам, ведь если спросить в первой ли число трети от всех можно получить ответ нет, и тогда нужно искать его в оставшихся двух третьих чисел.
Тогда сначала задаем вопрос «Это число находится в большей половине от всех чисел?»
Если ответ «Да», то число находится от $65$ до $128$ . «Нет» — от $1$ до $64$ .
Допустим число — $35$ .
Тогда на вопрос будут ответы: нет $(1...64 )$ , да $(33...64)$ , нет $(33 ...48)$ , нет $(33...40 )$ , нет $(33 ...36)$ , да $(35...36 )$ , нет $(35)$ .
Заметим, что если перевести все «Да» в $1$ , а «Нет» в $0$ , то получится код $01000102$ , а $3510 = 01000112$ . Они отличаются на единицу, потому что мы считали от $1$ до $128$ , а $7$ битами можно записать $0...127$ .
Значит число можно отгдадать за $7$ вопросов. Таким образом, мы, можно сказать, с каждым вопросом узнаем по $1$ биту числа.

Ответ: 7