POJ——多項式の加算

7662 ワード

         :http://www.rxwcv.cn
1:多項式加算
表示コミット統計質問合計時間制限: 
1000ms 
メモリの制限: 
5000kB
説明
    2つの多項式を加算する場合によく遭遇しますが、ここでは、2つの多項式を加算することをプログラムでシミュレートする必要があります.まず、係数、べき乗数のような複数の整数対で表される2つの多項式があります.各多項式は独立した1行です.
例えば多項式2 x 20-x 17+5 x 9-7 x 7+16 x 5+10 x 4 + 22x2- 15
対応する式は、2 20−1 17 5 9−7 16 5 10 4 22−15である.  
各行の多項式の終わりをマークするために、式の後に負数のべき乗数の整数対を加えた.
同時に入力される式のべき乗数のサイズ順はランダムです.
私たちがしなければならないのは、与えられた2つの多項式を加えることです.
 
 
 
入力
入力には複数行が含まれます.
第1行の整数nは、多項式の合計が必要なグループがどれだけあるかを示す.(1 < n < 100)
次は2 n行の整数で、各行は多項式の式です.nグループを加算する多項式を表す.
1行あたりの長さは300未満です.
出力
出力にはn行が含まれ,動作ごとに1組の多項式が加算された結果が含まれる.
各行の出力結果において、多項式の各項は「[x y]」形式の文字列で表され、xはその項の係数であり、yはその項のべき乗数である.各項目のべき乗が高いものから低いもの、すなわち、べき乗数の高いものを先に出力し、べき乗数の低いものを出力することが要求される.
係数がゼロの項目は出力しないでください.
サンプル入力
2
-1 17 2 20 5 9 -7 7 10 4 22 2 -15 0 16 5 0 -1
2 19 7 7 3 17 4 4 15 10 -10 5 13 2 -7 0 8 -8
-1 17 2 23 22 2 6 8 -4 7 -18 0 1 5 21 4 0 -1
12 7 -7 5 3 17 23 4 15 10 -10 5 13 5 2 19 9 -7
サンプル出力
[ 2 20 ] [ 2 19 ] [ 2 17 ] [ 15 10 ] [ 5 9 ] [ 6 5 ] [ 14 4 ] [ 35 2 ] [ -22 0 ]
[ 2 23 ] [ 2 19 ] [ 2 17 ] [ 15 10 ] [ 6 8 ] [ 8 7 ] [ -3 5 ] [ 44 4 ] [ 22 2 ] [ -18 0 ]
ヒント
第1のサンプルデータの第2の行の末尾の8-8は、べき乗-8が負の数であるため、この行のデータは終了し、8-8は計算に関与しない.
# include
# include

using namespace std;

typedef struct LNode{
  int num;
  int pow;
  struct LNode * next;
}LNode, * LinkList;

bool cmp(LNode a, LNode b)
{
    return a.pow>b.pow;
}

void ListInsert(LNode * pHead, int a, int b)
{
    LNode * p=new LNode;
    p->num=a;
    p->pow=b;
    p->next=pHead->next;
    pHead->next=p;
}
LNode * find(LNode * pHead, int b)
{
    LNode *p=pHead->next;
    while(p&&p->pow!=b)
    {
        p=p->next;
    }
    return p;
}

void sort(LNode * pHead)
{
    LNode * p, *q;
    int ta, tb;
    for(p=pHead->next; p!=NULL; p=p->next)
      for(q=pHead->next; q->next!=NULL; q=q->next)
      {
            if(q->pownext->pow)
            {
                ta=q->num;
                tb=q->pow;
                q->num=q->next->num;
                q->pow=q->next->pow;
                q->next->num=ta;
                q->next->pow=tb;
            }

      }

}


int main(void)
{
    LNode * pHead = NULL, *p, *q;
    int n, t, a, b, i;
    cin>>n;
    for(i=0; i)
    {
        pHead = new LNode;
        pHead->next=NULL;
        t=1;
        while(t<=2)
        {
            while(cin>>a>>b)
            {
                if(b<0)
                break;
                if((p=find(pHead, b))!=NULL)
                {
                    p->num+=a;
                }
                else
                ListInsert(pHead, a, b);

            }
            t++;
        }
        sort(pHead);
        p=pHead->next;
        while(p!=NULL)
        {
            if(p->num==0)
            {
                p=p->next;
                continue;
            }
            cout<<"[ "<num<<" "<pow<<" ]"<<" ";
            p=p->next;
        }
        cout<<endl;
        p=pHead->next;
        while(!p)
        {
            q=p;
            p=p->next;
            delete q;
        }
    }
    return 0;
}
 
         :http://www.rxwcv.cn
転載先:https://www.cnblogs.com/Hewie/p/3439841.html