Уменьшающееся число в Python (задача)

Question

Над заданым число можно проводить несколько операций:

Если число делиться на 3, то поделить число на 3.
Если число делиться на 2, то поделить число на 2
Вычесть 1

По заданому числу n найти найменьшее число операций после выполнения которых получиться 1 Каждая строка должна содержать одно натуральное число. Проблема в том что у меня запускаеться код но выводит количество операций 1 для всех чисел(

Ввод:

1
5
10

Вывод:

0
3
3

Мой пример кода:

def third(number, heart):
    number = number / 3
    heart =+ 1
    print(heart)

def second(number,heart):
    number = number / 2
    heart =+ 1
    print(heart)

def one(number,heart):
    number = number - 1
    heart =+ 1
    print(heart)

def app(number,heart):
    while (number != 1):
        if (number%3) == 0:
            third(number, heart)
        elif (number%2) == 0:
            second(number,heart)
        else:
            one(number,heart)

        break
heart = 0
n = int(input())
a = int(input())
b = int(input())
app(n, heart)
app(a, heart)
app(b, heart)

Answer 1

В вашем коде переменная heart всегда равна 1, потому что вместо += вы используете =+, то есть присваиваете переменной значение +1=1. Если данная задача является олимпиадной и n довольно большое, то нужно использовать подход динамического программирование. Если же мало, то можно рекурсивно перебрать все варианты.

Рекурсивное решение может выглядить так:

def app(number, moves):
    if number < 1:
        return float("inf")
    if number == 1:
        return moves
    variants = [app(number - 1, moves + 1)]
    if number % 3 == 0:
        variants.append(app(number // 3, moves + 1))
    if number % 2 == 0:
        variants.append(app(number // 2, moves + 1))
    return min(variants)


n = int(input())
a = int(input())
b = int(input())
print(app(n, 0))
print(app(a, 0))
print(app(b, 0))

Динамическое решение может выглядить так:

dp = dict()


def app(number, moves):
    if number in dp.keys():
        return dp[number] + 1
    if number < 1:
        return float("inf")
    if number == 1:
        return moves
    variants = [app(number - 1, moves + 1)]
    if number % 3 == 0:
        variants.append(app(number // 3, moves + 1))
    if number % 2 == 0:
        variants.append(app(number // 2, moves + 1))
    return min(variants)


n = int(input())
for num in range(n):
    curr = app(num, 0)
    dp[num] = curr
print(app(n, 0))

БЛОГ НА HUSL

Уменьшающееся число в Python (задача)

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