Question

Добрый вечер! Помогите пожалуйста срочно решить задачу. Мистер Фокс и мистер Форд играют в такую игру. Мистер Фокс загадывает число от 1 до 255 (включительно). Мистер Форд может задать несколько вопросов, на каждый из которых можно ответить да или нет. Все вопросы задаются одновременно (например, записываются на бумаге), все ответы даются одновременно. Каким наименьшим количеством вопросов мистер Форд может гарантированно обойтись, чтобы наверняка узнать загаданное число?

Answer 1

Наверное, 8. Сначала делим число 226 пополам (т.к всего 226 вариантов чисел), задаёт вопрос, "больше 113 или нет". После опять дели пополам оставшуюся часть и опять задаёт аналогичный вопрос. И т.д.

Answer 2

Добрый вечер! Чтобы гарантированно узнать загаданное число от 1 до 255, мистер Форд может воспользоваться стратегией, основанной на бинарном поиске.

Сначала он задает вопрос, разделяющий диапазон возможных чисел пополам: "Мистер Фокс, ваше число больше 127?". Если мистер Фокс отвечает "да", то мистер Форд оставляет вариант от 128 до 255. Если ответ "нет", то оставляет вариант от 1 до 127.

Затем он задает вопрос, снова разделяющий текущий диапазон пополам: "Мистер Фокс, ваше число больше 63?". И снова исключает половину возможных чисел в зависимости от ответа.

Продолжая таким образом, мистер Форд будет делить диапазон возможных чисел пополам на каждом шаге до тех пор, пока останется только одно возможное число. Всего ему понадобится 8 вопросов, чтобы гарантированно определить загаданное число.

Таким образом, наименьшим количеством вопросов, которым гарантированно можно обойтись, чтобы узнать загаданное число от 1 до 255, является 8 вопросов.