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