Два друга играют в игру: один загадывает целое число от 1 до 300, а второй задает вопросы о загаданном числе, на которые можно ответить да или нет....

Разрешается задавать вопросы только двух видов: “”Это число больше N?” или “Это число равно N?”, где N – любое число из указанного промежутка. Какое минимальное число вопросов понадобится, чтобы гарантированно отгадать любое загаданное число из указанного промежутка?

Лучший ответ по мнению автора

для данной задачи, в качестве универсального решения подходит двоичный поиск (ссылка, вторая часть статьи)
а его сложность определяется формулой Log2(N)=Log2(300)=8.2288186905

то есть гарантированное решение находится за 9 ходов, естественно, в случае везения, количество ходов может быть меньшим
19.11.15
Лучший ответ по мнению автора

Другие ответы

Сейчас на сайте
у меня получилось 8 вопросов
19.11.15

Елена Васильевна

Сейчас на сайте
Читать ответы

Виктор Щебетун

Читать ответы

Карина

Читать ответы
Посмотреть всех экспертов из раздела Учеба и наука > Информатика
Пользуйтесь нашим приложением Доступно на Google Play Загрузите в App Store