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