在 C 中包含 3 个变量的多项式加法

Question

这是给我们的编码练习。我见过很多例子，但它们大多只使用一个变量 x。对于这个，两个多项式最多可以包含 3 个变量。

让我解释一下输入。第一行表示第一个多项式的项数（非零系数）n。接下来的 n 行以 x exponent y exponent z exponent coefficient 的形式表示第一个多项式的每一项。示例：4x⁵y⁴z² 将是 5 4 2 4。下一行是同样的事情，但它是针对第二个多项式的。我们要 return 结果总和并按规范顺序逐行打印。系数是一个实数，可以是有符号或无符号的。我会提供一个测试用例。

我已经研究并制定了所有任务。事实上，我将提供的测试用例可以通过我的代码正确回答。我的问题是，在隐藏的情况下，我的代码给出了错误的答案，我开始认为我的算法遗漏了什么。

无论如何，这是我的全部代码。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>

struct Node
{

    float coeff;
    int powX;
    int powY;
    int powZ;
    struct Node* next;
};


void readPolynomial(struct Node** poly)
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    *poly = temp;

    int terms;
    fscanf(stdin, "%d", &terms);
    getchar();

    char entry[999999];
    char *splitter;
    for(int i = 0; i < terms; i++)
    {
        fgets(entry, sizeof(entry), stdin);
        splitter = strtok(entry," ");
        temp->powX = atoi(splitter);
        splitter = strtok(NULL, " ");
        temp->powY = atoi(splitter);
        splitter = strtok(NULL, " ");
        temp->powZ = atoi(splitter);
        splitter = strtok(NULL, " ");
        temp->coeff = atof(splitter);
        temp->next = NULL;
        if(i != terms-1)
        {
            temp->next = (struct Node*)malloc(sizeof(struct Node));
            temp = temp->next;
            temp->next = NULL;
        }
    }
}

int compareTerms(const struct Node *a, const struct Node *b)
{
    int cmp;

    cmp = (a->powX > b->powX) - (a->powX < b->powX);
    if (cmp != 0) {
        return cmp;
    }
    cmp = (a->powY > b->powY) - (a->powY < b->powY);
    if (cmp != 0) {
        return cmp;
    }
    cmp = (a->powZ > b->powZ) - (a->powZ < b->powZ);
    return cmp;
}

void sortPolynomialTerms(struct Node **poly)
{
    struct Node *head;
    unsigned int sublen;

    head = *poly;
    if (!head) {

        return;
    }

    sublen = 1;
    while (1) {
        struct Node *tail;
        struct Node *p;
        struct Node *q;
        struct Node *e;
        unsigned int plen;
        unsigned int qlen;
        unsigned int merges;
        unsigned int i;

        p = head;
        head = NULL;
        tail = NULL;
        merges = 0;
        while (p) {
            merges++;
            q = p;
            plen = 0;
            for (i = 0; i < sublen; i++) {
                plen++;
                q = q->next;
                if (!q) {
                    break;
                }
            }

            qlen = plen;

            while (plen || (qlen && q)) {
                if (!plen || (qlen && q && compareTerms(p, q) < 0)) {
                    e = q;
                    q = q->next;
                    qlen--;
                } else {
                    e = p;
                    p = p->next;
                    plen--;
                }
                if (tail) {
                    tail->next = e;
                } else {
                    head = e;
                }
                tail = e;
            }

            p = q;
        }
        tail->next = NULL;

        if (merges <= 1) {
            break;
        }

        sublen *= 2;
    }

    *poly = head;
}

void printPolynomial(const struct Node *poly)
{
    while (poly)
    {
        if(poly->coeff != 0)
        {
                printf("%d %d %d %.3f\n", poly->powX, poly->powY, poly->powZ, poly->coeff);
        }
        poly = poly->next;
    }
}

void canonicalPolynomial(struct Node **poly)
{
    sortPolynomialTerms(poly);
    printPolynomial(*poly);
}

