Форум » Динамическое программирование » Задание 23 (№ 5544) (М. Шагитов) » Ответить
Задание 23 (№ 5544) (М. Шагитов)
don: Здравствуйте. Задача из Готовые варианты с ответами (Вариант 1) (№ 5544) (М. Шагитов) Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера: 1. Прибавь 2 2. Умножь на 3 3. Умножь на 4 Выполняя первую из них, исполнитель увеличивает число на экране на 2, выполняя вторую – умножает на 3, выполняя третью – умножает на 4. Программой для исполнителя называется последовательность команд. Сколько существует различных программ, которые преобразуют исходное число 1 в число 600, и при этом траектория вычислений (включая начальное число) содержит три подряд идущих числа, сумма которых кратна 11. def f(x,y): if x>y: return 0 if x==y: return 1 if x<y: if (f(x,y)+f(x+1,y)+f(x+2,y))%11==0: return f(x+2,y)+f(x*3,y)+f(x*4,y) print(f(1,600)) Помогите разобраться, где ошибка?
Ответов - 7
MrAndrewson: if (f(x,y)+f(x+1,y)+f(x+2,y))%11==0: Это не гарантирует, что траектория вычислений (включая начальное число) содержит три подряд идущих числа, сумма которых кратна 11. Тут вы берете не числа траектории, поскольку команды другие. К тому же, в траектории может быть одна и та же команда несколько раз.
don: def f(x,y): if x>y: return 0 if x==y: return 1 if x<y: if (f(x,y)+f(x+2,y)+f(x+4,y))%11==0 or (f(x,y)+f(x+2,y)+f((x+2)*3,y))%11==0: return f(x+2,y)+f(x*3,y)+f(x*4,y) print(f(1,600)) Даже если все варианты траекторий перебирать (записал не все, только две), то ошибка: builtins.RecursionError: maximum recursion depth exceeded in comparison
Alex_R: [pre2]# Список всех траекторий из 1 в 600 res = [] def f(a, b, way: list): if a == b: res.append(way) # траектория завершена, добавим ее в res return 1 elif a > b: return 0 else: # Разветвление на 3 пути a1 = a + 2 a2 = a * 3 a3 = a * 4 # Создаем 3 копии траектории и добавляем в каждую новые числа way1 = way.copy() way1.append(a1) way2 = way.copy() way2.append(a2) way3 = way.copy() way3.append(a3) # Рекурсивно продолжаем поиск return f(a1, b, way1) + f(a2, b, way2) + f(a3, b, way3) print('Total ways:', f(1, 600, [1])) count = 0 # Перебор всех траекторий и подсчет тех, в которых 3 числа рядом делятся без остатка на 11 for w in res: # Перебор чисел в траектории for i in range(len(w) - 2): if sum(w[i:i+3]) % 11 == 0: count += 1 break print('Ответ:', count) [/pre2]
don: Спасибо!
Mathew131: Задача 13 (№ 5544) Почему если пишу tr.append(start) выводит неправильный ответ? А если tr = tr + [start], то правильный В чем прикол? def f(start, end, tr = []): # tr.append(start) tr = tr + [start] if start == end: for i in range(len(tr)-2): if (tr + tr[i+1] + tr[i+2]) % 11 == 0: return 1 return 0 if start > end: return 0 return f(start + 2, end, tr) + f(start * 3, end, tr) + f(start * 4, end, tr) print(f(1, 600))
Gala: уберите return 0 после первого return
Gala: tr.append плевать хотел, то у Вас t=[]. Он все добавляет к предыдущей траектории.
полная версия страницы