Вопрос школьника
Петя задумал натуральное число меньше 100. Покажите, что вы можете определить это число, задав Пете не более 7 вопросов, на которые он будет давать ответы словами «да» или «нет».
Ответ от учителя
Для решения этой задачи можно использовать метод бинарного поиска. Суть метода заключается в том, что мы делим возможный диапазон значений на две части и задаем вопрос, в какой из этих двух частей находится искомое число. Затем мы повторяем этот процесс для выбранной части диапазона, пока не найдем искомое число.
1. Спросим у Пети, является ли число, которое он задумал, меньше 50. Если да, то мы можем исключить все числа от 50 до 99 из возможных вариантов.
2. Если Петя ответил, что его число меньше 50, то мы спрашиваем, является ли число, которое он задумал, меньше 25. Если да, то мы можем исключить все числа от 25 до 49 из возможных вариантов.
3. Если Петя ответил, что его число меньше 25, то мы спрашиваем, является ли число, которое он задумал, меньше 13. Если да, то мы можем исключить все числа от 13 до 24 из возможных вариантов.
4. Если Петя ответил, что его число меньше 13, то мы спрашиваем, является ли число, которое он задумал, меньше 7. Если да, то мы можем исключить все числа от 7 до 12 из возможных вариантов.
5. Если Петя ответил, что его число меньше 7, то мы спрашиваем, является ли число, которое он задумал, меньше 4. Если да, то мы можем исключить все числа от 4 до 6 из возможных вариантов.
6. Если Петя ответил, что его число меньше 4, то мы спрашиваем, является ли число, которое он задумал, меньше 2. Если да, то мы можем исключить все числа от 2 до 3 из возможных вариантов.
7. Если Петя ответил, что его число меньше 2, то остается только одно возможное число — 1.
Таким образом, мы задали всего 7 вопросов и определили число, которое задумал Петя.
