如何用Prolog实现多项式重根判断？

作为Prolog新手，你已经搞定了多项式求导这一步，真不错！其实判断多项式有没有重根，完全不用直接去求解根——我们可以利用**多项式最大公因式（GCD）**的数学性质来简化问题：如果原多项式和它的导数存在次数≥1的公因式，那就说明这个多项式有重根。

为什么这个方法可行？简单说：如果多项式P(x)有重根r，那么(x-r)²会整除P(x)，对应的(x-r)就会整除P(x)的导数P’(x)，所以P(x)和P’(x)的GCD就不是常数（次数≥1）。反过来，如果两者的GCD次数≥1，说明它们有公因式，对应公根也就是P(x)的重根。

下面一步步实现这个逻辑：

1. 完善多项式求导函数 #

先把你提到的求导思路落地，处理系数列表（最高次项在前，比如[3,2,1]对应3x²+2x+1），同时处理前导零的情况让结果更整洁：

% derivative(+Polynomial, -Derivative)
% 输入系数列表（高次到低次），输出导数的系数列表
derivative([], []).
derivative([_], []). % 常数项的导数为0，用空列表表示
derivative(Poly, Deriv) :-
    length(Poly, Len),
    HighestDegree is Len - 1,
    derivative_helper(Poly, HighestDegree, DerivTemp),
    drop_leading_zeros(DerivTemp, Deriv).

derivative_helper([], _, []).
derivative_helper([Coeff|Rest], Degree, [NewCoeff|DerivRest]) :-
    NewCoeff is Coeff * Degree,
    NextDegree is Degree - 1,
    derivative_helper(Rest, NextDegree, DerivRest).

% 移除前导零（可选，但让结果更干净）
drop_leading_zeros([0|Rest], Result) :-
    drop_leading_zeros(Rest, Result).
drop_leading_zeros(List, List).

2. 实现多项式基本运算 #

求GCD需要用到多项式的加减乘除，先实现这些基础工具：

% 获取多项式次数（最高非零项的指数）
degree(Poly, Deg) :-
    drop_leading_zeros(Poly, CleanPoly),
    length(CleanPoly, Len),
    Deg is Len - 1.

% 给多项式补零到指定次数
pad_with_zeros(Poly, MaxDeg, Padded) :-
    degree(Poly, Deg),
    NumZeros is MaxDeg - Deg,
    length(Zeros, NumZeros),
    maplist(=(0), Zeros),
    append(Poly, Zeros, Padded).

% 多项式加法
poly_add(A, B, Sum) :-
    degree(A, DegA),
    degree(B, DegB),
    MaxDeg is max(DegA, DegB),
    pad_with_zeros(A, MaxDeg, APadded),
    pad_with_zeros(B, MaxDeg, BPadded),
    maplist(add_pair, APadded, BPadded, SumTemp),
    drop_leading_zeros(SumTemp, Sum).

add_pair(X, Y, Z) :- Z is X + Y.

% 多项式减法（转为加负多项式）
poly_subtract(A, B, Diff) :-
    maplist(negate, B, NegB),
    poly_add(A, NegB, Diff).

negate(X, Y) :- Y is -X.

% 多项式乘法
poly_multiply(A, B, Product) :-
    degree(A, DegA),
    degree(B, DegB),
    TotalDeg is DegA + DegB,
    length(Product, TotalDeg + 1),
    maplist(=(0), Product),
    multiply_helper(A, DegA, B, DegB, Product).

multiply_helper([], _, _, _, _).
multiply_helper([CoeffA|RestA], DegA, B, DegB, Product) :-
    multiply_term_by_poly(CoeffA, DegA, B, DegB, Temp),
    poly_add(Product, Temp, NewProduct),
    NextDegA is DegA - 1,
    multiply_helper(RestA, NextDegA, B, DegB, NewProduct).

multiply_term_by_poly(CoeffA, DegA, B, DegB, Temp) :-
    Shift is DegA,
    length(PreZeros, Shift),
    maplist(=(0), PreZeros),
    maplist(multiply_by(CoeffA), B, ScaledB),
    append(PreZeros, ScaledB, Temp).

multiply_by(Factor, X, Result) :- Result is X * Factor.

% 多项式除法（求余式，用于GCD）
poly_divide(Dividend, Divisor, Quotient, Remainder) :-
    degree(Dividend, DegD),
    degree(Divisor, DegV),
    (DegD < DegV ->
        Quotient = [],
        Remainder = Dividend
    ;
        nth0(0, Dividend, CoeffD),
        nth0(0, Divisor, CoeffV),
        LeadQCoeff is CoeffD / CoeffV,
        LeadQDegree is DegD - DegV,
        length(LeadQList, LeadQDegree + 1),
        nth0(0, LeadQList, LeadQCoeff),
        maplist(=(0), LeadQListRest),
        length(LeadQListRest, LeadQDegree),
        append([LeadQCoeff], LeadQListRest, LeadQ),
        poly_multiply(Divisor, LeadQ, TempPoly),
        poly_subtract(Dividend, TempPoly, NewDividend),
        poly_divide(NewDividend, Divisor, QuotientRest, Remainder),
        poly_add(LeadQ, QuotientRest, Quotient)
    ).

3. 实现多项式GCD算法 #

用欧几里得算法，和整数GCD逻辑类似，不断用前一个多项式除以后一个多项式取余，直到余式为零：

% poly_gcd(+A, +B, -GCD)
poly_gcd(A, B, GCD) :-
    drop_leading_zeros(A, CleanA),
    drop_leading_zeros(B, CleanB),
    (CleanB = [] ->
        GCD = CleanA
    ;
        poly_divide(CleanA, CleanB, _, Remainder),
        poly_gcd(CleanB, Remainder, GCD)
    ).

4. 判断重根的核心函数 #

结合求导和GCD，只要GCD的次数≥1，就说明存在重根：

% has_multiple_root(+Polynomial)
% 当多项式存在重根时成功返回
has_multiple_root(Poly) :-
    derivative(Poly, Deriv),
    drop_leading_zeros(Deriv, CleanDeriv),
    CleanDeriv \= [], % 导数为零说明原多项式是常数，无重根
    poly_gcd(Poly, CleanDeriv, GCD),
    degree(GCD, Deg),
    Deg >= 1.

测试例子 #

% 测试1: (x-1)² = x²-2x+1，存在重根
?- has_multiple_root([1,-2,1]).
true.

% 测试2: 3x²+2x+1，无重根
?- has_multiple_root([3,2,1]).
false.

% 测试3: (x-1)³ = x³-3x²+3x-1，存在重根
?- has_multiple_root([1,-3,3,-1]).
true.

注意事项 #

上面的代码用了浮点数运算，对于整数系数的多项式可能存在精度问题。如果需要精确处理，可以把系数表示为有理数（分子+分母的元组），修改加减乘除操作来处理分数运算，避免浮点数误差。

内容的提问来源于stack exchange，提问作者A.A.