序言擴展歐幾里德算法

我一直在努力與幾個prolog代碼幾天，我找不到出路。我想寫的擴展歐幾里德算法，並找到值p和s：序言擴展歐幾里德算法

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

方程，這裏是我曾嘗試：`

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.

後有點搜索，我發現S和p係數從1和0開始，第二個值分別爲0和1.然後它繼續一個模式，這是我在si_finder和ti_finder謂詞中完成的。常用謂詞是我試圖遞歸控制模式的地方。然而，通用謂詞在每次調用中都會返回false。任何人都可以幫助我在Prolog中實現這個算法。

在此先感謝。

來源

2017-05-27 adropintheocean

您可能會發現[視頻解釋算法（https://www.youtube.com/watch?v = hB34-GSDT3k）有幫助。我認爲你的謂詞比你真正需要的參數多得多。 – lurker

謝謝，我在搜索過程中觀看過這段視頻，但這需要返回替換，因爲我正在查找卡住的係數。我以這種方式 – adropintheocean

你可以使用約束開始根據執行我的代碼[鏈接]（https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm），找到係數。查看庫clpfd的手冊。 –

首先讓我們來思考謂詞的arity。顯然你想要有數字A和B以及Bézout係數P和S作爲參數。由於該算法正在計算GCD，因此將其作爲參數也是適合的。這留下了我們的觀點5.當我們談論擴展的歐幾里德算法時，讓我們稱謂爲eeuclid/5。其次，考慮一個例子：讓我們用算法來計算P，S和GCD爲A = 242和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

我們可以觀察以下幾點：

算法停止，如果餘量變爲0
該行中的最後一行包含在剩餘列中的GCD（在本實施例1）和在P分別爲係數的Bezout和S列（在本實施例2和-7）
商數是從以前的餘數中計算出來的。所以在下一次迭代中，A變成B，B變成B1。
P和S從它們各自的前輩計算。例如：P3 = P1-3 * P2 = 1-3 * 0 = 1和S3 = S1-3 * S2 = 0-3 * 1 = -3。既然前面兩個P和S都足夠了，我們不妨將它們作爲一對，例如， P1-P2和S1-S2。
算法開始於對病人：1-0和S：0-1
該算法以更大的數量

把這個一起啓動，調用謂詞以確保A是更大的數字，除了它的五個參數之外，它還必須將起始對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，S1是Bézout係數。否則，商Q，其餘B1和P和S中的新值被計算和a_b_p_s_/7被調用，這些新的值：

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).

上述示例查詢這產生所期望的結果：

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

的確：GCD（242,69）= 1 = 2 * 242 - 7 * 69

編輯：退一步講，我建議添加兩個約束。首先調用0123.之前Bézout的身份，0123'的第一個目標後第二A #> B。我編輯了上面的謂詞並標出了新的目標。這些增加使得eeuclid/5更通用。例如，你可以問什麼數字A和B具有Bézout係數2和-7和1作爲gcd。這個查詢沒有唯一的答案，Prolog會爲您提供每個潛在解決方案的剩餘目標。但是，你可以要求在有限的範圍內A和B，說從0到50，然後用label/1獲得實際的數字：

?- [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

沒有新增加的約束查詢第五液後也不會終止。然而，隨着新的約束Prolog是能夠確定，有沒有更多的解決方案50之間0和

來源

2017-06-07 21:45:36 tas

序言擴展歐幾里德算法

回答

相關問題