Некоторые задания:
4. По каналу связи передаются сообщения, содержащие только буквы, входящие в слово ИНФОРМАТИКА. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано: никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Ф – 010, Р – 011, М – 101, Т – 1101, К – 111.
Какое наименьшее число двоичных знаков может содержать код слова ИНФОРМАТИКА?
Ответ: ___________________________.
5. Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. В конец двоичной записи добавляется двоичный код остатка от деления числа N на 4.
3. Результатом работы алгоритма становится десятичная запись полученного числа R.
Пример 1. Дано число N = 13. Алгоритм работает следующим образом.
1. Строим двоичную запись: 1310 = 11012.
2. Остаток от деления 13 на 4 равен 1, добавляем к двоичной записи цифру 1, получаем 110112 = 2710.
3. Результат работы алгоритма R = 27.
Пример 2. Дано число N = 14. Алгоритм работает следующим образом.
1. Строим двоичную запись: 1410 = 11102.
2. Остаток от деления 14 на 4 равен 2, добавляем к двоичной записи цифры 10 (102 = 210), получаем 1110102 = 5810.
3. Результат работы алгоритма R = 58.
Назовем доступными числа, которые могут получиться в результате работы этого алгоритма. Например, числа 27 и 58 – доступные.
Какое наибольшее количество доступных чисел может быть на отрезке, содержащем 49 натуральных чисел?
Ответ: ___________________________.
6. Исполнитель Черепаха передвигается по плоскости и оставляет след в виде линии. Черепаха может выполнять две команды: Вперёд n (n – число) и Направо m (m – число). По команде Вперёд n Черепаха перемещается вперёд на n единиц. По команде Направо m Черепаха поворачивается на месте на m градусов по часовой стрелке, при этом соответственно меняется направление дальнейшего движения.
В начальный момент Черепаха находится в начале координат и направлена вверх (вдоль положительного направления оси ординат).
Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что заданная последовательность из S команд повторится k раз.
Черепаха выполнила следующую программу:
Повтори 4 [Вперёд 14 Направо 90]
Повтори 5 [Вперёд 5 Направо 45]
Определите, сколько различных точек с целочисленными координатами будет находиться на линиях, полученных при выполнении данной программы.
Ответ: ___________________________.
7. Камера наблюдения каждые n секунд (n – целое число) делает фотографию с разрешением 1024×768 пикселей и палитрой 4096 цветов. Фотографии передаются по каналу с пропускной способностью 200 Кбайт/сек, при этом используются методы сжатия, позволяющие уменьшить размер изображения в среднем на 20 %.
Определите минимально возможное значение n, при котором возможна передача в режиме реального времени.
Ответ: ___________________________.
8. Сколько существует 11-значных девятеричных чисел, в записи которых не встречается цифра 0, любые две соседние цифры имеют разную чётность, и никакая цифра не повторяется больше 4 раз?
Ответ: ___________________________.
