3

背景

我需要写一个谓词eval(P,A,R)，其中：
P表示多项式系数的列表，即1+2x+3x^2表示为[1,2,3]。
A 表示 X 的值
。R 是多项式在 X=A 处的结果。

示例： eval([3,1,2],3,R) 产生 R = 24。 *编辑，以前不正确的示例

我正在尝试使用本文中的累加器和Learn Prolog Now上的示例。

我的算法：
0. 将结果和指数变量初始化为 0。
1. 取列表的头部。
2. 将列表的头部乘以 A^(exponent)。
3. 更新结果和指数。

我的代码： 

eval(P,A,R) :- accEval(P,A,0,0,R).      
accEval(([H|T]),A,Pow,Accres,R) :- 
        Rnew is (Accres+H*(A**Pow)), 
        Pownew is Pow+1, 
        R = Accres, 
        accEval(T,A,Pownew,Rnew,Rnew).  % *See below
accEval([],A,Pow,Accres,Accres).

% *Previously, when the second Rnew in this line was R instead, output was "no".

产生跟踪：

| ?- eval([1,2],3,R).
  1    1  Call: eval([1,2],3,_20) ? 
  2    2  Call: accEval([1,2],3,0,0,_20) ? 
  3    3  Call: _126 is 0+1*3**0 ? 
  3    3  Exit: 1.0 is 0+1*3**0 ? 
  4    3  Call: _157 is 0+1 ? 
  4    3  Exit: 1 is 0+1 ? 
  5    3  Call: accEval([2],3,1,1.0,1.0) ? 
  6    4  Call: _218 is 1.0+2*3**1 ? 
  6    4  Exit: 7.0 is 1.0+2*3**1 ? 
  7    4  Call: _249 is 1+1 ? 
  7    4  Exit: 2 is 1+1 ? 
  8    4  Call: accEval([],3,2,7.0,7.0) ? 
  8    4  Exit: accEval([],3,2,7.0,7.0) ?  % We have the correct answer.
  5    3  Exit: accEval([2],3,1,1.0,1.0) ? % Wait! What are you doing!?
  2    2  Exit: accEval([1,2],3,0,0,0) ?   % Why is this falling back out?
  1    1  Exit: eval([1,2],3,0) ? 

R = 0  % Incorrect. The answer should be 7.

如我的代码中所述，以前的尝试对 R 没有产生任何价值，而是产生“否”或在其他实现中产生“是”。

问题

为什么结果会丢失，没有带回原来的调用？

4

3 回答 3

2

这有点简单：

eval(P,A,R) :- accEval(P,A,0,0,R).
accEval(([H|T]),A,Pow,Accres,R) :-
        Rnew is (Accres+H*(A**Pow)),
        Pownew is Pow+1,
        accEval(T,A,Pownew,Rnew,R).  % *See below
accEval([],_A,_Pow,Accres,Accres).

但你的例子似乎不正确

?-  eval([3,2,1],3,R).
R = 18.

确实 3+2*X+X^2 with X=3 产生 18

于 2013-03-06T22:20:15.207 回答
2

应该在递归结束时与累加器值统一的变量已经绑定到一个值。您使用累加器的方式如下：

  • 当你第一次“调用”谓词时，给累加器一个初始值
  • 使用累加器将累加值传递给递归调用
  • 将结果与递归结束子句中的累加器统一起来

根据经验，谓词头部的 Result 变量与向下传递给递归调用的变量相同。这样，一旦它与最后的实际结果（在递归结束子句中）统一起来，它也将在递归之外传递给调用者。

于 2013-03-06T22:21:54.840 回答
0

这里的策略可能是所谓的霍纳模式。在霍纳模式中，您不需要幂函数 (**)/2 或 (^)/2。霍纳模式说：

a_0 + a_1*x + .. + a_n-1*x^n-1 + a_n*x^n =

a_0 + x*(a_1 + .. + x*(a_n-1 + x*a_n)..)

如果您允许以相反的顺序提供系数 [a_n,..,a_0]，那么 Horner 模式很容易在 Prolog 中实现，如下所示：

eval([C|L], X, R) :-
    eval(L, C, X, R).

eval([C|L], A, X, R) :-
    B is A*X+C,
    eval(L, B, X, R).
eval([], A, _, A).

作为奖励，霍纳方案在数值上更稳定。这是一个示例运行：

?- eval([2,1,3],3,R).
R = 24
于 2016-11-09T19:54:57.743 回答