Сколько вопросов «да/нет» нужно, чтобы угадать число
Информатика, 9 класс · Множества
📚 Программа 9 класса · модуль «Электронные таблицы, кодирование, графы» — тренажёр 5 из 8. За освоение тренажёра — +15 ★.
Правило и как решать
Каждый вопрос делит варианты пополам: за k вопросов различимо 2^k чисел.
Подсказка: Найди наименьшую степень двойки, не меньшую N.
Примеры с разбором
Пример 1
Вопросов нужно; Чисел за 12 вопросов
Ответ: Вопросов нужно 7; Чисел за 12 вопросов 4096
Решение: Каждый вопрос удваивает число различимых вариантов: 2^7 = 128 ≥ 76, а 2^6 = 64 < 76. За 12 вопросов различимо 2^12 = 4096 чисел.
Пример 2
Вопросов нужно; Чисел за 6 вопросов
Ответ: Вопросов нужно 9; Чисел за 6 вопросов 64
Решение: Каждый вопрос удваивает число различимых вариантов: 2^9 = 512 ≥ 312, а 2^8 = 256 < 312. За 6 вопросов различимо 2^6 = 64 чисел.
Пример 3
Вопросов нужно; Чисел за 11 вопросов
Ответ: Вопросов нужно 9; Чисел за 11 вопросов 2048
Решение: Каждый вопрос удваивает число различимых вариантов: 2^9 = 512 ≥ 302, а 2^8 = 256 < 302. За 11 вопросов различимо 2^11 = 2048 чисел.