Преобразование рекурсивной формулы в псевдокод с использованием мемоизации - PullRequest
Новая
       80

Преобразование рекурсивной формулы в псевдокод с использованием мемоизации

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

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

Моя формула повторения: 

N(C,i) =
1 if C = 0
0 if i=0 or C<0}
N(C-p_i, i-1) + N(C, i-1) otherwise

Моя текущая попытка: 

MEM-N(C, i, r)
    if r[i] >= 0 then
        return r[i]
    if i = 0 and r[i] >= 0 or C < 0 and r[i] >= 0 then
        return 0
    else if C = 0 and r[i] >= 0 then
        return 1
    else
        q = -$\infty$
        q = MEM-N(C - $p_i$, i-1) + MEM-N(C,i - x, r)
        r[i] = q
        return q

1 Ответ

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

Исходя из комментариев: 

MEM-N(C, i, r)
    if C = 0 then
        return 1
    else if i = 0 or C < 0 then
        return 0
    else if r[i] >= 0 then
        return r[i]                                        # move here
    else
        q = MEM-N(C - p_i, i - 1, r) + MEM-N(C, i - 1, r)  # fix
        r[i] = q
        return q
...