Python-сообщество

Fiares_Curie · Окт. 8, 2021 22:32:23

Имеется калькулятор, который выполняет три операции:

Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Определите кратчайшую последовательность операций, необходимую для получения из числа 1 заданное число N.

Входные данные:
Программа получает на вход одно число N, не превосходящее 106.

Выходные данные:
Выведите строку, состоящую из цифр “1”, “2” или “3”, обозначающих одну из трех указанных операций, которая получает из числа 1 число N за минимальное число операций. Если возможных минимальных решений несколько, выведите любое из них.
Мой код:

 n = int(input())
x = 1
s = ""
while x < n:
    if x*3 < n:
        x *= 3
        s = s + "3"
    elif x*3 == n:
        s = s + "3"
        print(s)
        break
    elif x*2 < n:
        x *= 2
        s = s + "2"
    elif x*2 == n:
        s = s + "2"
        print(s)
        break
    elif x+1 < n:
        x += 1
        s = s + "1"
    elif x+1 == n:
        s = s + "1"
        print(s)
        break

Но заходит эта программа только на четырех тестах (из 19). Где ошибки?

py.user.next · Окт. 9, 2021 00:43:28

Fiares_Curie
Где ошибки?

Подход неправильный. Пиши рекурсивную функцию. Если сделаешь хвостовую рекурсию, то сможешь преобразовать её в цикл. Но я думаю, что тебе и рекурсии будет достаточно для прохождения.
Тут писал ссылку на пример.

Ты делай сам. Или мы сейчас за тебя сделаем эту задачу и ты так ничему и не научишься. Потому что, чтобы научиться чему-то, надо делать это самому, прогонять через свои мозги, искать самому вариант, думать самому. Только так мозги обучаются.

Отредактировано py.user.next (Окт. 9, 2021 00:45:49)

xam1816 · Окт. 9, 2021 21:09:11

Это задача из динамического программирования,т.е или по другому нахождение оптимального решения.Мне понимание динамического программирования плохо дается,прямо стена какая-то.
Понравилась цитата“ Динамическое программирование - это когда задачу,которую не понятно как решать,разбиваешь на более мелкие задачи,которые тоже не понятно как решать”

Вот и берем значит задачу типа

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)# примененные операции

Python-сообщество

Уведомления

#1 Окт. 8, 2021 22:32:23

Задача "Калькулятор с восстановлением ответа"

#2 Окт. 9, 2021 00:43:28

Задача "Калькулятор с восстановлением ответа"

#3 Окт. 9, 2021 21:09:11

Задача "Калькулятор с восстановлением ответа"

Board footer