Калькулятор с восстановлением ответа (Python)

@Gernar · Регистрация: 12.11.2016

Студворк — интернет-сервис помощи студентам

Здравствуйте.
В общем, условие такое:
***
Исполнитель «Калькулятор» может с заданным числом X выполнить одну из трех операций и
получить новое число. Возможные операции:
 Прибавить к числу X единицу.
 Умножить число X на 2.
 Умножить число X на 3.
При помощи наименьшего числа операций получите из числа 1 заданное число N.

Во второй строке выведите k+1 число, последовательно получающиеся при выполнении
операций. Первое из них должно быть равно 1, а последнее N. Если решений несколько,
выведите любое из них.
----
Программа получает на вход одно число N, не превосходящее 106.
----
Сначала выведите необходимое количество операций k.
Во второй строке выведите k+1 число, последовательно получающиеся при выполнении
операций. Первое из них должно быть равно 1, а последнее N. Если решений несколько,
выведите любое из них.
****
Первую часть этого задания я уже сделал:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = int(input())
q=[0,1,1,1] + [0]*(n-3)
counter = 0
for i in range(4,n+1):
    if i % 3 ==0:
        q[i] = min(q[i//3], q[i-1]) + 1
    elif i % 2==0:
        q[i] = min(q[i//2], q[i-1]) + 1
    else:
        q[i] = q[i-1] + 1
 
print(q[n])
# q - quantity
# n - N

Теперь мне нужно вывести список преобразования числа, не пойму как это написать, помогите.
Например:

Ввод:
5
Вывод:
3
1, 3, 4, 5

Добавлено через 1 час 42 минуты
Впрочем, подойдёт и сама идея реализации данной программы, попытаюсь сам написать

@keepermag · 13.11.2016, 06:15

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
N = int(input())
list_x = [1]
 
while N != 1:
    list_x.append(N)
    if N%3 == 0:
        N = N / 3
    elif N%2 == 0:
        N = N / 2
    else:
        N = N - 1
list_x.sort()
    
print ('the number of operations - %s' %(len(list_x)-1))    
print (list_x)

@Gernar · 14.11.2016, 16:22 **[ТС]**

к сожалению твой код не правильный, так как он показывает не наименьшее количество операций. Допустим, он покажет не правильный результат при вводе числа 962340. Мой код покажет 17, твой код покажет 23 вроде.

@keepermag · 28.11.2016, 00:06

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
x = input()
d = {1:1,2:1,3:1}
dd = {}
nn = 1
 
 
def if_is(ii):
    if ii in d:
        return True
    else:
        return False
 
 
while x not in d:
    for i in d:
        if not if_is(i + 1):
            dd[i + 1] = i
        if not if_is(i * 2):
            dd[i * 2] = i
        if not if_is(i * 3):
            dd[i * 3] = i
    d.update(dd)
    nn += 1
 
tm = d[x]
print (tm)
for i in xrange(nn-1):
    print (d[tm])
    tm = d[tm]
 
print ('\n%s' % nn)

Добавлено через 8 минут
P.S.
Лучше поздно чем никогда, решил всё таки доделать. Надеюсь теперь правильно будет работать. Прогнал через тест, на этот раз у тебя больше показывает, например на 642.

@Tom_Waits · 02.05.2021, 21:40

А не должны ли мы ещё одну строчку добавить, для случая если число делится и на 2 и на 3 одновременно?

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = int(input())
q = [0, 0, 1, 1] + [0] * (n - 3)
 
for i in range(4, n + 1):
    if i % 3 == 0 and i % 2 == 0:
        q[i] = min(q[i // 3], q[i // 2], q[i - 1]) + 1
    elif i % 3 == 0:
        q[i] = min(q[i // 3], q[i - 1]) + 1
    elif i % 2 == 0:
        q[i] = min(q[i // 2], q[i - 1]) + 1
    else:
        q[i] = q[i - 1] + 1
 
print(q[n])

Новые блоги и статьи Все статьи Все блоги /
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а привычная функция main(). . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/

@Gernar 0 / 0 / 1 Регистрация: 12.11.2016 Сообщений: 3
	14.11.2016, 16:22 [ТС]
	к сожалению твой код не правильный, так как он показывает не наименьшее количество операций. Допустим, он покажет не правильный результат при вводе числа 962340. Мой код покажет 17, твой код покажет 23 вроде. 0