Форум » Динамическое программирование » Не получается решить задание ЕГЭ 23 №6500 » Ответить
Не получается решить задание ЕГЭ 23 №6500
egorissa: [pre2] def f(start, finish, counter): if start > finish or start == 11 or start == 35 or counter > 5: return 0 if start == finish: return 1 if start < finish: return f(start + 1, finish, counter + 1) + f(start + 3, finish, counter) + f(start * 2, finish, counter) print(f(2, 18, 0) * f(18, 40, 5)) print(f(2, 18, 1) * f(18, 40, 4)) print(f(2, 18, 2) * f(18, 40, 3)) print(f(2, 18, 3) * f(18, 40, 2)) print(f(2, 18, 4) * f(18, 40, 1)) print(f(2, 18, 5) * f(18, 40, 0)) [/pre2] Сначала подумал использовать оба вызова функции с параметром counter = 0, потом понял, что будет допущено 10 использований команды 1. Потом всё-таки сделал допустимое количество использований этих команд = 5, перебрал разные варианты (чтобы от 2 до 18 не использовалась, а от 18 до 40 использовалась 5 раз или меньше и т.д. (команды print)), но ничего путёвого не вышло. Прошу помощи!
Ответов - 1
Ж: Вот более компактный код [pre2] f=lambda n,k,tr: f(n+1,k+1,tr+[n]) + f(n+3,k,tr+[n]) + f(n*2,k,tr+[n]) if n<40 and k<=5 else n==40 and k<=5 and 18 in tr and 11 not in tr and 35 not in tr print(f(2,0,[])) [/pre2] В вашем коде считаются случаи, которые имеют ровно 5 команд +1, а надо не более 5. И выход из рекурсии неверен - не проверили, что счетчик числа команд +1 стал равным 5. Вот ваш поправленный код: [pre2] def f(start, finish, counter): if start > finish or start == 11 or start == 35 or counter > 5: return 0 if start == finish : return counter == 5 if start < finish: return f(start + 1, finish, counter + 1) + f(start + 3, finish, counter) + f(start * 2, finish, counter) print(f(2, 18, 0) * f(18, 40, 5)) print(f(2, 18, 1) * f(18, 40, 4)) print(f(2, 18, 2) * f(18, 40, 3)) print(f(2, 18, 3) * f(18, 40, 2)) print(f(2, 18, 4) * f(18, 40, 1)) print(f(2, 18, 5) * f(18, 40, 0)) print(f(2, 18, 1) * f(18, 40, 5)) print(f(2, 18, 2) * f(18, 40, 4)) print(f(2, 18, 3) * f(18, 40, 3)) print(f(2, 18, 4) * f(18, 40, 2)) print(f(2, 18, 5) * f(18, 40, 1)) print(f(2, 18, 2) * f(18, 40, 5)) print(f(2, 18, 3) * f(18, 40, 4)) print(f(2, 18, 4) * f(18, 40, 3)) print(f(2, 18, 5) * f(18, 40, 2)) print(f(2, 18, 3) * f(18, 40, 5)) print(f(2, 18, 4) * f(18, 40, 4)) print(f(2, 18, 5) * f(18, 40, 3)) print(f(2, 18, 4) * f(18, 40, 5)) print(f(2, 18, 5) * f(18, 40, 4)) print(f(2, 18, 5) * f(18, 40, 5)) [/pre2] последний блок можно сделать более компактным [pre2] kol=0 for n in range(6): for k in range(6): kol+=f(2, 18, k+n) * f(18, 40, 5-k) print(kol) [/pre2]
полная версия страницы