void addPolynomials(struct Node** result, struct Node* first, struct Node* second)
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->next = NULL;
    *result = temp;
    while(first && second)
    {
        if(compareTerms(first, second) < 0)
        {
            temp->coeff = second->coeff;
            temp->powX = second->powX;
            temp->powY = second->powY;
            temp->powZ = second->powZ;
            second = second->next;

        }
        else if(compareTerms(first, second) > 0)
        {
            temp->coeff = first->coeff;
            temp->powX = first->powX;
            temp->powY = first->powY;
            temp->powZ = first->powZ;
            first = first->next;
        }
        else
        {
            temp->coeff = first->coeff + second->coeff;
            temp->powX = first->powX;
            temp->powY = first->powY;
            temp->powZ = first->powZ;
            first = first->next;
            second = second->next;
        }
        if(first && second)
        {
            temp->next = (struct Node*)malloc(sizeof(struct Node));
            temp = temp->next;
            temp->next = NULL;
        }
    }
    while(first || second)
    {
        temp->next = (struct Node*)malloc(sizeof(struct Node));
        temp = temp->next;
        temp->next = NULL;

        if(second)
        {
            temp->coeff = second->coeff;
            temp->powX = second->powX;
            temp->powY = second->powY;
            temp->powZ = second->powZ;
            second = second->next;
        }

        else if(first)
        {
            temp->coeff = first->coeff;
            temp->powX = first->powX;
            temp->powY = first->powY;
            temp->powZ = first->powZ;
            first = first->next;
        }
    }
}

int main()
{
    struct Node* first = NULL;
    struct Node* second = NULL;
    struct Node* result = NULL;

    readPolynomial(&first);
    readPolynomial(&second);
    addPolynomials(&result, first, second);
    canonicalPolynomial(&result);
    return 0;
}

测试用例：

预期输出：

7 0 0 1.000
5 3 2 4.000
1 6 0 -7.000
1 3 0 3.000
1 2 3 4.000
1 0 1 9.000
0 7 0 -8.000

解释：

     x⁷           - 7xy⁶                       - 6y⁷
 +        4x⁵y³z²        + 3xy³ + 4xy²z³ + 9xz - 2y⁷

 =   x⁷ + 4x⁵y⁴z² - 7xy⁶ + 3xy³ + 4xy²z³ + 9xz - 8y⁷

最初，我认为我的 addPolynomial 功能有问题。我只是从一个变量的多项式加法的示例代码中取出它并做了一些修改。

checkTerms遍历整个多项式，如果相邻项的度数相同，则相加

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>

struct Node
{

    float coeff;
    int powX;
    int powY;
    int powZ;
    struct Node* next;
};


void readPolynomial(struct Node** poly)
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    *poly = temp;

    int terms;
    fscanf(stdin, "%d", &terms);
    getchar();

    char entry[30];
    char *splitter;
    for(int i = 0; i < terms; i++)
    {
        fgets(entry, sizeof(entry), stdin);
        splitter = strtok(entry," ");
        temp->powX = atoi(splitter);
        splitter = strtok(NULL, " ");
        temp->powY = atoi(splitter);
        splitter = strtok(NULL, " ");
        temp->powZ = atoi(splitter);
        splitter = strtok(NULL, " ");
        temp->coeff = atof(splitter);
        temp->next = NULL;
        if(i != terms-1)
        {
            temp->next = (struct Node*)malloc(sizeof(struct Node));
            temp = temp->next;
            temp->next = NULL;
        }
    }
}

int compareTerms(const struct Node *a, const struct Node *b)
{
    int cmp;

    cmp = (a->powX > b->powX) - (a->powX < b->powX);
    if (cmp != 0) {
        return cmp;
    }
    cmp = (a->powY > b->powY) - (a->powY < b->powY);
    if (cmp != 0) {
        return cmp;
    }
    cmp = (a->powZ > b->powZ) - (a->powZ < b->powZ);
    return cmp;
}

