Задано число из промежутка от 1 до 64. Какое количество информации необходимо для угадывания числа из этого промежутка?
10-11 класс
|
Самая оптимальная стратегия угадывания - дихотомия, то есть деление отрезка пополам и задавание вопроса больше? (или меньше?)
Например, загадано 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 бит. Можно ещё сократить немного, так как в последующем вопросе используется информация из предыдущего(один из концов интервала).
Уточни, что имеется в виду под фразой "какое количество информации", иначе задача неопределена и допускает многочисленные толкования.
Процес угадывания, т.е нет факта что произошло угадывание, просто факт действия, удачный или нет.
64 = 2 в ст. 6
6 бит на одну попытку
Другие вопросы из категории
Нужна блок-схема и программа в паскале.
Задание прикреплено
(укажите несколько правильных ответов)
1) перемещение данных на самый высокии уровень
2) перемещение данных на самый низкии уровень
3) перемещение данных с более высоко уровня на более низкий
4) перемещение данных с более низкого уровня на более высокии
5) удаление данных с физического носителя
Читайте также
31, мм - целое число из диапазона от 1 до 12, а гг - целое число из диапазона от 1 до 2020 (если какая-то часть формата нарушена, то данная подстрока в качестве даты не рассматривается.) Заменить каждую дату сообщения на дату следующего дня. Написать программу на Паскале. Сроооооооооооооочнооо. Пооожалуйста.....