Рассмотрим несколько заданий по информатике из ЕГЭ-2022, присланных подписчиками.
Задание №4: Кодирование по Фано
Дано 6 букв: А, В, Г, О, С, Т. Известны кодовые слова для некоторых букв: Т (10), У (30), С (11), А (001). Необходимо найти кодовые слова для букв В и Г, удовлетворяющие условию Фано, и указать наименьшую возможную длину закодированной последовательности для слова «СУСТАВ».
Строим бинарное дерево. Так как кодовые слова Т (10) и С (11) начинаются с 1, для остальных букв кодовые слова должны начинаются с 0. Получаем: А (001), В (010), Г (011).
Длина кодирования слова «СУСТАВ»:
- С — 2 символа
- У — 3 символа
- С — 2 символа
- Т — 2 символа
- А — 3 символа
- В — 3 символа
Итоговая длина: 15 символов.
Задание №5: Алгоритм обработки числа
Алгоритм обработки числа N:
- Строится двоичная запись числа N.
- Справа дописывается 0, если в числе единиц больше, чем нулей, и 1 в противном случае.
- Если количество разрядов чётное, убираются 2 средних разряда; если нечётное — 3 средних разряда.
- Полученное число переводится в десятичную систему.
Необходимо найти количество различных значений N на отрезке [50, 100] включительно, которые могут получиться в результате работы алгоритма. Алгоритм реализован с использованием цикла, перебирающего числа. Количество различных результатов сохраняется в множестве. Результат: 13.
Задание №8: Комбинаторика и коды
Руслан составляет 5-буквенные коды из букв слова «РУСЛАН». Гласные буквы (А, У) могут входить в код не более одного раза. Сколько кодов может составить Руслан? Используется функция, генерирующая все возможные комбинации. Далее перебираются комбинации, проверяется количество гласных и считается количество подходящих кодов.
Задание №9: Позиция комбинации в списке
Мария составляет 4-буквенные комбинации из букв слова «МАРИЯ». Найти позицию комбинации «ОРИМ» в алфавитном списке. Создаётся список всех 4-буквенных комбинаций из букв «МАРИЯ» в алфавитном порядке. Используется метод для нахождения позиции комбинации «ОРИМ». Результат: 85.
Задание №26: Анализ пар чисел в файле
В файле записан набор натуральных чисел, не превышающих 10<sup>9</sup>. Все числа различны. Необходимо определить количество пар чисел с одинаковой чётностью, сумма которых также присутствует в наборе. Найти максимальную сумму таких пар. Оптимизированный вариант использует словарь для ускорения поиска. Результат: 10 пар, максимальная сумма — … (значение из файла).
Задание №16: Вычисление функции и количество цифр
Задана функция F(n) с рекурсивным определением. Необходимо найти количество различных цифр в целой части F(15). Функция F(n) реализована рекурсивно. Целая часть F(15) вычисляется и преобразуется в строку. Для нахождения количества различных цифр используется множество. Результат: 3.