Задание №4: Кодирование по условию Фано
Задано: сообщения содержат буквы из набора {а, з, к, н, и, ч}. Используется двоичный код, удовлетворяющий условию Фано (никакое кодовое слово не является началом другого). Известны кодовые слова для букв «н» (1111) и «з» (11). Необходимо найти кодовые слова для букв «а», «к» и «ч», минимизирующие количество двоичных знаков для кодирования слова «казачка».
Для букв «а», «к» и «ч» нужно найти кодовые слова, удовлетворяющие условию Фано и имеющие минимальную длину. Буква «а» встречается трижды, поэтому ей нужно присвоить кратчайшее кодовое слово. Выберем «0».
Построим бинарное дерево, начиная с «1» (так как «0» уже используется, а начало с «0» нарушит условие Фано для «з» и «н»). Для буквы «н» (1111) используем ветку из четырёх единиц. Буква «к» встречается дважды, поэтому ей присвоим кодовое слово «10». Остаётся одна ветка для «ч» – «110».
Полученные кодовые слова: а – 0, к – 10, ч – 110, з – 11, н – 1111.
Подсчитаем общее количество двоичных знаков для слова «казачка»: 1 + 2 + 0 + 1 + 4 + 2 + 0 + 1 = 11.
Задание №8: Перестановки и комбинаторика в Python
Ася составляет 7-буквенные слова из букв слова «самокат». Буквы могут повторяться. Необходимо найти количество слов, содержащих комбинацию «сам» ровно один раз, где слева и справа от «сам» находятся одинаковые гласные.
Используем модуль itertools и функцию product для генерации всех возможных 7-буквенных комбинаций из букв слова «самокат». Для исключения дубликатов используем множество. Из каждой комбинации формируем строку с помощью метода join.
Ищем индекс комбинации «сам» с помощью метода index. Условие: индекс не должен быть равен 0 (комбинация не в начале слова) и 4 (комбинация не в конце слова). Символы слева и справа от «сам» должны быть одинаковыми гласными (а или о).
Если все условия соблюдены, добавляем слово в множество. Количество элементов в множестве – искомый ответ (216).
Задание: Семизначные числа
Сергей составляет семизначные десятичные числа, где вторая и третья цифры – квадрат первой, а перед последней цифрой записан куб последней.
Используем функцию product для генерации всех возможных семизначных чисел. Проверяем условия:
- Первая цифра не равна нулю.
- Вторая и третья цифры равны квадрату первой.
- Перед последней цифрой стоит куб последней (куб может занимать 1, 2 или 3 позиции).
Подсчитываем количество подходящих чисел (2925).
Задание: Символьные последовательности
Сколько существует символьных последовательностей длины 3 в четырёхбуквенном алфавите {A, B, C, D}, если одним из соседей A обязательно является D, а B и C никогда не соседствуют?
Используем функцию product. Проверяем условия:
- B и C не соседствуют.
- Количество A не превышает количество комбинаций AD или DA.
Подсчитываем количество подходящих последовательностей (29).
Задание №15: Поразрядная конъюнкция
Найти минимальное натуральное значение параметра a, при котором выражение истинно при любом значении x:
(x & 57) != 0) | ((x & 38) != 0) | ((x & 9) == 0) | ((x & a) == 0)
Выносим выражение в отдельную функцию. Перебираем натуральные значения a и проверяем выражение для диапазона значений x (например, от -1000 до 1000). Выводим минимальное значение a, при котором функция возвращает True для всех x (2).
Задание №16: Рекурсия
Дано рекуррентное соотношение:
f(0) = 0 f(n) = f(n-1) + 1, если n нечетное f(n) = f(n/2), если n четное
Найти количество значений n меньше, чем некоторого большого числа, для которых f(n) = 3.
Анализ показывает, что f(n) равно количеству единиц в двоичном представлении n. Необходимо найти количество чисел с тремя единицами в двоичном представлении. Подсчитываем число сочетаний из 30 по 3 (30 – количество знаков в двоичном представлении большого числа, 3 – количество единиц): 4060.
Задание: Рекурсия и анализ выражения
Дано рекуррентное соотношение (другое, чем в предыдущем задании). Необходимо найти значение выражения:
12445 * (f(10000) — f(12000)) / f(11000) + 101
Анализ выражения показывает, что f(10000) — f(12000) сокращается с f(11000), оставляя 1. Результат: 2446.