Для передачи сообщения используется цифровая клавиатура (см. рисунок) и следующий алгоритм шифрования: каждый символ кодируется последовательностью из 3-х цифр. При этом, последовательность не может начинаться с 1 и 9, двигаться между клавишами можно только по правилам шахматного коня.
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
0 |
|
Рисунок. Цифровая панель
Алфавит какой длины можно использовать при таком алгоритме шифрования?
Длина алфавита определяется количеством различных комбинаций из трех цифр, которые можно получить из панели с учетом правил и ограничений их построения. Правило шахматного коня определяет порядок перехода от одной цифры к другой (см. рисунок 3.2-1)
Рисунок 3.2-1 – Правило шахматного коня
Существует два варианта решения:
1. Перебор всех комбинаций вручную.
2. Автоматическое построение комбинаций с использованием графа переходов.
Способ 1.
Для поиска всех возможных комбинаций необходимо построить варианты перехода из каждой цифры клавиатуры. Возможные переходы:
1: 6, 8
2: 9,7
3: 4, 8
4: 0, 3, 9
5: пусто
6: 0, 1, 7
7: 2, 6
8: 1, 3
9: 2, 4
0: 6,4
Далее необходимо построить таблицу со всеми возможными комбинациями
Всего 46 комбинаций. В задании указано, что комбинация не может начинаться с 1 (5 комбинаций) и с 9 (5 комбинаций).
Ответ: 46–5–5 = 36 комбинаций.
Способ 2.
Необходимо задать матрицу переходов (двумерный массив), после чего осуществить перебор всех возможных трехзначных путей.
Пример задания матрицы на основе словаря на языке программирования Python представлен в листинге 3.2-1.
Листинг 3.2-1 – Матрица переходов на основе словаря на языке программирования Python
# матрица переходов
turns = {0: [4, 6], # переход из 0
1: [6, 8], # переход из 1
2: [7, 9], # переход из 2
3: [4, 8], # переход из 3
4: [3, 9, 0], # переход из 4
5: [], # переход из 5
6: [1, 7, 0], # переход из 6
7: [2, 6], # переход из 7
8: [1, 3], # переход из 8
9: [2, 4] # переход из 9
}
Подсчет числа комбинаций можно реализовать следующим образом:
1) Организовать цикл, в котором перебирать все возможные цифры на первом месте комбинации.
2) Для каждой первой цифры из матрицы переходов получить массив цифр для второй позиции в комбинации.
3) В цикле перебирать цифры для второй позиции, для каждой из которых определять количество цифр для третьей позиции в комбинации. Полученное число добавлять в общий список числа комбинаций.
Пример реализации такой программы на языке программирования Python представлен в листинге 3.2-2.
Листинг 3.2-2 – Реализации программы подсчета общего числа комбинаций на языке программирования Python
# счетчик комбинаций
cnt = 0
# сама комбинация
combo = [0, 0, 0]
# перебираем первую цифру
for a in range(10):
# пропускаем цифры 1 и 9
if a == 1 or a == 9:
continue
combo[0] = a
# массив для второй цифры
array2 = turns[a]
# перебираем все комбинации для второй цифры
# из матрицы переходов
for b in array2:
combo[1] = b
# массив для третьей цифры
array3 = turns[b]
# добавляем к результату число переходов из второй цифры
cnt += len(array3)
# перебираем все комбинации для третьей цифры
# из матрицы переходов для вывода на экран
for c in array3:
combo[2] = c
print(combo)
# вывод общего числа комбинаций на экран
print(cnt)
В результате выполнения программа выводит на экран следующее.
[0, 4, 3]
[0, 4, 9]
[0, 4, 0]
[0, 6, 1]
[0, 6, 7]
[0, 6, 0]
[2, 7, 2]
[2, 7, 6]
[2, 9, 2]
[2, 9, 4]
[3, 4, 3]
[3, 4, 9]
[3, 4, 0]
[3, 8, 1]
[3, 8, 3]
[4, 3, 4]
[4, 3, 8]
[4, 9, 2]
[4, 9, 4]
[4, 0, 4]
[4, 0, 6]
[6, 1, 6]
[6, 1, 8]
[6, 7, 2]
[6, 7, 6]
[6, 0, 4]
[6, 0, 6]
[7, 2, 7]
[7, 2, 9]
[7, 6, 1]
[7, 6, 7]
[7, 6, 0]
[8, 1, 6]
[8, 1, 8]
[8, 3, 4]
[8, 3, 8]
36
Ответ – 36 комбинаций.