Question

Мальчик задумал число от 1 до 100. Чтобы его угадать, дедушка может задавать вопросы, на которые мальчик может ответить «да» или «нет». За сколько вопросов дедушка наверняка сможет угадать число?

Answer 1

Он может называть каждое число по порядку. За 100 раз он наверняка угадает число.

Answer 2

Дедушка может использовать стратегию бинарного поиска, чтобы угадать число мальчика с наименьшим количеством вопросов.

Идея бинарного поиска заключается в том, чтобы делить диапазон возможных чисел пополам на каждом шаге и задавать вопросы, чтобы исключить половину диапазона.

Изначально дедушка может спросить мальчика, является ли его число больше 50. Если мальчик отвечает "да", то дедушка может исключить все числа от 1 до 50, иначе - все числа от 51 до 100.

На каждом шаге дедушка будет делить оставшийся диапазон пополам и задавать вопросы, чтобы исключить половину оставшихся чисел. Например, если остался диапазон от 1 до 50, дедушка может спросить мальчика, является ли его число больше 25. Если мальчик отвечает "да", то дедушка исключает числа от 1 до 25, иначе - числа от 26 до 50.

Таким образом, дедушка будет делить диапазон пополам на каждом шаге и исключать половину оставшихся чисел. Количество вопросов, необходимых для угадывания числа, будет равно количеству шагов, необходимых для сокращения диапазона до одного числа.

В данном случае, диапазон чисел от 1 до 100 может быть сокращен до одного числа за максимум 7 шагов. На первом шаге дедушка спрашивает мальчика, является ли число больше 50, на втором - больше 25, на третьем - больше 12, на четвертом - больше 6, на пятом - больше 3, на шестом - больше 1, и на седьмом - равно 1.