void sortPolynomialTerms(struct Node **poly)
{
    struct Node *head;
    unsigned int sublen;

    head = *poly;
    if (!head) {

        return;
    }

    sublen = 1;
    while (1) {
        struct Node *tail;
        struct Node *p;
        struct Node *q;
        struct Node *e;
        unsigned int plen;
        unsigned int qlen;
        unsigned int merges;
        unsigned int i;

        p = head;
        head = NULL;
        tail = NULL;
        merges = 0;
        while (p) {
            merges++;
            q = p;
            plen = 0;
            for (i = 0; i < sublen; i++) {
                plen++;
                q = q->next;
                if (!q) {
                    break;
                }
            }

            qlen = plen;

            while (plen || (qlen && q)) {
                if (!plen || (qlen && q && compareTerms(p, q) < 0)) {
                    e = q;
                    q = q->next;
                    qlen--;
                } else {
                    e = p;
                    p = p->next;
                    plen--;
                }
                if (tail) {
                    tail->next = e;
                } else {
                    head = e;
                }
                tail = e;
            }

            p = q;
        }
        tail->next = NULL;

        if (merges <= 1) {
            break;
        }

        sublen *= 2;
    }

    *poly = head;
}

void printPolynomial(const struct Node *poly)
{
    while (poly)
    {
        if(poly->coeff != 0)
        {
                printf("%d %d %d %.3f\n", poly->powX, poly->powY, poly->powZ, poly->coeff);
        }
        poly = poly->next;
    }
}

void canonicalPolynomial(struct Node **poly)
{
    sortPolynomialTerms(poly);
    printPolynomial(*poly);
}

void checkTerms(struct Node* poly)
{
    while(poly)
    {
        if(poly->next != NULL)
        {
            if(compareTerms(poly, poly->next) == 0)
            {
                poly->coeff = poly->coeff + poly->next->coeff;
                poly->next = poly->next->next;
            }
        }
        poly = poly->next;
    }
}


void addPolynomials(struct Node** result, struct Node* first, struct Node* second)
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->next = NULL;
    *result = temp;
    while(first && second)
    {
        if(compareTerms(first, second) < 0)
        {
            temp->coeff = second->coeff;
            temp->powX = second->powX;
            temp->powY = second->powY;
            temp->powZ = second->powZ;
            second = second->next;

        }
        else if(compareTerms(first, second) > 0)
        {
            temp->coeff = first->coeff;
            temp->powX = first->powX;
            temp->powY = first->powY;
            temp->powZ = first->powZ;
            first = first->next;
        }
        else
        {
            temp->coeff = first->coeff + second->coeff;
            temp->powX = first->powX;
            temp->powY = first->powY;
            temp->powZ = first->powZ;
            first = first->next;
            second = second->next;
        }
        if(first && second)
        {
            temp->next = (struct Node*)malloc(sizeof(struct Node));
            temp = temp->next;
            temp->next = NULL;
        }
    }
    while(first || second)
    {
        temp->next = (struct Node*)malloc(sizeof(struct Node));
        temp = temp->next;
        temp->next = NULL;

        if(second)
        {
            temp->coeff = second->coeff;
            temp->powX = second->powX;
            temp->powY = second->powY;
            temp->powZ = second->powZ;
            second = second->next;
        }

        else if(first)
        {
            temp->coeff = first->coeff;
            temp->powX = first->powX;
            temp->powY = first->powY;
            temp->powZ = first->powZ;
            first = first->next;
        }
    }
}

int main()
{
    struct Node* first = NULL;
    struct Node* second = NULL;
    struct Node* result = NULL;

    readPolynomial(&first);
    readPolynomial(&second);
    sortPolynomialTerms(&first);
    checkTerms(&first);
    sortPolynomialTerms(&second);
    checkTerms(&second);
    addPolynomials(&result, first, second);
    canonicalPolynomial(&result);
    return 0;
}

Answer 1

不需要使用列表。由于引入的多项式的大小是预先给定的，因此可以分配一个足够的。接下来使用 realloc() 加载另一个多项式。零系数的定义存在问题。应指定精度。我假设它是 0.

问题可以分阶段解决：

