Вопрос школьника
Мы знаем, что Поля родилась с 15 по 28 января. За сколько вопросов мы можем узнать ее день рождения, если она согласна отвечать на наши вопросы только «да» или «нет». Каким может быть первый вопрос?
Ответ от учителя
Если мы можем задавать только вопросы с ответами «да» или «нет», то мы можем использовать метод бинарного поиска.
Сначала мы задаем вопрос, относится ли день рождения Поли к первой половине периода (15-21 января). Если ответ «да», то мы продолжаем поиск в первой половине периода, задавая вопросы о середине этой половины (18 января) и т.д. Если ответ «нет», то мы продолжаем поиск во второй половине периода, задавая вопросы о середине этой половины (25 января) и т.д.
Таким образом, мы можем узнать день рождения Поли за максимум 4 вопроса.
Первый вопрос может быть: «Относится ли день рождения Поли к первой половине периода (15-21 января)?»
