Иногда задачи из прошлых математических олимпиад неожиданно начинают появляться в интернете. Они выглядят сложными, но мы так не считаем: давайте разберемся с этой задачей вместе.
Кажется, что для решения такой задачи потребуется множество попыток. Однако математики уверены: задавая правильные вопросы, можно обойтись всего десятью. Как это возможно? Попробуйте разобраться, но будьте готовы к тому, что задача не из простых.
Условие
Друг задумал целое число в диапазоне от 1 до 1000. Ваша задача — угадать его, задавая вопросы. Но есть одно строгое правило: на каждый вопрос ваш друг может ответить только «да» или «нет».
Эта задача не просто о том, чтобы угадать число, но и о стратегии поиска. Каждый вопрос должен максимально сокращать количество возможных вариантов. Если действовать верно, после каждого ответа количество возможных вариантов уменьшается примерно вдвое. Вот какой способ решения мы предлагаем.
Принцип решения
Всего 10 вопросов достаточно для того, чтобы гарантированно угадать любое целое число от 1 до 1000. Это классическая задача на бинарный поиск, где каждый вопрос делит возможный диапазон пополам. Используйте вопросы в формате: «Задуманное число не больше X?», где X — середина текущего интервала. Начните с диапазона [1; 1000].
-
Если ответ «да», новый диапазон — [низ; X].
-
Если «нет», новый диапазон — [X+1; высок].
Таким образом, каждый вопрос исключает примерно половину возможных вариантов. После 10 вопросов диапазон сужается до одного числа.
Пошаговый алгоритм
Вот точная последовательность вопросов для любого результата (адаптируйте X в зависимости от ответов):
-
Не больше 500?
-
Не больше 250? (или 750, если предыдущий ответ «нет»)
-
Не больше 125? (или 375/625/875 по ситуации)
-
Не больше 62? (и так далее, пересчитывая середину)
-
Не больше 31?
-
Не больше 15?
-
Не больше 7?
-
Не больше 3?
-
Не больше 1?
-
Равно 1? (или финальное уточнение).
Попробуем угадать число 92 с помощью бинарного поиска
Давайте применим стратегию вопросов формата «Задуманное число не больше X?», деля диапазон пополам на каждом шаге.
-
Начальный диапазон: 1–1000.
Вопрос: «Число не больше 500?»
Ответ: Да → новый диапазон: 1–500 -
Диапазон: 1–500
Вопрос: «Число не больше 250?»
Ответ: Да → новый диапазон: 1–250 -
Диапазон: 1–250
Вопрос: «Число не больше 125?»
Ответ: Да → новый диапазон: 1–125 -
Диапазон: 1–125
Вопрос: «Число не больше 62?»
Ответ: Нет → новый диапазон: 63–125 -
Диапазон: 63–125
Вопрос: «Число не больше 93?»
Ответ: Да → новый диапазон: 63–93 -
Диапазон: 63–93
Вопрос: «Число не больше 77?»
Ответ: Нет → новый диапазон: 78–93 -
Диапазон: 78–93
Вопрос: «Число не больше 85?»
Ответ: Нет → новый диапазон: 86–93 -
Диапазон: 86–93
Вопрос: «Число не больше 89?»
Ответ: Нет → новый диапазон: 90–93 -
Диапазон: 90–93
Вопрос: «Число не больше 91?»
Ответ: Нет → новый диапазон: 92–93 -
Диапазон: 92–93
Вопрос: «Число не больше 92?»
Ответ: Да → задуманное число: 92
Итог:
После 10 вопросов диапазон сужается до одного числа, и мы точно определяем задуманное число. Таким образом, бинарный поиск обеспечивает успех за минимальное количество шагов.
Фух! Это было сложно. Давайте теперь решим более простую задачу.
Фото: hi-tech.mail.ru