프롤로그를 사용하여 다항식의 GCD를 계산하십시오

Question

제목 종류는 모두입니다. 두 다항식의 GCD를 계산하려고합니다. 이것이 Prolog에서 수행 될 수있는 방법이 있습니까? 그렇다면 좋은 출발점은 무엇입니까? 특히, 프롤로그를 사용하여 다항식 나누기를 구현하는 방법에 문제가 있습니다.

편집 예를 들어, 입력 및 출력을 포함합니다 :

예 입력 :

?- GCD(x^2 + 7x + 6, x2 − 5x − 6, X). 

예 출력 : 오프 기회에

X = x + 1. 

솔루션

이 다른 사람 이 작업을 수행해야합니다. 여기에 내 fi가 있습니다. 솔루션 :

tail([_|Tail], Tail). 
head([Head | _], Head). 

norm(Old, N, New) :- 
    length(Tail, N), 
    append(New, Tail, Old). 
norm(Old, N, []) :- 
    length(Old, L), 
    N > L. 

mult_GCD(List, GCD) :- length(List, L), 
    L > 2, tail(List, Tail), 
    mult_GCD(Tail, GCD). 
mult_GCD([H | T], GCD) :- 
    length(T, L), 
    L == 1, head(T, N), 
    gcd(H, N, GCD). 

lead(List, List) :- 
    length(List, L), 
    L == 1. 
lead([0 | Tail], Out) :- 
    !, lead(Tail, Out). 
lead([Head | Tail], [Head | Tail]) :- Head =\= 0. 

poly_deg([], 0). 
poly_deg(F, D) :- 
    lead(F, O), 
    length(O, N), 
    D is N - 1. 

poly_red([0], [0]). 
poly_red(Poly, Out) :- 
    mult_GCD(Poly, GCD), 
    scal_div(Poly, GCD, Out). 

poly_sub(Poly,[],Poly) :- Poly = [_|_]. 
poly_sub([],Poly,Poly). 
poly_sub([P1_head|P1_rest], [P2_head|P2_rest], [PSub_head|PSub_rest]) :- 
    PSub_head is P1_head-P2_head, 
    poly_sub(P1_rest, P2_rest, PSub_rest). 

scal_prod([],_Sc,[]). 
scal_prod([Poly_head|Poly_rest], Sc, [Prod_head|Prod_rest]) :- 
    Prod_head is Poly_head*Sc, 
    scal_prod(Poly_rest, Sc, Prod_rest). 

scal_div([],_,[]). 
scal_div([Poly_head|Poly_rest], Sc, [Prod_head|Prod_rest]) :- 
    Prod_head is Poly_head/Sc, 
    scal_div(Poly_rest, Sc, Prod_rest). 

poly_div(Num, Den, OutBuild, Out) :- 
    poly_deg(Num, X), 
    poly_deg(Den, Y), 
    X < Y, 
    Out = OutBuild. 
poly_div(INum, IDen, OutBuild, Out) :- 
    lead(INum, [NumHead | NumTail]), lead(IDen, [DenHead | DenTail]), 
    Q is NumHead/DenHead, 
    append(OutBuild, [Q], Out1), 
    append([DenHead], DenTail, DenNorm), append([NumHead], NumTail, Num), 
    scal_prod(DenNorm, Q, DenXQ), 
    poly_sub(Num, DenXQ, N), 
    poly_div(N, IDen, Out1, Out). 

poly_mod(Num, Den, Out) :- 
    poly_deg(Num, X), poly_deg(Den, Y), 
    X < Y, 
    lead(Num, Out1), 
    poly_red(Out1, Out2), 
    lead(Out2, Out). 
poly_mod(INum, IDen, Out) :- 
    lead(INum, [NumHead | NumTail]), lead(IDen, [DenHead | DenTail]), 
    Q is NumHead/DenHead, 
    append([DenHead], DenTail, DenNorm), append([NumHead], NumTail, Num), 
    scal_prod(DenNorm, Q, DenXQ), 
    poly_sub(Num, DenXQ, N), 
    poly_mod(N, IDen, Out). 

