Prolog拡張ユークリッドアルゴリズム

Question

私はいくつかのプロローグコードで数日間苦労していましたが、その方法を見つけることができませんでした。ここでの方程式とは、私が試したものである

a*p + b*s = gcd(a,b) 

：私は、拡張ユークリッドアルゴリズムを記述し、値pとsを見つけようとしています、私はそれはsが見つかり少し検索した後 `

common(X,X,X,_,_,_,_,_,_). 
common(0,Y,Y,_,_,_,_,_,_). 
common(X,0,X,_,_,_,_,_,_). 

common(X,Y,_,1,0,L1,L2,SF,TF):- 
            append(L1,1,[H]), 
            append(L2,0,[A]), 
            SF is H , 
            TF is A, 
            common(X,Y,_,0,1,[H],[A],SF,TF). 

common(X,Y,_,0,1,L1,L2,SF,TF):- 
            append(L1,0,[_,S2]), 
            append(L2,1,[_,T2]), 
            Q is truncate(X/Y), 
            S is 1-Q*0,T is 0-Q*1 , 
            common(X,Y,_,S,T,[S2,S], 
            [T2,T],SF,TF). 

common(X,Y,N,S,T,[S1,S2],[T1,T2],SF,TF):- 
            Q is truncate(X/Y), 
            K is X-(Y*Q), 
            si_finder(S1,S2,Q,SF), 
            ti_finder(T1,T2,Q,TF), 

common(Y,K,N,S,T,[S2,S],[T2,T],SF,TF). 


si_finder(PP,P,Q,C):- C is PP - Q*P. 

ti_finder(P2,P1,QA,C2):- C2 is P2 - QA*P1. 

とp係数は1と0から始まり、それらの第2の値はそれぞれ0と1です。それはsi_finder述語とti_finder述語で行ったパターンで続きます。共通述語はパターンを再帰的に制御しようとしたところです。しかし、共通の述語はすべての呼び出しでfalseを返すようにしています。誰も私がPrologでこのアルゴリズムを実装するのを助けることができます。

ありがとうございます。

Answer 1

まず、述語のアリティについて考えてみましょう。明らかに、数字AとBだけでなく、ベジェ係数PとSを引数として使用したいと思います。とにかくアルゴリズムはGCDを計算しているので、それを引数としてもよいでしょう。そのため、私たちには未知数が残っています。5.拡張ユークリッドアルゴリズムについて話しているので、述語eeuclid/5を呼び出しましょう。次に、例を考えてみますのは、A = 242のためにP、SおよびGCDを計算するためのアルゴリズムを使用してみましょうし、Bは69を=：

quotient (Q) | remainder (B1) | P | S 
-------------+-------------------+-------+------- 
      |    242 | 1 | 0 
      |    69 | 0 | 1 
242/69 = 3 | 242 − 3*69 = 35 | 1 | -3 
69/35 = 1 | 69 − 1*35 = 34 | -1 | 4 
35/34 = 1 | 35 − 1*34 = 1 | 2 | -7 
34/1 = 34 | 34 − 34*1 = 0 | -69 | 242 

私たちは次のことを観察することができます：

• アルゴリズムがあれば停止します最後の行（この例では2 -7）（本実施例1の）残りの列のGCDとPにおけるBézout係数およびS列をそれぞれ含有

前に余りが0

• ラインなります

• 商は前の剰余から計算されます。次の反復でAはBになり、BはB1になります。

• PおよびSは、それぞれの前任者から計算されます。たとえば、P3 = P1-3 * P2 = 1-3 * 0 = 1、S3 = S1-3 * S2 = 0-3 * 1 = -3などです。また、前の2つのPとSを持つだけで十分なので、ペアとして渡すこともできます。 P1-P2、S1-S2となる。 0-1は、アルゴリズムが一緒にこのすべてを置く大きな数

で始まる

、呼び出し元の述語があり：1-0とS：

アルゴリズムは、ペアPで始まりますAがより大きい数であり、それが5つの引数であることを保証するために、最初の対1-0と0-1を実際の関係を記述する述語に渡す必要があります。a_b_p_s_/7：

:- use_module(library(clpfd)). 

eeuclid(A,B,P,S,GCD) :- 
    A #>= B, 
    GCD #= A*P + B*S,    % <- new 
    a_b_p_s_(A,B,P,S,1-0,0-1,GCD). 
eeuclid(A,B,P,S,GCD) :- 
    A #< B, 
    GCD #= A*P + B*S,    % <- new 
    a_b_p_s_(B,A,S,P,1-0,0-1,GCD). 

a_b_p_s_/7の最初のルールは、B = 0でアルゴリズムが停止する基本ケースを記述します。そして、AはGCDであり、P1はベジェ係数である。そうでなければ商Q、残りのB1とP及びSの新しい値が計算され、a_b_p_s_/7はそれらの新しい値と呼ばれる。

?- eeuclid(242,69,P,S,GCD). 
P = 2, 
S = -7, 
GCD = 1 ; 
false. 

：

a_b_p_s_(A,0,P1,S1,P1-_P2,S1-_S2,A). 
a_b_p_s_(A,B,P,S,P1-P2,S1-S2,GCD) :- 
    B #> 0, 
    A #> B,       % <- new 
    Q #= A/B, 
    B1 #= A mod B, 
    P3 #= P1-(Q*P2), 
    S3 #= S1-(Q*S2), 
    a_b_p_s_(B,B1,P,S,P2-P3,S2-S3,GCD). 

上記の例でこれをクエリは、所望の結果をもたらします

そして実際：GCD（242,69）= 1 = 2 * 242から7 * 69

EDIT：私は2つの制約を追加することをお勧め考え直しオン。最初にBézoutの身元をa_b_p_s_/7と呼び、a_b_p_s_/7の最初の目標の後にA #> Bと呼んでいます。上記の述語を編集し、新しい目標をマークしました。これらの追加により、eeuclid/5はより汎用性が高まります。たとえば、数字AとBがベジェ係数2と-7と1をgcdとして持つかどうかを調べることができます。このクエリには一意の答えはなく、Prologはすべての潜在的な解決策の残存目標を与えます。

?- [A,B] ins 0..50, eeuclid(A,B,2,-7,1), label([A,B]). 
A = 18, 
B = 5 ; 
A = 25, 
B = 7 ; 
A = 32, 
B = 9 ; 
A = 39, 
B = 11 ; 
A = 46, 
B = 13 ; 
false.  % <- previously loop here 

を新たに追加した制約なしでクエリを第五解決した後に終了しません。しかし、あなたはAとBのための限られた範囲を求めることができ、実際の数値を取得するにはlabel/1を使用し、その後0〜50と言います。しかし、新しい制約により、Prologは0と50の間に解がなくなることを確かめることができます。