pat 1009（需回顾）

Product of Polynomials (25)

This time, you are supposed to find A*B where A and B are two polynomials.

Input Specification:

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K N1 a_N1 N2 a_N2 ... NK a_NK, where K is the number of nonzero terms in the polynomial, Ni and a_Ni (i=1, 2, ..., K) are the exponents and coefficients, respectively. It is given that 1 <= K <= 10, 0 <= NK < ... < N2 < N1 <=1000.

Output Specification:

For each test case you should output the product of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate up to 1 decimal place.

Sample Input

2 1 2.4 0 3.2
2 2 1.5 1 0.5

Sample Output

3 3 3.6 2 6.0 1 1.6

这道题难倒不难，就是细节需要注意的多点，主要有两方面： 一，每一项插入以计算出的积时，有三个地方需要考虑，头 尾 中间;二 结果为零的需要删除节点

View Code

  1 #include<stdio.h>
  2 struct node
  3 {
  4     int exponents;
  5     float coefficients;
  6 };
  7 struct Polynomials{
  8     int number;
  9     node items[15];
 10     Polynomials(){
 11         number = 0;
 12     }
 13 };
 14 struct product {
 15     int number;
 16     node items[105];
 17     product(){
 18         number = 0;
 19     }
 20 };
 21 void insertItem(product &a, const node &b)
 22 {
 23     int i,j;
 24     // a 为空
 25     if (a.number == 0)
 26     {
 27         a.items[0] = b ;
 28         a.number ++;
 29         return ;
 30     }
 31     // 插在末尾后面
 32     if (a.items[a.number-1].exponents> b.exponents)
 33     {
 34         a.items[a.number] = b;
 35         a.number++;
 36         return ;
 37     }
 38 
 39     //寻找插的位置
 40     for (i = a.number-1; i >= 0; i--)
 41     {
 42         if (a.items[i].exponents<b.exponents)
 43              continue;
 44         else
 45             break;    
 46     }
 47 
 48     //插在最前面
 49     if(i == -1){
 50         j = a.number-1;
 51 
 52         while(j>=0){
 53             a.items[j+1] =a.items[j];
 54             j--;
 55         }
 56         a.items[0] = b;
 57         a.number++;
 58         return ;
 59     }
 60 
 61     //插在中间
 62     if(a.items[i].exponents == b.exponents){
 63         
 64         a.items[i].coefficients+= b.coefficients ;
 65         //两项和为零
 66         if (a.items[i].coefficients == 0)
 67         {
 68             j = i;
 69             while (j < a.number -1)
 70             {
 71                 a.items[j] = a.items[j+1];
 72             }
 73             a.number --;
 74             return ;
 75         }
 76     }else{
 77         
 78         j = a.number-1;
 79 
 80         while (j>i)
 81         {
 82             a.items[j+1] =a.items[j];
 83             j--;
 84         }
 85 
 86         a.items[i+1] = b;
 87         a.number++;
 88         return ;
 89 
 90     }
 91 
 92 }
 93 void insert(product &a,const Polynomials & b){
 94     
 95     int i;
 96     // 初始化
 97     if(a.number == 0){
 98         a.number = b.number;
 99         for(i = 0; i < b.number; i++)
100             a.items[i] = b.items[i];
101         return ;
102     }
103     for (i = 0; i <b.number ; i++)
104           insertItem(a, b.items[i]);
105 
106 }
107 Polynomials p1,p2,p3;
108 product  result;
109 int main()
110 {
111     int i,j,k;
112     int exponents;
113     float coefficients;
114     while (scanf("%d", &k) !=EOF){
115     
116     result.number = 0;
117     p1.number = k;
118     for (i =0; i<k;i++)
119     {
120         scanf("%d %f",&p1.items[i].exponents, &p1.items[i].coefficients);    
121     }
122 
123 
124     scanf("%d", &k);
125     p2.number = k;
126     for (i =0; i<k;i++)
127     {
128         scanf("%d %f",&p2.items[i].exponents, &p2.items[i].coefficients);    
129     }
130 
131     p3.number =p1.number;
132     for(i =0;i <p2.number ;i++){
133 
134         for (j =0; j<p1.number ;j++)
135         {
136             p3.items[j].exponents = p1.items[j].exponents + p2.items[i].exponents;
137             p3.items[j].coefficients = p1.items[j].coefficients * p2.items[i].coefficients ;
138         }
139         insert(result, p3);
140         
141     }
142 
143     printf("%d", result.number) ;
144     for (i = 0; i< result.number ;i++)
145     {
146         printf(" %d %.1f", result.items[i].exponents, result.items[i].coefficients);
147     }
148     
149     }
150     return 0;
151 }

--------------------------------------------------------------------天道酬勤！