多項式クラスを作ります。

なんでこういうのを作りたいかというと、 多項式の5×5の行列式を計算するとかが大変だから。
多項式ってのは複数の変数（って言っていいんだっけ？）があるものを含みます。 これの加減乗くらいはやりたいですね。 あと微分・積分もいるのかな？ 零点とか極値まで求められたらすごいけど。

こういうのって悩むんですよね。 STL の vector みたいなわかりにくいのは嫌だけど、 Polynomial なんて長たらしい名前にはしたくないし、 でも、Poly だとわけわかんないし。
うーん、悩んだところで Polynomial に決定。 実際に使う時は typedef で Poly とか P とか短くすればいいでしょう。

多項式をどのように表現しましょう。 とりあえず、map を使って、

    項 → 係数
 

という関係を定義すると都合よさそうです。すなわち、

    x + 2 * y
 

というの多項式があったとすると、

    x → 1
    y → 2
 

とします。
では、項はどのように表現しましょうね。例えば次のような項を考えます。

    x2y3z
 

これも map を使って、

    変数 → べき乗
 

という関係を定義するとよいです。 これだと、負のべき乗も表せますね。
けれど、掛け算をしてべき乗がキャンセルされて0になったら、 それはもう要らない「キー」ですよね。 掛け算したときに毎回チェックして「値」が0になった「キー」 は削除してもいいんですが、それはちょっと美しくないですね。
うーん、負のべき乗は使わないようにしましょうか。 元々そうするつもりはなかったし。

まとめると、

    map<map<string,int>,double>
 

となります。例えば、

    xy + 3 * z2
 

は、

    map<map<string,int>,double> p;
    map<string,int> term;
    
    term.insert(make_pair("x", 1));
    term.insert(make_pair("y", 1));
    p.insert(make_pair(term, 1));       //xy
    term.clear();
    
    term.insert(make_pair("z", 2));     //z2
    p.insert(make_pair(term, 3));       //xy+3z2
 

という感じになります。
定数項は空の map を使います。こんな感じ。

    map<map<string,int>,double> p;
    map term;
    
    p.insert(make_pair(term, 4));       //4
 

結局、Polynomialは、

    map<map<string,int>,double>
 

の派生クラスとなります。

足し算は、次のような手順で行います。

    1. 引数を項ごとに足していく
    2. 係数が0の項は消す
 

コードで書くとこんな感じです。

    Polynomial& Polynomial::operator +=(const Polynomial& a) {
        for(Polynomial::const_iterator p = a.begin(); p != a.end(); ++p) {
            if((this->operator[](p->first) += p->second) == 0)  //係数の足し算
                this->erase(p->first);                          //0なら項を消す
        }
        return *this;
    }
 

すでにある項は係数同士を足し合わせ、 なかった項は係数が0に初期化されそこに係数が足されます。 引き算も同様です。

かけ算は、次のような手順で行います。

    1. 第一引数と第二引数のすべての組み合わせで項のかけ算をする
    2. 係数をかける
    3. 用意したPolynomialオブジェクトの項に係数を足す
    4. すべて終わったら係数をチェックして0ならその項は消す
 

1. の項のかけ算は足し算のときと同様です。
コードで書くとこんな感じです。

    Polynomial operator *(const Polynomial& a, const Polynomial& b) {
        Polynomial  c;
        Polynomial::const_iterator  p, q;
        map<string,int>    r;
        map<string,int>    term;  //項
        for(p = a.begin(); p != a.end(); ++p) {
            for(q = b.begin(); q != b.end(); ++q) {
                term = p->first;        //aの項
                for(r = q->first.begin(); r != q->first.end(); ++r)
                    term[r->first] += r->second;    //同じ変数同士でべき乗の足し算
                c[term] += p->second * q->second;
            }
        }
        for(p = c.begin(); p != c.end(); ++p) {
            if(p->second == 0)
                c.erase(p->first);
        }
        return c;
    }
 

書いてみると以外に簡単ですね。 あと、かけてべき乗が0になったら消すってのも別に美しくないってほどじゃない。 ま、多項式だからこれでいいってことにしましょう。