Как я могу рассчитать, сколько раз конкретная функция будет выполнена в рекурсии - PullRequest
Новая
       8

Как я могу рассчитать, сколько раз конкретная функция будет выполнена в рекурсии

0 голосов
/ 03 июня 2018

Этот вопрос относится к коду удара: 

cost = [[1, 10, 75, 92],
         [-1, 0, 35, 50],
         [-1, -1, 0, 80],
         [-1, -1, -1, 0]]

def min_cost(source, destination):
   if s==d or s == d-1:
       return cost[s][d]
    mc = cost[s][d]
    for i in range(s+1, d):
        tmp = min_cost(s, i) + min_cost(i, d)
    if tmp < mc:
        mc = tmp
return mc

Когда я выполнял тот же пробный прогон, я видел, что min_cost (1,3) выполняется 2 раза.Я читал в одной книге, где автор упомянул, что если бы у нас было 10 станций между ними, то min_cost (1, 3) будет работать 144 раза.

Как мы можем выяснить это число, не выполняя пробный прогон.Я знаю, используя уравнения рекурсии, мы можем вычислить время, затраченное на функцию, но как можно сказать, что определенная функция будет выполняться столько раз?

Ответы [ 3 ]

0 голосов
/ 05 июня 2018

Хотя я понимаю, что вы не хотите, чтобы пробный прогон просто подсчитывал звонки, я все же хотел бы сначала сделать это, просто чтобы посмотреть, что происходит.Итак, вот так: 

def min_cost(s, d):
    global count
    count += 1
    if s==d or s == d-1:
        return cost[s][d]
    mc = cost[s][d]
    for i in range(s+1, d):
        tmp = min_cost(s, i) + min_cost(i, d)
    if tmp < mc:
        mc = tmp
    return mc

for n in range (2, 8):
    cost = [[0 for i in range (n)] for j in range (n)]
    count = 0
    min_cost(0, n-1)
    print (str (n) + ': ' + str (count))

Вывод: 

2: 1
3: 3
4: 9
5: 27
6: 81
7: 243

Итак, мы видим, что количество вызовов для ds = k равно 3 степени (k-1).Знание того, что мы должны доказать, иногда очень упрощает нахождение доказательства.

Теперь к самому доказательству.Это будет доказательство по индукции .Во-первых, обратите внимание, что количество вызовов min_cost(s, d) зависит только от значения d-s, а не от отдельных значений s и d.

Основа такова, что для d-s=1, мы получаем один звонок.Для d-s>1 мы делаем один звонок, и из него следующие звонки: 

min_cost(s, s+1) and min_cost(s+1, d)
min_cost(s, s+2) and min_cost(s+2, d)
...
min_cost(s, d-1) and min_cost(d-1, d)

Итак, для d-s=k количество звонков f(k) равно: 

f(k) = 1 +
       f(1) + f(k-1) +
       f(2) + f(k-2) +
       ... +
       f(k-1) + f(1)
     = 2 * (f(1) + f(2) + ... + f(k-1))

Если по предположению индукции мы уже доказали, что f (v) = 3 v для всех v 1 + 3 2 + ... + 3 k-1 ), что составляет тривиально 3 k , завершая наше доказательство.

Наконец, обратите внимание, что, хотя представленный алгоритм является экспоненциальным, основная задача может быть решена за полиномиальное время, наиболее просто за O ((ds)^ 2) запоминая звонки, для которых мы уже сделали всю работу.

0 голосов
/ 12 июня 2018

Я думаю, что глобальная переменная, которая находится за пределами функции (член вашего класса, если в Java, или глобальная переменная в C ++ / C) и увеличение ее значения на единицу каждый раз, когда вы ее вызываете, должна сработать.

0 голосов
/ 03 июня 2018

Существует несколько вариантов расчета этой суммы при работе с рекурсией.Простейшим было бы добавить в рекурсивный метод еще одну переменную, которая увеличивается каждый раз, когда она возвращается, и в последнем операторе, в котором она возвращается, она не увеличивается, а просто возвращает последнюю сумму, которая будет рекурсивно возвращаться в верхний регистр.request.

Пример в псевдокоде: 

function recursionfunction(x, y, recursioncount) {
    if(expressionIsFalse) {
        recursionfunction(x, y, recursioncount+1);
    } else {
        return recursioncount;
    }
}

print recursionfunction('','', 0);

Другой способ работы - присвоение переменной по ссылке, указателю или глобальной переменной (в зависимости от языка программирования) и увеличение этого счетчика..

Вам это помогло?

...