Question

К начальному числу единице можно прибавить единицу, умножить на два, умножить на три. На каждом последующем шаге можно выполнять только эти три операции. Определить за какое минимальное число шагов можно достичь произвольно введенного числа N. До предела умножать на три , потом на два и добавлять единицами не оптимальный к сожалению алгоритм. Нужна либо формула, либо алгоритм (словами ! ) , либо программа на Питон.

Answer 1

N = int(input())

dp = [100000000 for i in range(N + 2)]

dp[1] = 0

for i in range(2, N + 1):

    dp[i] = dp[i - 1] + 1

    if i % 2 == 0 and dp[i // 2] != 100000000:

       dp[i] = min(dp[i], dp[i // 2] + 1)

    elif i % 3 == 0 and dp[i // 3] != 100000000:

       dp[i] = min(dp[i], dp[i // 3] + 1)

print(dp[N])

Answer 2

Для решения этой задачи можно использовать жадный алгоритм. Вам нужно начать с числа 1 и последовательно применять операции прибавления единицы, умножения на два и умножения на три, чтобы приближаться к заданному числу N. Вот пример алгоритма на Python:

pythonCopy code
def minimize_steps_to_N(N):
    current_number = 1
    steps = 0

    while current_number < N:
        # Если умножение на 3 приближает нас к N, то используем его
        if current_number * 3 <= N:
            current_number *= 3
        # В противном случае, если умножение на 2 приближает нас к N, то используем его
        elif current_number * 2 <= N:
            current_number *= 2
        # В противном случае, прибавляем 1
        else:
            current_number += 1

        steps += 1

    return steps

# Введите ваше число N
N = int(input("Введите число N: "))
steps = minimize_steps_to_N(N)
print(f"Минимальное количество шагов для достижения {N} равно {steps}")

Этот код будет последовательно применять операции, чтобы приближаться к числу N, и считать количество шагов, необходимых для достижения N.