Главная arrow icon Вопросы arrow icon Учеба и наука arrow icon Информатика arrow icon Два друга играют в игру: один…

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

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

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

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

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

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

Рейтинг: 121 998
6-й в Учебе и науке
у меня получилось 8 вопросов
19.11.15

Еva
Рейтинг: 121 998
6-й в Учебе и науке
Читать ответы
Посмотреть всех экспертов из раздела Учеба и наука > Информатика
Похожие вопросы
Пользуйтесь нашим приложением Доступно на Google Play Загрузите в App Store
  • карты visa
  • карты master card
  • карты maestro
  • карты МИР
Мы используем файлы cookie. Пользуясь сайтом, вы принимаете условия нашего соглашения. Принять Детальнее