读取第一个多项式的大小
分配数组
加载第一个多项式
读取第二个多边形的大小
重新分配数组以适应两个多项式
阅读第二个多边形
对项进行排序以确保所有具有相同指数的项都是邻居
累积具有相同指数的连续项块
打印结果

代码。省略了错误处理。

#include <stdio.h>
#include <stdlib.h>

struct term {
    int x, y, z;
    double coef;
};

struct term load_term() {
    struct term T;
    scanf("%d %d %d %lf", &T.x, &T.y, &T.z, &T.coef);
    return T;
}

int term_cmp(const void *a_, const void *b_) {
    const struct term *a = a_, *b = b_;
    if (a->x != b->x) return b->x - a->x;
    if (a->y != b->y) return b->y - a->y;
    return b->z - a->z;
}

int main() {
    int n = 0, m;

    // load first polynomial
    scanf("%d", &m);
    struct term *P = malloc(m * sizeof *P);
    while (m--) P[n++] = load_term();

    // load second polynomial
    scanf("%d", &m);
    P = realloc(P, (n + m) * sizeof *P);
    while (m--) P[n++] = load_term();

    // sort by x,y,z exponents
    qsort(P, n, sizeof *P, term_cmp);

    // merge
    int n2 = 0;
    for (int i = 0; i < n; ++i) {
        if (n2 > 0 && term_cmp(&P[n2 - 1], &P[i]) == 0) {
            // as long as exponents are the same as the last
            // accumulate coefficients to the last term
            P[n2 - 1].coef += P[i].coef;
        } else {
            // start a new term
            P[n2++] = P[i];
        }
    }

    // print accumulated polynomial of size `n2`
    for (int i = 0; i < n2; ++i)
           if (P[i].coef != 0)
        printf("%d %d %d %.3lf\n", P[i].x, P[i].y, P[i].z, P[i].coef);

    free(P);
}

Answer 2

我认为它可以写得更简洁。你能试试这个代码吗？我的方法与@tsanisl 的方法非常相似。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<float.h>

static int comparefn(const void *a, const void *b)
{
  const double *l= (const double *) a;
  const double *r= (const double *) b;
  for(int i= 0; i< 3; ++i) {
    if(l[i]< r[i]) { return -1; }
    if(l[i]> r[i]) { return 1; }
    if(l[0]== r[0]) { continue; }
  }
  return 0;
}

double *data= NULL;
int main(int argc, char *argv[])
{
  int n1= 0;
  scanf("%d", &n1);
  data= malloc(sizeof(double)* n1* 4);
  int i= 0;
  for(; i< n1; ++i) {
    scanf("%lf %lf %lf %lf", data+ i* 4, data+ i* 4+ 1, data+ i* 4+ 2, data+ i* 4+ 3);
  }

  int n2= 0;
  scanf("%d", &n2);
  data= realloc(data, sizeof(double)* (n1+ n2)* 4);
  for(; i< n1+ n2; ++i) {
    scanf("%lf %lf %lf %lf", data+ i* 4, data+ i* 4+ 1, data+ i* 4+ 2, data+ i* 4+ 3);
  }

  qsort(data, ((size_t) (n1+ n2)), sizeof(double)* 4, &comparefn);
  for(i= 1; i< n1+ n2; ++i) {
    if(0== comparefn(data+ i* 4, data+ (i- 1)* 4)) {
      data[i* 4+ 3]+= data[(i- 1)* 4+ 3]; data[(i- 1)* 4+ 3]= 0.0;
    }
  }
  for(i= n1+ n2- 1; i> -1; --i) {
    if(fabs(data[i* 4+ 3])> DBL_EPSILON) {
      printf("%g %g %g %.3lf\n", data[i* 4], data[i* 4+ 1], data[i* 4+ 2], data[i* 4+ 3]);
    }
  }

  if(NULL!= data) {
    free(data);
    data= NULL;
  }

  return 0;
}

在 C 中包含 3 个变量的多项式加法

Polynomial Addition that contains 3 variables in C

c

struct

linked-list

polynomials