Форум » Динамическое программирование » Разберите решение для 7178 » Ответить
Разберите решение для 7178
MKSK: Я перепробовал множество решений(с помощью рекурсии). Но всё сводится к недостатку памяти, либо к бесконечному алгоритму. result = [] po = 0 def f(x,y,way:list): global po if x == y: result.append(way) po += 1 return 1 elif x > y: return 0 else: return f(x+2,y,way.copy())+f(x+3,y,way.copy())+f(x*3,y,way.copy()) print("Total",f(1,123,[1])) Это я уже просто отчаялся и решил записывать пути в массив, чтобы потом их разобрать. Но этот алгоритм приводит к недостатку памяти, что логично. А все остальные выполняются больше 8минут(дальше я не замерял). В ответах написано, что ответ 60, а значит, число подходящих решений должно быть больше 9**6.
Ответов - 1
Ж: Даже не возьмусь внятно объяснить, что делает этот код. Но ответ он выдает верный. И считает мгновенно. Но суть примерно такова: Максимальное число операций меньше 65. После каждого шага мы определяем количество способов получить очередное число, учитывая только разницу в количестве четных и нечетных чисел в траектории. Если одно и то же число с одинаковой разницей можно получить несколькими способами, складываем их и храним единожды в словаре. [pre2] kol=0; c={(1,1):1} for k in range(65): d={} for e in c: if e[0]%2==0: zn=-1 else: zn=1 if e[0]+2<=123: if (e[0]+2,e[1]+zn) not in d: d[e[0]+2,e[1]+zn]=c[e] else: d[e[0]+2,e[1]+zn]+=c[e] if e[0] + 3 <= 123: if (e[0] + 3, e[1] - zn) not in d: d[e[0] + 3, e[1] - zn] = c[e] else: d[e[0] + 3, e[1] - zn] += c[e] if e[0] *3 <= 123: if (e[0]*3,e[1]+zn) not in d: d[e[0]*3,e[1]+zn]=c[e] else: d[e[0]*3,e[1]+zn]+=c[e] c=d kol+=sum([c[t] for t in c if t[0]==123 and t[1]==0]) # print(d) print(kol,sum(int(c) for c in str(kol))) [/pre2]
полная версия страницы