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