Как решить задачу калькулятор на питон

Question

Здравствуйте подскажите пожалуйста как решить эту задачу, и ход мыслей желательно

...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)

Answer 1

Ход мыслей такой: надо придумать функцию которая решает задачу. Затем её запрограммировать.

f(n) - минимальное чиcло шагов для получения n из единицы. Что про неё можно сказать?

f(1) = 0 - это я думаю объяснять не нужно.
f(k + 1) <= 1 + f(k) - f(k + 1) не может быть больше, иначе нарушится требование минимальности (обоснование опущено, но вы должны это хорошо понимать);
f(2k) <= 1 + f(k) - следущее правило, обоснование аналогично;
f(3k) <= 1 + f(k) - аналогично.

Все условия переведены на язык формул. Надо написать функцию f:

f(1) = 0
если k делится на 2 и на 3 то f(k) = 1 + min(f(k - 1), f(k / 2), f(k / 3))
если k делится на 2 и не делится на 3 то f(k) = 1 + min(f(k - 1), f(k / 2))
и так далее ...

Код:

def f(n):
    if n == 1:
        return 0
    v = f(n - 1)
    if n % 2 == 0:
        v = min(v, f(n // 2))
    if n % 3 == 0:
        v = min(v, f(n // 3))
    return v + 1


print(f(int(input())))

Для маленьких n работает хорошо, после сотни тормозит, для больших чисел падает с переполнением стека. Теория хороша, практика не очень.

Проблема в том что мы очень много раз вычисляем одни и те же значения f(n). Можно сделать оценку, что количество вызовов растет как e^n. Чтобы избавится от повторных вызовов, значения функции надо запоминать в кэше:

import functools


@functools.lru_cache(None)
def f(n):
    if n == 1:
        return 0
    v = f(n - 1)
    if n % 2 == 0:
        v = min(v, f(n // 2))
    if n % 3 == 0:
        v = min(v, f(n // 3))
    return v + 1


print(f(int(input())))

Кэш всё ускоряет, но проблема с глубиной рекурсии остаётся. Чиним её: вычисляем значения f последовательно от единицы до n, вычисленные значения храним в списке cache и используем по необходимости. Рекурсии нет и нет проблем с её глубиной:

def f(n):
    cache = [0] * (n + 1)
    for i in range(2, n + 1):
        v = cache[i - 1]
        if i % 2 == 0:
            v = min(v, cache[i // 2])
        if i % 3 == 0:
            v = min(v, cache[i // 3])
        cache[i] = v + 1
    return cache[-1]


print(f(int(input())))

Answer 2

for m in range(2, 1000, 2):
    for n in range(1, 1001, 2):
        if 200_000_000 < 2**m * 3**n < 4_000_000:
            print(2**m * 3**n)

БЛОГ НА HUSL

Как решить задачу калькулятор на питон

Ответы (2 шт):