Коля познакомился с новой игрой отгадай число, в которой за минимальное число в диапазоне от 1 до n. за какое наименьшее количество вопросов (на которое соперник отвечает да или нет)коля может угадать число ? вводится одно число n. входные данные 5, выходные данные 3
При N=5 минимальным кол-вом вопросов (при оптимальных условиях) будет 2 вопроса
Объяснение:
Допустим в диапазоне 1-N было выбрано число 4
Задём вопрос "Это число больше 3 (половина возможных чисел)?", получаем ответ "да", потом спрашиваем "это число больше 4 (половина оставшихся чисел)?", получаем ответ "нет", значит раз это число больше 3 и не больше 4, то это и есть 4, остаётся уточнить это, задав 3 вопрос "является ли это число четвёркой"
Допустим выбрано число 1
"Это число больше 3?" - "нет"
"Это число больше 1?" - "нет" -- логично что это число 1
а если бы ответ был бы "да", то осталось бы проверить является ли это число 2, иначе это 3