Здравствуйте подскажите пожалуйста как решить эту задачу, и ход мыслей желательно
...34... Введение в динамическое программирование. Python
Калькулятор
Имеется калькулятор, который выполняет три операции:
- прибавить к числу X единицу;
- умножить число X на 2;
- умножить число X на 3.
Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N.
Примеры
Ввод 1
32718
Вывод
17Ввод 2
1
Вывод
0
Вот мой код:
a = float(input())
count = 0
while a != 1:
if (a % 2 == 0 or a % 3 == 0):
if (((a - 1) % 9 == 0) and a % 16 != 0):
a = (a - 1)/9
count += 3
else:
if ((a - 1) % 32 == 0):
a = (a - 1)/32
count += 6
if (a % 16 == 0):
a = a/16
count += 4
if (a % 16 != 0 and a % 2 == 0):
a = a/2
count += 1
if (a % 9 == 0 or a % 3 == 0):
a = a/3
count += 1
else:
if a != 1:
a = a - 1
count += 1
if a == 1:
break
print(count)