多项式最大公约数C ++

Question

这是我尝试实现一个找到两个多项式的GCD的程序。我意识到除法方法存在问题。在某些情况下，在division()中递减多项式的程度的while循环进入“无穷大”，我无法理解究竟是哪个。

关于这里出了什么问题的任何线索？

#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

这似乎很可能就行了

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

什么是坏的。你的系数是浮点数。由于计算机（不幸）是有限的，因此浮点计算中会出现小错误。如果系数正好为0，则代码仅退出while循环。似乎在某些输入上，尽管它应该均匀分配，但是得到R->coeff[0] = 0.0000000001或其他一些非常小的值，它不是0。

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

（更仔细地查看代码，你也可以在其他地方进行精确的等式检查 - 这些都应该改为检查绝对值非常小。）

Answer 2

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

如果R是零多项式，那就严重错了。

Answer 3

这个C ++库实现了多项式除法：PolynomialDivHang_test_no_hang