[データ構造]多項式-DT、表示方法、多項式加算

10997 ワード
データ構造 テキストリンク

多項式

  • a∗xea * x^ea∗xe
  • a=係数
  • x=変数
  • e=指数

    • 多項式ADT

  • object
  • p(x) = a1 x^e1 + a2 x^e2 + ... + an * x^en
  • :指数(指数)、係数(係数)の順序対
  • functions
  • Polynomial ZeroP() : return p(X)=0
  • Boolean IsZeroP(p) : if (poly) return FALSE else return TRUE
  • Coefficient coef(p, e) : if ( ∈ p) return c else return 0
  • Exponent maxExp(p):return max(最高差を返す)
  • Polynomial addTerm(p, c, e) if(∈p)エラーelse戻り挿入poly
  • Polynomial delTerm(p, e) if(∈p)削除したpolyese戻りエラー
    • を返します.
  • Polynomial singleMult(p, c, e) return poly c x^e
  • Polynomial polyAdd(p1, p2) return p1 + p2
  • Polynomial polyMult(p2, p2) return p1 * p2

    • 多項式演算の実現

  • 多項式の生成
  • zeroP()およびaddTerm()を使用して作成
  • addTerm(addTerm(addTerm(zeroP(), a, 3), b, 2), 5, 0) 
      = $a*x^3 + b*x^2+5$표
  • プレゼンテーションの仮定
  • 指数降順で
    • を並べる
  • すべての指数は
    • とは異なります.
    係数が0の項
  • を含まない

    • 表示方法


    1ππはすべての差のカウント値を配列として格納する
     typedef struct {
		int degree;
		float coef[MAX_DEGREE];
} polynomial;
  • は多項式a={5,{10,0,0,6,3}を表す.
    • 係数が0の場合、メモリの浪費が深刻です.
    2▼▼▼▼指数と係数が存在する港湾配列
    #define MAX_TERMS 100 // 지수가 존재하는 term 최대수 

typedef struct {
		float coef; //계수
		float expon; //지수
} polynomial;

polynomial term [MAX_TERMS];
int avail = 0; // 다음 번 빈 슬롯의 array index 번호 유지

  • 表示法:terms[MAX TERMS]={{10,5},{6,1},{3,0}

  • 1つの配列は複数の多項式を表すことができる

    • プラス
  • 多項式
    • ▼0▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼2倍

    多項式加算関数を表すアルゴリズム

    polyAdd(p1, p2)
    // p3 = p1 + p2 : 다항식 p1과 p2를 더한 결과 p3을 반환
    p3 = zeroP();
    while (not isZeroP(p1) and not isZeroP(p2) do {
        case {
            maxExp(p1) < maxExp(p2) :
                p3=addTerm(p3, coef((p2), maxExp(p2)), maxExp(p2);
                p2=delTerm(p2, maxExp(p2));
            maxExp(p1) = maxExp(p2) :
                sum=coef(p1, maxExp(p1)) + coef(p2, maxExp(p2));
                if (sum != 0) then p3 = addTerm(p3, sum, maxExp(p1));
                p1 = delTerm(p1, maxExp(p1));
                p2 = delTerm(p2, maxExp(p2));
            maxExp(p1) > maxExp(p2) :
                p3 = addTerm(p3, coef(p1, maxExp(p1)), maxExp(p1));
                p1 = delTerm(p1, maxExp(p1));
        }
    }
    if (not isZero(p1)) then p1의 나머지 항들을 p3에 복사
    else if (not isZeroP(p2)) then p2의 나머지 항들을 p3에 복사
    return p3;
end polyAdd()
    ゲートin→p 1とp 2を同時に比較し,大指数からp 3にコピーした.
    while out→p 1またはp 2で先に終了した場合、その残りをp 3にコピーする
  • 麦汁箱:A(x)とB(x)指数が重ならない場合、
  • whileサイクルの回数=m+n-1
  • 時間複雑度:O(n+m)
    • Express+GraphQL+MongoDB無限スクロール
    React現代化テスト