1

我有一个幂函数pow，它试图计算 的B的幂的 值E。到目前为止，我处理了这些情况 -
1. 指数为 0
2. 指数非零 

pow(B,0,1).
pow(B,E,Result):-   E2 is E - 1,
                    pow(B,E2,Result2),
                    Result is B*Result2.

如何添加幂函数可以处理负指数的另一种情况？

4

3 回答 3

4

首先，应该考虑如何定义 0 0。形式上是不确定的。它可能是零，也可能是 1。正如 Wolfram 的 Mathworld 在其关于幂的文章和关于零的文章中所说：

0 0（零的零次方）本身是未定义的。这个量缺乏明确定义的含义源于相互矛盾的事实：a 0始终为 1，因此 0 0应等于 1，但 0 a始终为 0（对于a > 0），因此 0 a应等于 0 . 0 0的定义选择通常被定义为不确定的，尽管定义 0 0 = 1 允许简单地表达一些公式 (Knuth 1992; Knuth 1997, p. 57)。

所以你应该首先选择如何定义 0 0 的特殊情况：是 0 吗？是1吗？它是未定义的吗？

我选择将其视为未定义。

话虽如此，您可以将正指数视为重复乘法（例如，10 3是 10*10*10，或 1,000），您可以将负指数视为表示重复除法（例如，10 -3是 ( ((1/10)/10)/10)，或 0.001)。我的倾向，部分是因为我喜欢这种方法的对称性，部分是为了避免削减（因为削减通常是你没有正确定义解决方案的信号），会是这样的：

% -----------------------------
% The external/public predicate
% -----------------------------
pow( 0 , 0 , _ ) :- ! , fail .
pow( X , N , R ) :-
  pow( X , N , 1 , R )
  .

% -----------------------------------
% the tail-recursive worker predicate
% -----------------------------------
pow( _ , 0 , R , R  ).
pow( X , N , T , R  ) :-
  N > 0 ,
  T1 is T * X ,
  N1 is N-1   ,
  pow( X , N1 , T1 , R )
  .
pow( _ , 0 , R , R  ) :-
  N < 0 ,
  T1 is T / X ,
  N1 is N+1   ,
  pow( X , N1 , T1 , R )
  .

正如其他人所指出的那样，另一种方法是将正指数定义为表示重复乘法，将负指数定义为表示正指数的倒数，因此 10 3是 10*10*10 或 1,000，而 10 -3是1/(10 3 )，或 1/1,000 或 0.001。要使用这个定义，我会再次避免削减并做这样的事情：

% -----------------------------
% the external/public predicate
% -----------------------------
pow( 0 , 0 , _ ) :-  % 0^0 is indeterminate. Is it 1? Is it 0? Could be either.
  ! ,
  fail
  .
pow( X , N , R ) :-
  N > 0 ,
  pow( X , N , 1 , R )
  .
pow( X , N , R ) :-
  N < 0 ,
  N1 = - N ,
  pow( X , N1 , 1 , R1 ) ,
  R is 1 / R1
  .

% -----------------------------------
% The tail-recursive worker predicate
% -----------------------------------
pow( _ , 0 , R , R  ).
pow( X , N , T , R  ) :-
  N > 0 ,
  T1 is T * X ,
  N1 is N-1   ,
  pow( X , N1 , T1 , R )
  .
于 2011-11-23T18:45:44.513 回答
2

首先，您的第二个子句是非尾递归的（您可以在此处阅读有关该主题的信息）。这意味着最终，您将在运行它时耗尽调用堆栈内存。一件好事是使用累加器使其尾递归。您可以按如下方式实现：

% we add an accumulator to poW/3, making it pow/4.
pow(B, E, Result) :- pow(B, E, 1, Result).

% when we hit 0, our accumulator holds B^E so we unify it with result.
pow(_, 0, Accu, Accu) :- !.

% at each step, we multiply our accumulator by B
pow(B, E, Accu, Result) :-
    NewE is E - 1,
    NewAccu is Accu * B,
    pow(B, NewE, NewAccu, Result).

然后，您可以通过在其他子句之上添加此子句来简单地处理否定情况（它只是告诉 prolog 负幂是正幂的倒数）：

pow(B, E, Result) :-
    E < 0,
    PositiveE is - E,
    pow(B, PositiveE, 1, R),
    !,
    Result is 1 / R.

请注意，您可以直接使用您的代码执行此操作：

pow(B, E, Result) :-
    E < 0,
    PositiveE is - E,
    pow(B, PositiveE, R),
    !,
    Result is 1 / R.

另外，我们现在引入了一个非常红色的切割（如有必要，请参见此处了解红色切割的含义）。所以最好用这个修改变成绿色切割：

pow(B, E, Result) :-
    E < 0,
    PositiveE is - E,
    pow(B, PositiveE, 1, R),
    !,
    Result is 1 / R.

% we add an accumulator to poW/3, making it pow/4.
pow(B, E, Result) :-
    E >= 0, %************* HERE *****************
    pow(B, E, 1, Result).

% when we hit 0, our accumulator holds B^E so we unify it with result.
pow(_, 0, Accu, Accu) :- !.

% at each step, we multiply our accumulator by B
pow(B, E, Accu, Result) :-
    NewE is E - 1,
    NewAccu is Accu * B,
    pow(B, NewE, NewAccu, Result).
于 2011-11-23T11:29:07.363 回答
2

别忘了a^(2b) = (a^b)^2和x^2 = x*x。可以从顶级“UI”谓词以非尾方式调用带有累加器的尾递归工作谓词。这样，您不必为负功率实现工作谓词，而是将其重用于正功率，并在顶级谓词中更改其结果（我看到这已经被建议）：

pow(B, E, R):- E<0 -> ... ; E=:=0 -> ... ; E>0 -> ... .
于 2011-11-23T12:29:02.337 回答