2001-gre-vs-practice.pdf/Q03

Задача зарезервирована: Urmat A 18:47, 19 декабря 2024 (UTC)

Задача зарезервирована: Urmat A 19:01, 19 декабря 2024 (UTC)

Задача зарезервирована: Urmat A 19:01, 19 декабря 2024 (UTC)

Вопрос: Q03-e5724f

Боб загадал число от 1 до 1000. Мэри должна угадать это число, спрашивая у Боба вопрос на "Да или Нет". Она знает, что он никогда не врёт. Используя оптимальную стратегию, сколько вопросов ей придётся задать в худшем случае, чтобы найти число?

Ответы

1. 1000
2. 999
3. 500
4. 32
5. Правильный ответ: 10

Объяснение =

Исходники — вопрос 3 на 12 странице книги «2001-gre-vs-practice.pdf»

Можно пройтись бинарным поиском, это оптимально. Идея в том, чтобы каждый раз делить числовой отрезок на 2 и выбирать тот, что нужно. Есть число 1024, оно же . А 1000<1024, поэтому максимум ей потребуется 10 вопросов.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.