Компьютер загадывает натуральное число от 1 до 21. После этого
можно ввести число, и он выдаст один из следующих ответов: «это
число равно загаданному», «отличается на 1 от загаданного», а если
число отличается от заданного более чем на 1, то отвечает просто
«больше загаданного» или «меньше загаданного». За какое
наименьшее количество вопросов можно узнать, какое число
загадал компьютер?
Ответы
Ответ дал:
1
Считаем наименьшее кол-во ходов в худшем случае
Робот загадывает 21
1)Выбираем число по середине - 11
Отсеивается числа от 1 до 12 включительно (тк число как минимум больше чем 11 на 2)
2)Среднее между 13 и 21 - 17
Отсеиваем числа до 18 включительно
3)Среднее между 19 и 21 - 20
2 хода на угадывания между 19 или 21(тк считаем в худшем случае
Ответ: 5 ходов
Аноним:
Хотел поругаться на условие «отличается на 1 от заданного», но посчитав log2(x) (формулы для поиска количества ходов поиска, где отвечают только больше, меньше, равно) понял что log2(21)=4,39≈5(округляем до большего, так как меньше 4,39 ходов мы сделать не можем), понял что условие «отличается на 1 от заданного» не влияет(даже чуть ускоряет при очень большом количестае чисел)
Не даёт изменить, но там 4 а не 5, так как когда осталось 3 числа, мы выбираем не по середине, а любое крайнее, тогда робот отвечает равно/отличается на 1/больше/меньше и тогда мы 2 хода ищем, а не в 3
Вас заинтересует
2 года назад
2 года назад
2 года назад
8 лет назад