3

我正在尝试编写一个谓词，它递归地找到某个数字的 n 次方 [A^n = A * A^(n-1)] 并使用快捷方式 A^(2n) = A^n * A^n。

这是迄今为止的解决方案。

p(_,0,1):-!.
p(A,N,R):-N mod 2=0,!,N1=N/2,p(A,N1,R1),R=R1*R1.
p(A,N,R):-N1=N-1,p(A,N1,R1),R=R1*A.

现在我想让这个尾递归。我可以为简单的情况做tail，例如没有捷径的阶乘和幂（通过添加一个累加器），但这很难。

任何帮助深表感谢！

4

2 回答 2

3

毕竟这似乎是可能的，只需从另一端开始：

pow(A,N,R) :-
    pow(A,N,A,1,R).

pow(_,N,R,N,R) :- !.
pow(A,N,Acc,M,R) :-
    M =< N div 2, !,
    M1 is M*2,
    NewAcc is Acc * Acc,
    pow(A,N,NewAcc,M1,R).
pow(A,N,Acc,M,R) :-
    M < N,
    M1 is M+1,
    NewAcc is A * Acc,
    pow(A,N,NewAcc,M1,R).

它将快捷方式应用到小于 N 的 2 的最大幂，这与您的算法正在执行的操作不同。

于 2013-03-08T10:52:33.823 回答
2

鲍里斯是对的，他的算法所做的与原来的不一样。但是，如果您真的想要，可以通过以下方式重现它：

请注意，您可以从数字的二进制表示中确定操作的顺序。让N=7，然后二进制N=111，表示为N=7~111。

现在您在原始算法中看到了该方案：

N      Op     N'
7~111  Mul    6~110 (= zero last bit) 
6~110  Squ    3~011 (= shift right)
3~011  Mul    2~010 
2~010  Squ    1~001
1~001  Base

考虑到由于算法的递归性质，这些步骤是从上到下进行的，你得到Base - Squ - Mul - Squ - Mul = ((A*A)*A)*((A*A)*A))*A = A**7

将此与 Boris 的算法进行对比：

N      Op     N'
1~001  Squ    2~010 (=shift left)
2~010  Squ    4~100 (=shift left)
4~100  Mul    5~101 (=add one)
5~101  Mul    6~110 (=add one)
6~110  Mul    7~111 (=add one)

Mul, Squ所以这个首先进行所有的移位，而原来的考虑除了 N 中的第一个之外的每个位，从右到左，如果该位被设置或只是Squ如果它未设置，则依次“排队”（因为自下而上）.

为了重现这种行为（更有效，因为你永远不会做比平方更简单的乘法），你可以从N二进制开始并执行以下操作（这里是一般的伪代码，你可以很容易地翻译成序言）：

Acc=A
for i in (reverse(tail(bits(N)))):
    Acc*=Acc
    if i==1:
       Acc*=A

这是为了N>=1. N=0是一种特殊情况，必须分开处理。

我很确定这是正确的。如果您有疑问，请考虑您的原始算法：测试mod 2 == 0与测试最后一位是否为零是相同的。如果不是，那么减一与将最后一位归零相同，而加倍和减半只是在二进制中左移或右移。

于 2013-03-08T14:42:48.833 回答