poly_gcd(X, Y, X):- poly_deg(Y, O), O == 0, !. 
poly_gcd(Y, X, X):- poly_deg(Y, O), O == 0, !. 
poly_gcd(X, Y, D):- poly_deg(X, Xd), poly_deg(Y, Yd), Xd > Yd, !, poly_mod(X, Y, Z), poly_gcd(Y, Z, D). 
poly_gcd(X, Y, D):- poly_mod(Y, X, Z), poly_gcd(X, Z, D). 

gcd(X, Y, Z) :- 
    X < 0, X > Y, !, 
    X1 is X - Y, 
    gcd(-X, Y, Z). 
gcd(X, Y, Z) :- 
    Y < 0, Y >= X, !, 
    Y1 is Y - X, 
    gcd(X, -Y, Z). 
gcd(X, 0, X). 
gcd(0, Y, Y). 
gcd(X, Y, Z) :- 
    X > Y, Y > 0, 
    X1 is X - Y, 
    gcd(Y, X1, Z). 
gcd(X, Y, Z) :- 
    X =< Y, X > 0, 
    Y1 is Y - X, 
    gcd(X, Y1, Z). 
gcd(X, Y, Z) :- 
    X > Y, Y < 0, 
    X1 is X + Y, 
    gcd(Y, X1, Z). 
gcd(X, Y, Z) :- 
    X =< Y, X < 0, 
    Y1 is Y + X, 
    gcd(X, Y1, Z). 

Answer 1

이 답변은 올바른 방향으로 밀어 넣기위한 것입니다.

먼저, x^2 + 7x + 6과 같은 표현식을 구문 분석해야한다는 것을 잊어 버리십시오. 이것은 아직 프롤로그에서 적절한 용어조차 아니다. 당신이 최고 수준에이를 작성하려고하면 오류가 발생합니다 :

?- Expr = x^2 + 7x + 6. 
ERROR: Syntax error: Operator expected 
ERROR: Expr = x^2 + 
ERROR: ** here ** 
ERROR: 7x + 6 . 

프롤로그 당신이 가지고있는 7x 처리하는 방법을 알고하지 않습니다. 식을 구문 분석하는 것은 자신의 문제, 그리고 당신이 이미 그것을 구문 분석과 같은 예를 들어 보이는 표현 입수했습니다 가정하는 경우 어쩌면 쉽게 :

[6, 7, 1] 

마찬가지로, x^2 − 5x − 6이된다을 :

[-6, -5, 1] 

지금

[] 

algorithm at the Wikipedia page를 살펴 :

및 나타내는 0 당신은 빈 목록을 사용합니다. 학위는 deg이고 주요 계수는 lc입니다. 위의 목록 표현으로, 당신은 사람들을 정의 할 수 있습니다

poly_lc(F, C) :- 
    last(F, C). 

poly_deg(F, D) :- 
    length(F, N), 
    D is N - 1. 

The leading coefficient is the last element of the list.

The degree is one less then the length of the list holding the coefficients.

당신은 또한 다항식으로 간단한 산술 연산을 수행 할 수 있어야합니다. Wikipedia page의 정의를 사용하면 예를 들어 []과 [1]을 추가하면 [1]을 얻게되며 [-2, 2]을 [1, -3, 1]과 곱하면 [-2, 8, -8, 2]이됩니다. precursory search은 나에게 this question here on Stackoverflow을주었습니다. 이 정의 술어를 사용 : 당신이 시도하고 내가 위의 링크 된 위키 문서에 설명 된대로 다항식 부문을 구현하기 위해

?- poly_prod([-2,2], [1, -3, 1], P). 
P = [-2.0, 8.0, -8.0, 2] . 

?- poly_sum([], [1], S). 
S = [1]. 

여기부터, 그것은 수 있어야한다. 더 많은 문제가 발생하면 질문을 수정하거나 새 질문을해야합니다.