Это задача из динамического программирования,т.е или по другому нахождение оптимального решения.Мне понимание динамического программирования плохо дается,прямо стена какая-то.
Понравилась цитата“ Динамическое программирование - это когда задачу,которую не понятно как решать,разбиваешь на более мелкие задачи,которые тоже не понятно как решать”
Вот и берем значит задачу типа
Fiares_Curie
Имеется калькулятор, который выполняет три операции:
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Определите кратчайшую последовательность операций, необходимую для получения из числа 1 заданное число N.
- чтобы получить 1 из 1 то нужно сделать 0 операций.Это понятно
- чтобы получить 2 из 1 то нужно сделать + 1 операцию,т.е. чтобы получить 1 ничего не надо делать,а 2 уже надо одну операцию
- чтобы получить 3 нужно посмотреть сколько мы делали операций чтобы дойти до 2 и прибавить еще одну операцию(+1) = 2 операции “х+1” нужно сделать. НО у нас есть способ x3,т.е нужно проверить можем ли мы из 3 без остатка попасть к 1 (3%3 == 0),тогда чтобы добраться до 3 нам нужна 1 операция (х3),т.е выбираем минимальное количество операций
- чтобы получить 4 из 1 то смотрим сколько операций получили для 3 и прибавим +1 или как случай выше если (4%2 == 0) то понимаем что из количества операций для 2 мы тоже можем сделать +1 одну операцию “х2”
- чтобы получить 5 из 1,то смотрим сколько операций нужно чтобы получить 4 и прибавляем +1,при этом не забываем проверять есть ли (5%2==0 или 5%3==0)
- чтобы получить
n из 1,то смотрим сколько операций нужно для
n-1 + 1,проверяем если
n%2 ==0,то смотрим сколько нужно операций для
n//2 и +1, проверяем если
n%3 == 0, то смотрим сколько нужно операций для
n//3 + 1,из них выбираем минимальное количество операций
для хранения кол-ва операций для каждого числа используем список
num = int(input('>>>'))
a = [0] * (num + 1) # для каждого числа пока заполняем по 0 операций
a[1] = 0 # продублирую для наглядности чтобы получить 1 нужно 0 операций
for n in range(2, num + 1): # для каждого числа из диапазона
minimal = a[n - 1] + 1 # смотрим сколько потребовалось операций для предыдущего и прибавляем
if n % 2 == 0:
minimal = min(minimal, a[n // 2] + 1) # сравниваем сколько операций потребовалось для n//2+1
if n % 3 == 0:
minimal = min(minimal, a[n // 3] + 1) # аналогично
a[n] = minimal # заполняем вместо 0 количество операций
затем восстанавливаем события
расписывать не буду,кому надо разберется
operations = []
i = num
while i > 1:
if a[i] == (a[i-1]+1):
operations.insert(0, 1)
i -= 1
continue
if i%2 == 0 and a[i] == a[i//2]+1:
operations.insert(0, 2)
i //= 2
continue
operations.insert(0, 3)
i //= 3
print(a[num])# минимальное количество операций для num
print(operations)# примененные операции