Загадано число из промежутка от 1 до 64.Какое кол-во информации нужно для угадывания промежутка?

Загадано число из промежутка от 1 до 64.Какое кол-во информации нужно для угадывания промежутка?
Гость
Ответ(ы) на вопрос:
Гость
Самая оптимальная стратегия угадывания - дихотомия, то есть деление отрезка пополам и задавание вопроса больше? (или меньше?)Например, загадано 50Последовательность32   64/2            больше48   (32+64)/2   больше56   (48+64)/2   меньше52   (48+56)/2   меньше50   (48+52)/2   попал Теперь о задаче. Вопрос очень некорректный, если бы он звучал, как сколько попыток нужно сделать, чтобы угадать? , то решение простое64 = 2^6, поэтому нужно 6 попыток 6 = 110b, значит 3 бит достаточно, чтобы в них разместить это количество попыток.НО в задаче вопрос-то другой! Потому что в процессе отгадывания на каждом шаге нужно знать 1. Концы отрезка, 2. ОтветКонцы это 6 бит и 6 бит +ответ 1 бит, итого 13 бит на шаг *6 = 78 бит. Можно ещё сократить немного, так как в последующем вопросе используется информация из предыдущего(один из концов интервала).Уточни, что имеется в виду под фразой "какое количество информации", иначе задача неопределена и допускает многочисленные толкования.
Гость
62=2^6 Значит,любое загаданное число можно отгадать за 6 раз.
Не нашли ответ?
Ответить на вопрос
Похожие вопросы