Question

за один ход разрешается прибавить к числу 2 или умножить его на 3 за Какое наименьшее число ходов можно из одного получить 315 ​

Answer 1

1×3×3×3×3×3+2×3×3×3+2×3×3=315

Answer 2

Для нахождения наименьшего числа ходов, чтобы получить число 315, можно использовать алгоритм поиска в ширину (BFS) или динамическое программирование. Однако, для данной задачи можно использовать метод обратного прохода, который позволит найти решение за O(log n), где n - исходное число.

1. Из числа 315 делаем обратный проход к исходному числу.
2. Если число четное, делим его на 2 (обратное действие от умножения на 3).
3. Если число нечетное, вычитаем из него 1 (обратное действие от прибавления 2).
4. Повторяем шаги 2 и 3 до тех пор, пока не вернемся к исходному числу.

Давайте проделаем шаги:

315 (исходное число) ->

314 (так как четное, делим на 2) ->

157 (так как нечетное, вычитаем 1) ->

156 (так как четное, делим на 2) ->

78 (так как четное, делим на 2) ->

39 (так как нечетное, вычитаем 1) ->

38 (так как четное, делим на 2) ->

19 (так как нечетное, вычитаем 1) ->

18 (так как четное, делим на 2) ->

9 (так как нечетное, вычитаем 1) ->

8 (так как четное, делим на 2) ->

4 (так как четное, делим на 2) ->

2 (так как четное, делим на 2) ->

1 (так как нечетное, вычитаем 1).

Теперь мы вернулись к исходному числу 1, и потребовалось 13 шагов, чтобы пройти от 1 до 315, используя только прибавление 2 и умножение на 3.

Ответ: наименьшее число ходов для получения 315 составляет 13.