Соответствие, добавление и умножение для многочленов с использованием связанного списка

Question

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

Функция совпадения должна указывать, совпадают ли 2 полинома. если так возвращает true, else false.

Добавить функцию jut добавляет 2 полинома.

Умножение только дает произведение двух полиномов.

Я зациклился на том, как начать эти функции. Любые советы или отзывы будут полезны. Огромное спасибо.

class Dlist 
{ 
private: 
Node* front; 
public: 
Dlist(Node* f = NULL){front = f;} 

void insertInOrder(int c, int x, int y) 
{ 
    Node* nn = new Node; 
    nn->coef = c; 
    nn->xdeg = x; 
    nn->ydeg = y; 
    int nsum = x + y; 

    Node* p = front; 


    if(front == NULL){ 
     front = nn; 
     return; 
    } 
    while(p != NULL){ 
     if(x == p->xdeg && y == p->ydeg){ 
      p->coef += c; 
      return; 
     } 
     p = p->next; 
    } 
    p = front; 
    if(nsum > p->xdeg + p->ydeg){ 
     nn->next = p; 
     front = nn; 
     return; 
    } 
    else{ 
     while(p->next != NULL && p->next->xdeg + p->next->ydeg > nsum){ 
      p = p->next; 
     } 
    } 
    nn->next = p->next; 
    p->next = nn; 
    return; 
}; 

void print() 
{ 
    Node* p = front; 
    while(p != NULL){ 
     cout << p->coef << "/" << p->xdeg << "/" << p->ydeg << " -> "; 
     p = p->next; 
    } 
    cout << "NULL" << endl; 
    return; 
}; 

int degree() 
{ 
    Node* p = front; 
    int maxd = 0; 

    while(p != NULL){ 
     if(maxd < p->xdeg + p->ydeg){ 
      maxd = p->xdeg + p->ydeg; 
     } 
     p = p->next; 
    } 

    return maxd; 
}; 

void coefficient(int input) 
{ 
    Node* p = front; 
    int index = 0; 
    while(p != NULL){ 
     p = p->next; 
     index++; 
    } 
    if(input < 0){ 
     cout << "Does not exist." << endl; 
     return; 
    } 
    else if(input > index){ 
     cout << "Does not exist." << endl; 
     return; 
    } 
    p = front; 
    for(int i = 0; i != input; i++){ 
     p = p->next; 
    } 
    cout << p->coef << endl; 
    return; 
} 
void sum() 
{ 


} 

};

Answer 1

Если мы думаем о psudocode для каждого алгоритма вы можете иметь что-то вроде

function match(poly1,poly2): 
    if(length(poly1) != length(poly2)) return false 
    foreach term1 in poly1: 
     boolean termmatched=false 
     foreach term2 in poly2: 
      if matchterms(term1,term2): 
       termmatched = true 
       break 
     endfor 
     if not termmatched: 
      return false 
    endfor 
    return true 
endfunction 

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

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

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

function add(poly1,poly2): 
    boolean flags[length(poly2)] // array of flags all false 
    polynomial result = empty polynomial 
    foreach term1 in poly1: 
     boolean termmatched=false 
     int i=0 
     foreach term2 in poly2: 
      if matchterms(term1,term2): 
       result.add(new term(term1.coef+term2.coef,term1.xdeg,term1.ydeg)) 
       flags[i]=true // mark flag for second term as matched 
       termmatched = true 
       break 
      ++i 
     endfor 
     if not termmatched: 
      result.add(new term(term1.coef,term1.xdeg,term1.ydeg)) 
    endfor 

    i =0 
    foreach term2 in poly2: 
     if(not flags[i]) 
      result.add(new term(term1.coef,term1.xdeg,term1.ydeg)) 
    endfor 
endfunction 

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

class polynomial 

methods add(coef,xord,yord): 
    foreach term: 
     if match(term,xord,yord): 
      term.coef += coef 
      return 
    endfor 
    // add a new term on the end of the linked list 
    insertInOrder(coef,xord,yord) 

с этим методом умножения становится просто

function multiply(poly1,poly2): 
    result = new polynomial 
    foreach term1 in poly1: 
     foreach term2 in poly2: 
      result.add(term1.coef*term2.coef, 
       term1.xord + term2.xord, 
       term1.yord + term2.yord) 
     endfor 
    endfor 
    return result 
endfunction 

С этим умным способом добавить добавление двух полиномы теперь становятся тривиальными

function add(poly1,poly2): 
    result = new polynomial 
    foreach term1 in poly1: 
     result.add(term1.coef,term1.xord,term1.yord) 
    endfor 
    foreach term2 in poly2: 
     result.add(term2.coef,term2.xord,term2.yord) 
    endfor 
    return result 
endfunction