Условие задачи
Ученики школы «Будущее» уже с младших классов много времени и сил отдают программированию. Сначала на площадке Яндекс.Учебник они проходят базовые алгоритмы с исполнителем «Робот», затем на ней же осваивают язык программирования Python.
Чтобы младшеклассникам было интереснее проходить алгоритмы, ученики 9 «П» класса сделали настоящего робота и подготовили для него специальное поле. Управляют роботом командами с компьютера.
Первая версия робота могла только двигаться в четырех направлениях, и ученики использовали равномерное кодирование для передачи команд роботу.
Во второй версии робота количество передаваемых команд увеличилось (несколько команд ученики даже зарезервировали на будущее). Было решено перейти к неравномерному кодированию. Чтобы узнать частоты использования команд для исполнителя, ученики 9 «П» провели исследование.
Итогом стала таблица:
Постройте оптимальный неравномерный код, удовлетворяющий условию Фано по таблице с частотами команд. Код должен включать резервные команды.
Сколько бит потребуется для кодирования следующей программы исполнителя «Робот»?
move_up()
move_up()
move_right()
fill_cell()
move_right()
fill_cell()
Ответ
Команды выписываем в таблицу в порядке убывания частот. Затем их разделяем на две группы так, чтобы суммы часто в каждой из групп были бы по возможности одинаковыми. Всем командам верхней половины в качестве первого символа записывается 1, а всем нижним 0. Каждая ...
