Как умножить многочлены в C?

Question

Надеюсь, этот код имеет смысл ..... Я создаю два многочлена и попытаюсь их размножить. Проблема в том, что я не знаю, что я должен сделать, чтобы умножить их должным образом. Эта программа умножает полиномы, сохраняет результат в другой полином, но не добавляет коэффициенты с одинаковой степенью.

Что делать, чтобы это сделать? Также как я должен использовать free() в этой программе?

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

typedef struct poly { 
    int coef; 
    int exp; 
    struct poly *next; 
} poly; 

int main(void) { 
    poly * po1, *head, *po2, *head2, *po3, *head3 = NULL; 
    int sel, c = 1; 

    head = NULL; 
    printf(
     "\nInsert elements for the first polynomial from the biggest to the smallest power of x. (Enter a power of zero (0) to stop)\n"); 
    while (1) { 
    po1 = (poly *) malloc(sizeof(poly)); 
    printf("Give number: "); 
    scanf("%d", &po1->coef); 
    printf("Give power of x: "); 
    scanf("%d", &po1->exp); 
    po1->next = head; 
    head = po1; 
    if (po1->exp == 0) break; 
    } 

    head2 = NULL; 
    printf(
     "\nInsert elements for the second polynomial from the biggest to the smallest power of x. (Enter a power of zero (0) to stop)\n"); 
    while (1) { 
    po2 = (poly *) malloc(sizeof(poly)); 
    printf("Give number: "); 
    scanf("%d", &po2->coef); 
    printf("Give power of x: "); 
    scanf("%d", &po2->exp); 
    po2->next = head2; 
    head2 = po2; 
    if (po2->exp == 0) break; 
    } 

    po1 = head; 
    po2 = head2; 

    printf("Multiplying********\n"); 
    po1 = head; 
    po2 = head2; 
    while (po1 || po2) { 
    po2 = head2; 
    while (po1 && po2) { 
     po3 = (poly *) malloc(sizeof(poly)); 
     po3->coef = (po1->coef) * (po2->coef); 
     po3->exp = (po1->exp) + (po2->exp); 
     po3->next = head3; 
     head3 = po3; 
     po2 = po2->next; 
    } 
    po1 = po1->next; 
    } 
    while (po3) { 
    printf("%+d(x^%d)", po3->coef, po3->exp); 
    po3 = po3->next; 
    } 
    printf("\n"); 

} 

} 

Answer 1

У вас есть два варианта:

• сделать второй проход (например, сортировать по коэффициентам), и объединить коэффициенты с той же силой.
• Сделайте умножение, как вы делаете это на бумаге, вычислите суммы для столбцов (это может быть скользящая сумма). Самый простой способ сделать это - сначала выполнить добавление.

Answer 2

Для начала вам понадобится более организованный способ добавления терминов к полиномам. Недостаточно просто добавлять новые коэффициенты в конец списка. Вам нужно найти правильную позицию в списке и добавить туда многочлен.

// Adds coef * x^exp to poly. 
void poly_add (poly ** add2me, int coef, int exp) 
{ 
    poly ** p; 

    // printf ("poly_add %d %d\n", coef, exp); 

    // Advance p to the first node such that 
    // *p is either the correct term or the subsequent term. 
    for (p = add2me; *p != NULL && (*p)->exp > exp; p = &(*p)->next); 

    // If *p is too small a coefficient/NULL, 
    // then it's pointing to the next term and you need to make a new node 
    if (*p == NULL || (*p)->exp < exp) 
    { 
     poly * new_poly = malloc(sizeof(poly)); 
     new_poly->coef = coef; 
     new_poly->exp = exp; 
     new_poly->next = *p; 
     *p = new_poly; 
    } 
    // Else *p is the correct exponent, in which case we add... 
    else 
    { 
     (*p)->coef += coef; 
    } 
} 

Тогда это всего лишь небольшая модификация вашего цикла умножения, чтобы заставить все работать.

printf("Multiplying********\n"); 
po1 = head; 
po2 = head2; 
po3 = NULL; 

while(po1||po2){ 
    po2 = head2; 
    while(po1&&po2) { 
     int new_coef = (po1->coef)*(po2->coef); 
     int new_exp = (po1->exp)+(po2->exp); 
     poly_add(&po3, new_coef, new_exp); 

     po2 = po2->next; 
    } 
    po1 = po1->next; 
} 

---

Добавление: free()

Каждый многочлен связанный список, так что вы хотите, чтобы вручную очистить полиномы потом с общей функцией список уничтожения, ...

void poly_free (poly * free_me) 
{ 
    poly * next; 
    for (; free_me != NULL; free_me = next) 
    { 
    next = free_me->next; // Safe because free_me != NULL 
    free(free_me); 
    } 
} 

Просто назовите это для каждого полинома, который вы делаете до завершения программы. Такие инструменты, как valgrind, помогут вам узнать, не утечка памяти.

Answer 3

Расширения на моем комментарии ...

Вы будете иметь гораздо проще время на управление коэффициентами, если хранить их в массивах таким образом, что позиция массива соответствует экспоненту. Например, вы бы представить 3.0x2 - 2.0x + 1.0 в

double c[3] = { 1.0, -2.0, 3.0 }; 

Таким образом, второй степени многочлен требует массив 3-элементный, 3-й степени многочлен требует массив 4-элементный и т.д.

перемножения двух полиномы затем становится простым вложенным циклом:

void polymul(double *x, size_t xsize, double *y, size_t ysize, double *r, size_t rsize) 
{ 
    memset(r, 0, sizeof *r * rsize); 

    for (size_t i = 0; i < xsize; i++) 
    { 
    for (size_t j = 0; j < ysize; j++) 
    { 
     r[i + j] += x[i] * y[j]; 
    } 
    } 
} 

Жизнь также будет проще, если вы выделите ввод/вывод и управление памятью из расчета.Если вы знаете, как большой ваши входные многочлены, вы знаете, как большой выходной полином должен быть:

double *x, *y; 
size_t xsize, ysize; 

getcoeffs(&x, &xsize); 
getcoeffs(&y, &ysize); 

size_t rsize = xsize + ysize - 1; 
double *r = malloc(sizeof *r * rsize); 

polymul(x, xsize, y, ysize, r, rsize); 
... 
free(r); 
free(x); 
free(y); 

Если вы обязались использовать список структур подхода, то ответ QuestionC является хорошим. Я просто думаю, что этот подход намного проще.