Question

Коля познакомился с новой игрой отгадай число, в которой за минимальное число в диапазоне от 1 до N. За какое наименьшее количество вопросов (на которое соперник отвечает да или нет)Коля может угадать число ? Вводится одно число N. Входные данные 5, Выходные данные 3

Answer 1

Ответ:

При N=5 минимальным кол-вом вопросов (при оптимальных условиях) будет 2 вопроса

Объяснение:

Допустим в диапазоне 1-N было выбрано число 4

Задём вопрос "Это число больше 3 (половина возможных чисел)?", получаем ответ "да", потом спрашиваем "это число больше 4 (половина оставшихся чисел)?", получаем ответ "нет", значит раз это число больше 3 и не больше 4, то это и есть 4, остаётся уточнить это, задав 3 вопрос "является ли это число четвёркой"

Допустим выбрано число 1

"Это число больше 3?" - "нет"

"Это число больше 1?" - "нет" -- логично что это число 1

а если бы ответ был бы "да", то осталось бы проверить является ли это число 2, иначе это 3

Answer 2

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

Изначально Коля задает вопрос: "Это число N/2?" Если соперник отвечает "да", то Коля угадал число за один вопрос. Если соперник отвечает "нет", то Коля задает следующий вопрос: "Это число больше N/2 или меньше?" Если соперник отвечает "больше", то Коля знает, что число находится в верхней половине диапазона (от N/2 + 1 до N). Затем Коля делит этот новый диапазон пополам и задает вопрос, например: "Это число (N/2 + N)/2?" Если соперник отвечает "да", то Коля угадал число за два вопроса. Если соперник отвечает "нет", то Коля знает, что число находится в нижней половине нового диапазона (от N/2 + 1 до N), и он задает вопрос: "Это число больше (N/2 + 1)/2 или меньше?" Процесс повторяется, пока Коля не угадает число.

В данном случае, когда N = 5, процесс будет выглядеть следующим образом:

1. Коля задает вопрос: "Это число 5/2?" (вопрос 1)

   • Если соперник отвечает "да", Коля угадал число.
   • Если соперник отвечает "нет", переходим к следующему шагу.

2. Коля задает вопрос: "Это число больше 5/2 или меньше?" (вопрос 2)

   • Если соперник отвечает "больше", переходим к шагу 3.
   • Если соперник отвечает "меньше", переходим к шагу 4.

3. Коля задает вопрос: "Это число (5/2 + 5)/2?" (вопрос 3)

   • Если соперник отвечает "да", Коля угадал число.
   • Если соперник отвечает "нет", Коля угадывает оставшееся число (5) и заканчивает.

4. Коля задает вопрос: "Это число больше (5/2 + 1)/2 или меньше?" (вопрос 3)

   • Если соперник отвечает "больше", Коля угадывает оставшееся число (4) и заканчивает.
   • Если соперник отвечает "меньше", Коля угадывает оставшееся число (3) и заканчивает.

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