Некоторые задания:
1. На рисунке схема дорог изображена в виде графа, в таблице звёздочками обозначено наличие дороги между населёнными пунктами. Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Выпишите последовательно без пробелов и знаков препинания указанные на графе буквенные обозначения пунктов от П1 до П8: сначала букву, соответствующую П1, затем букву, соответствующую П2, и т. д.
4. Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известно, что слово МАЛИНА кодируется как 011100011011110. Какой код соответствует слову НИЛ?
5. Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом:
1. Строится двоичная запись числа N.
2. Подсчитывается количество чётных и нечётных цифр в десятичной записи заданного числа. Если в десятичной записи больше чётных цифр, то в конец двоичной записи дописывается 1, если нечётных – 0. Если чётных и нечётных цифр в десятичной записи поровну, то в конец двоичной записи дописывается 0, если данное число чётное, и 1 – если нечётное. 3–4. Пункт 2 повторяется для вновь полученных чисел ещё два раза. 5. Результатом работы алгоритма становится десятичная запись полученного числа R.
Пример. Дано число N = 14. Алгоритм работает следующим образом:
1. Строим двоичную запись: 1410 = 11102.
2. В записи числа 14 чётных и нечётных цифр поровну. Число 14 чётное, дописываем к двоичной записи 0, получаем 111002 = 2810.
3. В записи числа 28 чётных цифр больше, дописываем к двоичной записи 1, получаем 1110012 = 5710.
4. В записи числа 57 нечётных цифр больше, дописываем к двоичной записи 0, получаем 11100102 = 11410.
5. Результат работы алгоритма R = 114. Определите количество принадлежащих отрезку [123 455; 987 654 321] чисел, которые могут получиться в результате работы этого алгоритма.
7. Книгу объёмом 1 Мбайт записали как аудиокнигу. Запись велась в формате стерео (2 канала) с частотой 32 кГц и разрешением 16 бит. За одну минуту записывалось в среднем 1,5 Кбайт текста. Сжатие данных позволило сократить размер полученного звукового файла на 80 %. Для удобства использования запись разделили на фрагменты со средним размером 20 Мбайт. Определите количество полученных фрагментов.
8. Митрофан составляет коды из букв, входящих в слово МИТРОФАН. Код должен состоять из 6 букв, буквы в коде не должны повторяться, согласных в коде должно быть больше, чем гласных, две гласные буквы нельзя ставить рядом. Сколько кодов может составить Митрофан?
10. Определите, сколько раз в тексте романа Михаила Булгакова «Мастер и Маргарита» встречается слово «зима» и производные от него в любой форме.
11. В информационной системе хранится информация об объектах определённой структуры. Описание каждого объекта включает в себя идентификатор объекта, описание структуры объекта и дополнительную информацию. Идентификатор объекта состоит из 9 заглавных латинских букв. Каждая буква идентификатора кодируется минимально возможным числом битов, а для хранения всего идентификатора отводится минимально возможное целое число байтов. Структура объекта описывается как последовательность простых элементов. Всего существует 1984 различных простых элемента. Каждый простой элемент кодируется одинаковым для всех элементов минимально возможным количеством битов. Для описания структуры объекта выделяется одинаковое для всех объектов минимальное количество байтов, достаточное для записи 50 простых элементов. Для хранения дополнительной информации выделяется одинаковое для всех объектов целое число байтов. Известно, что для хранения данных о 32 768 объектах потребовалось 4 Мбайт. Сколько байтов выделено для хранения дополнительной информации об одном объекте? В ответе запишите целое число – количество байт.
