多项式最大公约数 C++

Question

这是我尝试实现的一个程序，它可以找到两个多项式的 GCD。我意识到除法有问题。在某些情况下，一个 while 循环递减 division() 中生成的多项式的阶数进入 "infinity"，我无法理解到底是哪个。

这里有什么问题的线索吗？

#include<iostream>
#include<stdlib.h>



using namespace std;

//polynomial------------------------------
struct polynomial {
    float *coeff;
    int degree;
};

/*function declaration */
int get_data(polynomial *P); 
int display(polynomial *P);
int division(polynomial *P, polynomial *Q, polynomial *H, polynomial *R);
int polcpy(polynomial *p, polynomial *q);
void GCDPol(polynomial *P,polynomial *Q, polynomial *R);

//GCD of two polynomials------------------
void GCDpol(polynomial *P,polynomial *Q, polynomial *R) {
    polynomial *res, *v;
    res = (polynomial *) calloc(1,sizeof(polynomial));  
    v = (polynomial *) calloc(1,sizeof(polynomial));  
    while(1) {
        division(P, Q, v, R);
        if(R->degree==0 && R->coeff[0]==0)
            break;
        else
            polcpy(P,Q);
            polcpy(Q,R);
    }
    polcpy(R,Q);
    free(res);
    free(v);
}

//pol copy--------------------------------
int polcpy(polynomial *p, polynomial *q) {
    p->degree=q->degree;
    p->coeff = new float[p->degree + 1];
    for (int i=0; i<=p->degree; i++) 
        p->coeff[i]=q->coeff[i];
    return 0;
}

//division--------------------------------
int division(polynomial *P, polynomial *Q, polynomial *H, polynomial *R) {
    float u;
    int x;
    polynomial *nh, *nr;
    nh = (polynomial *) calloc(1,sizeof(polynomial));
    nr = (polynomial *) calloc(1,sizeof(polynomial));

    /*Euclidian Long Division*/
    polcpy(nr, P);  
    nh->degree = P->degree - Q->degree;
    nh->coeff = new float[nh->degree + 1];
    for (int i=nh->degree; i>=0; i--)  {
        nh->coeff[i] = nr->coeff[nr->degree] / Q->coeff[Q->degree];
        for (int j=i; j <= nr->degree; j++) {
            u = nh->coeff[i] * Q->coeff[j-i];
            nr->coeff[j] = nr->coeff[j] - u;
        }
        if (nr->degree > 0)  
            nr->degree--;
    }

    /*Quotient*/
    polcpy(H, nh);  
    /*Remainder*/   
    polcpy(R, nr);
    while(R->coeff[R->degree] == 0) {
        R->degree--;
    }   
    free(nh); 
    free(nr);
    return 0;
}

//display-------------------------------
int display(polynomial *P) {
    int i, j;
    for (i = P->degree; i >= 0; i--) {
        cout << P->coeff[i] << "x^" << i;
        if ((i - 1) != -1)
            cout << "+";
    }
    cout << "\n";
    return 0;
}

//get_data------------------------------
int get_data(polynomial *P) {
    cout << "Enter Degree Of Polynomial:";
    cin >> P->degree;
    P->coeff = new float[P->degree + 1];
    for (int i = P->degree; i >= 0; i--) {
        cout << "Enter coefficient of x^" << i << ":";
        cin >> P->coeff[i];
    }
    return 0;
}


int main() {
    polynomial *P, *Q, *R, *H;
    P = (polynomial *) calloc(1,sizeof(polynomial));
    Q = (polynomial *) calloc(1,sizeof(polynomial));
    R = (polynomial *) calloc(1,sizeof(polynomial));
    H = (polynomial *) calloc(1,sizeof(polynomial));
    cout<<"GDC\n";
    get_data(P);
    get_data(Q);
    cout << "Polynomial1:";
    display(P);
    cout << "Polynomial2:";
    display(Q);
    GCDpol(P,Q,R);
    display(R);
    free(R);
    free(P);
    free(Q);
    free(H);
    return 0;
}

Answer 1

while(R->coeff[R->degree] == 0) {
    R->degree--;
}

如果 R 是零多项式，这就大错特错了。

Answer 2

这条线似乎很可能

if(R->degree==0 && R->coeff[0]==0)
        break;

是什么坏了。你的系数是浮点数。因为计算机（不幸的是）是有限的，所以浮点数计算中会有小错误。代码仅在系数恰好为 0 时退出 while 循环。似乎在某些输入上，尽管它应该平分，但您得到 R->coeff[0] = 0.0000000001 或其他一些不完全为 0 的非常小的值。

尝试检查绝对值是否在某个非常小的公差范围内（例如 10^-10 或 10^-12。）如果您确实想要精确的值，则需要查看精确的精度浮点数，这是它自己的蠕虫。

（仔细看代码，你在其他地方也做了精确相等检查-这些应该都改为检查绝对值非常小。）

Answer 3

此 C++ 库实现多项式除法：PolynomialDivHang_test_no_hang

多项式最大公约数 C++

Polynomial Greatest Common Divisor C++

c++

polynomial-math

greatest-common-divisor

polynomials