Рекурсивные функции, как их можно сокращать У меня задана рекурсивная функция, как ее можно сократить
Описана рекурсивная функции с тремя параметрами F(a, b, c):

если a ≤ 0 или b ≤ 0 или c ≤ 0, то F(a, b, c) = 1
если a > 20 или b > 20 или c > 20, то F(a, b, c) = F(20, 20, 20)
если a < b и b < c, то F(a, b, c) = F(a, b, c-1) + F(a, b-1, c-1) - F(a, b-1, c)
иначе F(a, b, c) = F(a-1, b, c) + F(a-1, b-1, c) + F(a-1, b, c-1) - F(a-1, b-1, c-1)

20 Апр 2023 в 19:40
128 +1
0
Ответы
1

Для сокращения рекурсивной функции можно использовать мемоизацию, чтобы избежать повторных вычислений и ускорить работу функции. Мемоизация — это техника оптимизации, при которой результаты уже выполненных вычислений сохраняются в памяти и при повторном вызове функции с теми же параметрами результат берется из памяти, а не пересчитывается.

Для этой конкретной функции можно также оптимизировать условия базовых случаев (a ≤ 0, b ≤ 0, c ≤ 0 и a > 20, b > 20, c > 20) и убрать условие a < b и b < c, так как это условие не используется в рекурсивном вычислении. В итоге, оптимизированная версия функции может выглядеть следующим образом:

# Используем мемоизацию, чтобы избежать повторных вычислений
memo = {}
def F(a, b, c):
if (a, b, c) in memo:
return memo[(a, b, c)]
if a <= 0 or b <= 0 or c <= 0:
memo[(a, b, c)] = 1
return 1
if a > 20 or b > 20 or c > 20:
memo[(a, b, c)] = F(20, 20, 20)
return memo[(a, b, c)]
memo[(a, b, c)] = F(a-1, b, c) + F(a-1, b-1, c) + F(a-1, b, c-1) - F(a-1, b-1, c-1)
return memo[(a, b, c)]

Таким образом, мы оптимизировали рекурсивную функцию с помощью мемоизации и упростили некоторые условия.

16 Апр 2024 в 16:22
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Прямой эфир