Теория:
Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки. Правило такого преобразования называется кодом. При решении многих задач используют кодирование. Рассмотрим некоторые из таких задач и вспомним принципы работы с числами, записанными в позиционных системах счисления.
Пример \(1\). Все пятибуквенные слова, составленные из букв К, О, Р, А, записаны в алфавитном порядке. Вот начало списка:
1. ККККК
2. ККККО
3. ККККР
4. ККККА
5. КККОК
…
1. ККККК
2. ККККО
3. ККККР
4. ККККА
5. КККОК
…
Запиши слово, которое стоит на \(144\) месте от начала списка.
Решение: самый простой вариант решения этой задачи — использование системы счисления; здесь расстановка слов в алфавитном порядке равносильна расстановке по возрастанию чисел, записанных в четверичной системе счисления (основание системы счисления равно количеству используемых букв).
- Выполним замену: К — \(0\), О — \(1\), Р — \(2\), А — \(3\); поскольку нумерация слов начинается с \(1\), а первое число KКККК — \(00000\) равно \(0\), под номером \(144\) будет стоять число \(143\), которое нужно перевести в четверичную систему: .
- Так как составляются пятибуквенные слова, а в четверичном числе получилось четыре знака, то допишем незначащий ноль: .
- Выполнив обратную замену (цифр на буквы), получаем слово КРКАА.
Ответ: КРКАА.
Решим обратную задачу.
Пример \(2\). Все четырёхбуквенные слова, составленные из букв Я, К, Л, А, С, записаны в алфавитном порядке и пронумерованы, начиная с \(1\). Начало списка выглядит так:
1. АААА
2. АААК
3. АААЛ
4. АААС
5. АААЯ
6. ААКА
…
1. АААА
2. АААК
3. АААЛ
4. АААС
5. АААЯ
6. ААКА
…
Под каким номером в списке идёт первое слово, которое начинается с буквы Я и в котором две буквы С стоят рядом?
Решение: по аналогии с предыдущим решением будем использовать пятеричную систему счисления. Обрати внимание, что порядок букв должен соответствовать порядку букв в пронумерованном списке.
- Выполним замену: А — \(0\), К — \(1\), Л — \(2\), С — \(3\) и Я — \(4\).
- Слово, которое начинается с буквы Я и в котором две буквы С стоят рядом, запишется в новом коде так: . Переведём это число в десятичную систему:
. - Поскольку нумерация элементов списка начинается с \(1\), а числа в пятеричной системе — с \(0\), к полученному результату нужно прибавить \(1\), получим \(519\).
Ответ: \(519\).
Обрати внимание!
1. Основание системы счисления равно количеству используемых букв.
2. При выполнении замены цифры должны соответствовать порядку букв в пронумерованном списке.
3. Слова в списке нумеруются с единицы, значит, числу \(0\) будет соответствовать первое слово. Поэтому, если мы ищем номер слова, к результату прибавляем \(1\), а если ищем слово, то сначала вычитаем \(1\), а затем выполняем перевод.
2. При выполнении замены цифры должны соответствовать порядку букв в пронумерованном списке.
3. Слова в списке нумеруются с единицы, значит, числу \(0\) будет соответствовать первое слово. Поэтому, если мы ищем номер слова, к результату прибавляем \(1\), а если ищем слово, то сначала вычитаем \(1\), а затем выполняем перевод.
Для вычисления количества информации применяется несколько различных формул в зависимости от ситуации. Вспомним определения.
Алфавит — это набор знаков, используемый в том или ином языке.
Мощность алфавита — это количество используемых в алфавите знаков.
Сообщение — это любая последовательность символов какого-либо алфавита.
Мощность алфавита — это количество используемых в алфавите знаков.
Сообщение — это любая последовательность символов какого-либо алфавита.
Если алфавит языка состоит из \(N\) знаков, то количество различных сообщений длиной \(L\) знаков:
, где
\(Q\) — количество различных сообщений;
\(N\) — мощность алфавита;
\(L\) — длина сообщения.
Например, количество трёхбуквенных сообщений в русском алфавите составляет \(33⋅33⋅33=35~937\).
При дополнительных ограничениях количество возможных знаков в разных позициях сообщения может различаться, поэтому будем использовать формулу:
;
— возможное количество вариантов выбора знака в позиции \(k\).
Например, количество трёхбуквенных сообщений в русском алфавите, которые начинаются с буквы А или О, равно \(2⋅33⋅33=2178\).
При решении сложных комбинаторных задач лучше писать программу на Python для перебора всех возможных комбинаций символов и подсчёта среди них комбинаций, удовлетворяющих заданным условиям.
Пример \(3\). Есения составляет трёхбуквенные слова, в которых встречаются только буквы Я, К, Л, А, С, причём буква С появляется ровно один раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Есения?
Решение: напишем программу, которая будет перебирать трёхбуквенные комбинации символов {Я, К, Л, А, С} и подсчитывать среди них комбинации, где C встречается только один раз.
Т. к. слова состоят из \(3\) символов, мы формируем три вложенных цикла. В каждом цикле перебираем все буквы, которые даны.
Внутри циклов составляем слово и записываем его в переменную \(s\). Таким образом, в переменной \(s\) «прокрутятся» все возможные комбинации.
Подсчитывать будем только те, где всего одна буква C.
Рис. \(1\). Пример решения задачи \(3\)
Ответ: \(48\).
Пример \(4\). Сколько слов длиной \(5\), начинающихся с гласной буквы, можно составить из букв Я, К, Л, А, С? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.
Решение: напишем программу, которая будет перебирать пятибуквенные комбинации символов {Я, К, Л, А, С} и подсчитывать среди них комбинации, которые начинаются с гласных букв.
Рис. \(2\). Пример решения задачи \(4\)
Ответ: \(1250\).
Пример \(5\). Есения составляет четырёхбуквенные коды из букв ЯКЛАСС. Буква А может использоваться в коде не более одного раза, при этом она не может стоять на первом месте, на последнем месте и рядом с буквой Я. Все остальные буквы могут встречаться произвольное количество раз или не встречаться совсем. Сколько различных кодов может составить Есения?
Решение: важно, что буква С в слове «ЯКЛАСС» повторяется. В этом случае мы должны убрать повторение буквы С из перебора.
Рис. \(3\). Пример решения задачи \(5\)
Ответ: \(328\).
Пример \(6\). Сколько существует чисел, шестеричная запись которых содержит \(4\) цифры, причём все цифры различны и никакие две чётные и две нечётные цифры не стоят рядом?
Решение \(1\): выпишем все чётные и нечётные цифры, которые могут использоваться в шестеричной системе счисления:
чётные: \(0\), \(2\), \(4\) — итого \(3\) цифры,
нечётные: \(1\), \(3\), \(5\) — итого \(3\) цифры.
Рассмотрим два случая построения числа.
1) Начиная с чётной цифры. Важно помнить, что первая цифра не может быть равна \(0\) (поэтому на первой позиции \(2\) цифры из \(3\) возможных) и по заданию цифры не могут повторяться (поэтому каждый последующий разряд включает на одну цифру меньше). Изобразим схематично число, указывая сверху возможное количество цифр на разряд:
1) Начиная с чётной цифры. Важно помнить, что первая цифра не может быть равна \(0\) (поэтому на первой позиции \(2\) цифры из \(3\) возможных) и по заданию цифры не могут повторяться (поэтому каждый последующий разряд включает на одну цифру меньше). Изобразим схематично число, указывая сверху возможное количество цифр на разряд:
\(2 3 2 2=2⋅3⋅2⋅2=24\).
чнчн
чнчн
2) Начиная с нечётной цифры. Изобразим схематично число, указывая сверху возможное количество цифр на разряд:
\(3 3 2 2 = 3⋅3⋅2⋅2 = 36\).
нчнч
нчнч
Сложим количество вариантов: \(24+36 = 60\).
Ответ: \(60\).
Решение \(2\): напишем программу. Для определения чётности числа воспользуемся оператором \(\%\), который определяет остаток от деления, а для преобразования символа в число — функцией int(). Число не может начинаться с нуля, поэтому ноль исключим из первого цикла. В теле цикла первое условие проверяет, чтобы каждая цифра встречалась один раз в числе. Второе условие подсчитывает количество вариантов, когда первая цифра чётная, а чётность и нечётность цифр чередуются. Третье условие подсчитывает варианты, когда первая цифра нечётная, а чётность и нечётность цифр чередуются.
Рис. \(4\). Пример решения задачи \(6\)
Ответ: \(60\).