#algorithm #language-agnostic #dynamic-programming
#алгоритм #язык не зависит #динамическое программирование
Вопрос:
Я застреваю, когда возникает такая проблема:
Предположим, я хочу найти foo(n) . Я знаю формулу для foo(n) , но она включает в себя оба foo(n-1) и foo(n 1) в его вычислении.
Если бы я попытался решить их с помощью наивной рекурсивной функции, то эти два вызова функции снова вызывали бы родительскую функцию через них. Это привело бы к бесконечному циклу! например, попытка решить foo(n) будет включать вызов foo(n 1) , который будет вызывать обратный foo(n) вызов , и так далее.
Существует ли общий метод для решения этого конкретного типа проблем, не полагаясь на какие-либо предположения о точном вычислении foo(n) из foo(n-1) и foo(n 1) ?
Редактировать:
В моем примере я знаю foo(n) = 0 и foo(n-1) = 1 для конкретного n , и я хочу вычислить все значения между foo(n-2) и 0 .
Комментарии:
1. Это не является четко определенной проблемой, ни математически, ни вычислительно. Что вы пытаетесь вычислить?
2. Есть ли какой-либо верхний предел для остановки foo?
3. «Как решаются такие проблемы в программировании?» Например. указание s.th . например, максимальная глубина рекурсии.
4. @G.Bach Да, это хороший момент в базовых случаях. Итак, теперь мы на одной странице? В вопросе слишком мало информации, чтобы ответить на него.
5. Я абсолютно понятия не имею, почему этот вопрос отклонен или почему люди говорят о необходимости обеих границ и необходимости пройти весь путь вверх, а затем снова вниз. Похоже, это случай, когда люди не знают ответа на вопрос и поэтому делают неправильные предположения
Ответ №1:
На самом деле решение этой проблемы очень простое. Если у вас есть отношение, что-то вроде:
f(n) = f(n 1) - f(n-1)
Все, что вам нужно сделать, это вычесть положительное k значение из каждого из внутренних членов, чтобы ни один член не был функцией чего-либо выше n . Например, в этом случае k было бы 1 :
f(n-1) = f(n) - f(n-2)
Затем перестановка получает:
f(n) = f(n-1) f(n-2)
Который вы могли бы распознать как последовательность Фибоначчи. Это всего лишь пример, не имеет значения, какая связь между f(n) , f(n 1) и f(n-1) , пока это функция, которую вы можете отменить, вы всегда можете сместить аргументы функции, чтобы преобразовать ее в функцию f(n) , f(n-1) и f(n-2) . Другой пример:
f(n) = f(n 1) / f(n-1)
f(n-1) = f(n) / f(n-2)
f(n) = f(n-1) * f(n-2)
В более общих чертах, если у вас есть:
f(n) = H[f(n 1), f(n-1)]
Затем вы можете преобразовать это в:
f (n) = H-1[f (n-1), f (n-2)]
Где H — функция, а H-1 — ее обратная.
Это предполагает, что у вас есть два значения на нижней границе и вы хотите сделать шаг вверх. (например f(0) = 1, f(1) = 1 ). Если у вас есть верхние границы и вы хотите уйти, тогда вы бы добавили k вместо вычитания
Комментарии:
1. пользователь2732146 не указал, является ли f (n) суммой, произведением, разностью или чем-то еще из f(n 1) и f (n-1). Хотя я ожидаю, что это будет то, что он в конечном итоге скажет, мы не знаем этого прямо сейчас.
2. @G.Bach Но это не имеет значения. Каким бы ни было отношение, вы можете сделать то же самое. Это был просто пример. Если бы это было
f(n)=f(n 1)f(n-1)так, опять же, вы могли бы перенести это наf(n-1) = f(n)f(n-2)предоставлениеf(n) = f(n-1)/f(n-2)