编写一个类似阶乘的函数(Prolog)

Question

我必须编写一个Prolog程序来计算：

  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，因为我对该语言非常陌生。此外，我从来没有弄清楚如何做一个迭代的方法。任何帮助将不胜感激！

这是我对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

好的，

这是正确的代码：）你最大的错误是使变量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.

我决定将计算拉入它自己的谓词中，因为我不喜欢在两个不同的地方做同样的事情。