2001-gre-vs-practice.pdf/Q03

Вопрос: Q03-e5724f

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

Ответы

• 1000
• 999
• 500
• 32
• Правильный ответ: 10

Объяснение

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

Можно пройтись бинарным поиском , это оптимально.

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

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

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

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