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.

ここで、この末尾再帰を作成します。階乗やパワーなどの単純なケースでは、ショートカットなしで（アキュムレータを追加することで）テールを実行できますが、これは困難です。

どんな助けでも大歓迎です！

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

ボリスは、彼のアルゴリズムが元のアルゴリズムと同じではないという点で正しいです。しかし、本当にやりたいのであれば、これを再現する方法は次のとおりです。

数値の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は、最後のビットがゼロかどうかのテストと同じです。そうでない場合は、1を差し引くことは、最後のビットをゼロにすることと同じですが、2倍および2分の1は、2進数で左または右にシフトするだけです。

于 2013-03-08T14:42:48.833 に答える