Алгоритм поиска возможных способов простого многократного шифрования с помощью алфавита

Question

При использовании простого метода шифрования, в котором буквы заменяются индексными номерами алфавита, существует несколько способов их расшифровки, например. ABOR 121518, но 121518 также может быть AYEAH или LAER.

Ну, мне нужен алгоритм, чтобы рассчитать, сколько возможных способов для данного числа расшифровать сообщение описанным способом (например, 1225 имеет 5 - ABBE, AVE, ABY, LBE, LY).

Помоги мне, если хочешь.

Answer 1

Вы можете сделать это рекурсивно.

Общее количество способов кодирования первых n цифр равно (количество способов кодирования первых n-1 цифр, если последняя цифра равна 1 <= d <= 9) + (количество способов кодирования первых n-2 цифр, если последние две цифры 10 <= dd <= 26). </p>

Кэшировать результаты или использовать динамическое программирование для предотвращения экспоненциального взрыва.Техника очень похожа на вычисление чисел Фибоначчи.

Вот как вы можете сделать это в Python, чтобы продемонстрировать принцип:

# s is of form [1-9][0-9]*
s = '121518'
a=1 # Cache of f(i - 2)
b=1 # Cache of f(i - 1)
for i in range(1, len(s)):
   a, b = b, a * (10 <= int(s[i - 1: i + 1]) <= 26) + b * (s[i] != '0')
print b

Вы можете сделать это аналогичным образом в C ++,но так как это, кажется, домашнее задание / учебное упражнение, я надеюсь, вы не возражаете, что я оставлю вас для проработки деталей в C ++.