連合リストを使った多項式のマッチ、加算、および乗算

Question

私は乗算関数の実装からなるプログラムを書いていますが、3つの関数、つまりマッチ、加算、および乗算の問題があります。

match関数は、2つの多項式が同じかどうかを判断するものとします。 trueの場合はtrueを返し、そうでない場合はfalseを返します。

関数を追加すると、2つの多項式が追加されます。

乗算は、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 

のようなものは、各多項式中の用語の同じ番号を持っているので、この検索を最初にチェックしている場合があります。次に、第1の多項式の各項について、第2の多項式に一致する項があるかどうかを調べる。項が一致しない場合、多項式は一致せず、すぐに戻ることができます。

これは、最初の2つの異なる用語に一致する2番目の多項式の項を持つことはできないと仮定します。より洗練された手法では、第2の多項式の各項にフラグを設定して、すでに一致しているかどうかをチェックすることができます。

追加するには、一致する用語を見つけて係数を追加します。一致するものがない場合は、その用語を追加します。ここではおそらく、フラグを使用して、2番目の多項式のどの項が一致しているかを検出したいと考えています。あるいは、一致した項を2番目の多項式から削除することもできます。

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) 

をチェックするために、既存のすべての条項をループは、単に追加する2本のスマートaddメソッドで

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 

なりますaddメソッドを持っています多項式は今や自明になります

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