序言扩展欧几里德算法

Question

我一直在努力与几个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中实现这个算法。

在此先感谢。

Answer 1

首先让我们来思考谓词的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和