Дать факторную подобную функцию (Пролог)

Question

Я должен написать программу для вычисления Пролога:

f(0) = 2, 
    f(1) = 0, 
    f(2) = 3, 
    f(n) = 3f(n-3) + 2f(n-2) - f(n-1) for n≥3. 

мне нужно сделать итерационную версию, а также рекурсивный вариант. Я был в состоянии написать, что рекурсивную версию в SML:

fun myFunc 0 = 2 
| myFunc 1 = 0 
| myFunc 2 = 3 
| myFunc x = 3* myFunc(x-3) + 2* myFunc(x-2) - myFunc(x-1) 

Но у меня возникают проблемы с передачей его на Прологе, как я очень новый язык. Кроме того, я никогда не мог понять, как сделать итеративный подход. Любая помощь будет принята с благодарностью!

Вот моя попытка рекурсивной версии Prolog. Он не компилирует и, вероятно, даже не близко к праву:

my_Fun(0, 2). 
my_Fun(1, 0). 
my_Fun(2, 3). 
my_Fun(X, F) :- 
    X>=3, NewX is X-3, NewF is 3 * F, my_fun(NewX,NewF), 
    NewX2 is X-2, NewF2 is 2 * F, my_fun(NewX2, NewF2), 
    NewX3 is X-1, NewF3 is F, myFun(NewX3,NewF3). 

Answer 1

Ok вот правильный код :) Ваша самая большая ошибка делает переменные NEWF, NewF2, NewF3 зависит от чего-то, что не имеет значения (пример: NewF - 3 * F ... мы еще не знаем F). Проверьте код ниже и обратите внимание на разницу. «

my_fun(0, 2). 
my_fun(1, 0). 
my_fun(2, 3). 
my_fun(X, F) :- X>=3, NewX is X-3, my_fun(NewX,NewF), 
         NewX2 is X-2, my_fun(NewX2, NewF2), 
         NewX3 is X-1, my_fun(NewX3,NewF3), 
         F is 3*NewF+2*NewF2-NewF3. 

Вот код при использовании итеративного подхода. Мы используем аккумуляторы для хранения нужных нам значений, а затем используем эти значения для получения результата.

my_fun_iterative(0,2) :- !. 
my_fun_iterative(1,0) :- !. 
my_fun_iterative(2,3) :- !. 

my_fun_iterative(X,F) :- X > 2, 
         my_fun_iterative(0,ZeroV), 
         my_fun_iterative(1,OneV), 
         my_fun_iterative(2,TwoV), 
         V is 3*ZeroV+2*OneV-TwoV, 
         my_fun_iterative(X,3,OneV,TwoV,V,F),!. 

my_fun_iterative(X,X,_,_,F,False) :- not(F=False),!,false. 
my_fun_iterative(X,X,_,_,F,F). 
my_fun_iterative(X,N,SecondV,ThirdV,Acc,F) :- X > 3, 
               AccNew is 3*SecondV+2*ThirdV-Acc, 
               NNew is N+1, 
               my_fun_iterative(X,NNew,ThirdV,Acc,AccNew,F). 

Answer 2

Вот рекурсивная версия, которая позволяет избежать множества перерасчетов, сохраняя последние 3 расчеты на каждой итерации:

my_fun(N, F) :- 
    my_fun(N, F, _, _). 

my_fun(N, F, F2, F1) :- 
    N >= 3, 
    N1 is N-1, 
    my_fun(N1, F2, F1, F0), 
    F is 3*F0 + 2*F1 - F2. 
my_fun(0, 2, 0, 0). % 3rd and 4th terms are "dummies" 
my_fun(1, 0, 2, 0). % 4th term is "dummy" 
my_fun(2, 3, 0, 2). 

Пример итеративного (хвостовая рекурсия) версия:

my_fun_it(N, F) :- 
    N >= 3, 
    my_fun_it(0, F0), 
    my_fun_it(1, F1), 
    my_fun_it(2, F2), 
    my_fun_it(N, 3, F, F2, F1, F0). 
my_fun_it(0, 2). 
my_fun_it(1, 0). 
my_fun_it(2, 3). 

my_fun_it(N, C, F, F2, F1, F0) :- 
    C < N, 
    my_fun_calc(F0, F1, F2, F3), 
    C1 is C + 1, 
    my_fun_it(N, C1, F, F3, F2, F1). 
my_fun_it(N, N, F, F2, F1, F0) :- 
    my_fun_calc(F0, F1, F2, F). 

my_fun_calc(F0, F1, F2, F) :- 
    F is 3*F0 + 2*F1 - F2. 

Я решил вывести расчет в свой собственный предикат, так как мне не нравилось то же самое в двух разных местах.