С числом можно проделавать 2 типа операции: операция А умножает число ** 2, операция В...

Question

С числом можно проделавать 2 типа операции: операция А умножает число на 2, операция В вычитает 3. Как из 11 при помощи этих операций получить 25 за наименьшее количество ходов? В ответ напишите последовательность
операций (например последовательность операций АААВВВВВВВВВВВВВВВВВВВВВ за 24 хода достигает результата).

Answer 1

Проделаем "улучшенный перебор". Будем строить решение с конца (с числа 25) в виде ориентированного дерева, каждой вершине которого приписано некоторое число. Корень - число 25. У каждого узла до двух потомков: одно число получается делением на 2 (обратное действие к A. Тогда дуге приписываем букву A), другое - прибавлением 3 (обратное действие к B, тогда дуге приписываем букву B).
Заметим, что в случае, если в узле нечетное число, то потомок может быть только второй. Также если где-то на более высоком слое дерева было такое же число, как в данном узле, то его потомков можно не рассматривать (путь из корня через данную вершину будет иметь не наименьшую длину).
Заканчиваем, когда встретим число 11. В ответ записываем буквы, написанные на дугах в обратном пооядке (путь от 25 до 11 в обратном порядке)

Получаем ответ BBABAAB

---