Кодирование данных, комбинаторика, системы счисления

Что нужно знать:
• русский алфавит
• принципы работы с числами, записанными в позиционных системах счисления
• если слово состоит из L букв, причем есть n1 вариантов выбора первой буквы, n2 вариантов выбора второй буквы и т.д., то число возможных слов вычисляется как произведение
N = n1 · n2 · … · nL
• если слово состоит из L букв, причем каждая буква может быть выбрана n способами, то число возможных слов вычисляется как N = nL

Р-06. Вася составляет 5-буквенные слова, в которых есть только буквы С, Л, О, Н, причём буква С используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
Решение:
буква С может стоять на одном из пяти мест: С****, *С***, **С**, ***С* и ****С, где * обозначает любой из оставшихся трёх символов
в каждом случае в остальных четырёх позициях может быть любая из трёх букв Л, О, Н, поэтому при заданном расположении буквы С имеем 34 = 81 вариант
всего вариантов 5 · 81 = 405.
Ответ: 405.

Р-05. Сколько существует различных символьных последовательностей длины 5 в четырёхбуквенном алфавите {A, C, G, T}, которые содержат ровно две буквы A?
Решение (вариант 1, перебор):
1) рассмотрим различные варианты слов из 5 букв, которые содержат две буквы А и начинаются с А:
АА*** А*А** А**А* А***А
Здесь звёздочка обозначает любой символ из набора {C, G, T}, то есть один из трёх символов.
2) итак, в каждом шаблоне есть 3 позиции, каждую из которых можно заполнить тремя способами, поэтому общее число комбинаций (для каждого шаблона!) равно 33 = 27
3) 4 шаблона, когда на первом месте стоит буква А, они дают 4 · 27 = 108 комбинаций

4) теперь рассматриваем шаблоны, где первая по счёту буква А стоит на второй позиции, их всего три:
*АА** *А*А* *А**А
они дают 3 · 27 = 81 комбинацию
5) два шаблона, где первая по счёту буква А стоит на третьей позиции:
**АА* **А*А
они дают 2 · 27 = 54 комбинации
6) и один шаблон, где сочетание АА стоит в конце
***АА
они дают 27 комбинаций
7) всего получаем (4 + 3 + 2 + 1) · 27 = 270 комбинаций
ответ: 270.

Р-04. Сколько слов длины 5, начинающихся с гласной буквы, можно составить из букв Е, Г, Э? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.
Решение:
1) первая буква слова может быть выбрана двумя способами (Е или Э), остальные – тремя
2) общее число различных слов равно 2*3*3*3*3 = 162
ответ: 162.

Р-03. Все 4-буквенные слова, составленные из букв К, Л, Р, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. КККК
2. КККЛ
3. КККР
4. КККТ
……
Запишите слово, которое стоит на 67-м месте от начала списка.

Решение:
1) самый простой вариант решения этой задачи – использование систем счисления; действительно, здесь расстановка слов в алфавитном порядке равносильна расстановке по возрастанию чисел, записанных в четверичной системе счисления (основание системы счисления равно количеству используемых букв)
2) выполним замену К→0, Л→1, Р→2, Т→3; поскольку нумерация слов начинается с единицы, а первое число КККК→0000 равно 0, под номером 67 будет стоять число 66, которое нужно перевести в четверичную систему: 66 = 10024
3) Выполнив обратную замену (цифр на буквы), получаем слово ЛККР.
Ответ: ЛККР.

Р-02. Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке.
Вот начало списка:
1. ААААА
2. ААААО
3. ААААУ
4. АААОА
……
Запишите слово, которое стоит на 240-м месте от начала списка.

Решение (троичная система, идея М. Густокашина):
по условию задачи важно только то, что используется набор из трех разных символов, для которых задан порядок (алфавитный); поэтому для вычислений можно использовать три любые символа, например, цифры 0, 1 и 2 (для них порядок очевиден – по возрастанию)
выпишем начало списка, заменив буквы на цифры:
1. 00000
2. 00001
3. 00002
4. 00010
……

это напоминает (в самом деле, так оно и есть!) числа, записанные в троичной системе счисления в порядке возрастания: на первом месте стоит число 0, на втором – 1 и т.д.
тогда легко понять, что 240-м месте стоит число 239, записанное в троичной системе счисления
переведем 239 в троичную систему: 239 = 222123
заменяем обратно цифры на буквы: 22212 → УУУОУ
Ответ: УУУОУ.

Р-01. Все 5-буквенные слова, составленные из 5 букв А, К, Л, О, Ш, записаны в алфавитном порядке.
Вот начало списка:
1. ААААА
2. ААААК
3. ААААЛ
4. ААААО
5. ААААШ
6. АААКА
……
На каком месте от начала списка стоит слово ШКОЛА?

Решение:
1) по аналогии с предыдущим решением будем использовать пятеричную систему счисления с заменой А → 0, К → 1, Л → 2, О → 3 и Ш → 4
2) слово ШКОЛА запишется в новом коде так: 413205
3) переводим это число в десятичную систему:
413205 = 4·54 + 1·53 + 3·52 + 2·51 = 2710
4) поскольку нумерация элементов списка начинается с 1, а числа в пятеричной системе – с нуля, к полученному результату нужно прибавить 1, тогда…
Ответ: 2711.

Р-00. Все 5-буквенные слова, составленные из букв А, О, У, записаны в обратном алфавитном порядке. Вот начало списка:
1. УУУУУ
2. УУУУО
3. УУУУА
4. УУУОУ
……
Запишите слово, которое стоит на 240-м месте от начала списка.

Решение:
по условию задачи важно только то, что используется набор из трех разных символов, для которых задан порядок (алфавитный); поэтому для вычислений можно использовать три любые символа, например, цифры 0, 1 и 2 (для них порядок очевиден – по возрастанию)
выпишем начало списка, заменив буквы на цифры так, чтобы порядок символов был обратный алфавитный (У → 0, О → 1, А → 2):
1. 00000
2. 00001
3. 00002
4. 00010
……