c++ - 多项式最大公约数 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;

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

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

(更仔细地查看代码，您也在其他地方进行了精确的相等检查 - 这些都应该更改为检查绝对值是否非常小。)