一元多项式的乘法与加法运算的算法分析(java描述)

àì夳堔傛蜴生んèń 2022-09-02 14:45 159阅读 0赞

### 捷径到达所需位置 ###

*   *  准备工作（创建相关结构）
     *  将数据输入
     *  实现乘法操作
     *  乘法结果队列的调整
     *  输出结果
     *  实现加法操作（同时输出）
     *  总代码
     *  到此结束，感谢大家观看

**输入格式:**  
输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。  
**输出格式:**  
输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔。零多项式应输出`0 0`。  
**测试点**  
![借用一位朋友的图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MTI4MjM1MA_size_16_color_FFFFFF_t_70]

## 准备工作（创建相关结构） ##

**在这道题目中，我们使用“队列”的结构。**（原因见多项式乘法算法部分）

Queue<Integer> queue_a = new LinkedBlockingQueue<Integer>();
            Queue<Integer> queue_A = new LinkedBlockingQueue<Integer>();
            Queue<Integer> queue_b = new LinkedBlockingQueue<Integer>();
            Queue<Integer> queue_B = new LinkedBlockingQueue<Integer>();
            Queue<Integer> queue_c = new LinkedBlockingQueue<Integer>();    
            Queue<Integer> queue_C = new LinkedBlockingQueue<Integer>();
            int tempA,tempB,temp;
            int count = 0;

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>作用</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>(queue_)A,B</td> 
   <td>用来存放指数</td> 
  </tr> 
  <tr> 
   <td>(queue_)a,b</td> 
   <td>用来存放系数</td> 
  </tr> 
  <tr> 
   <td>(temp),A,B，</td> 
   <td>存放临时数据</td> 
  </tr> 
  <tr> 
   <td>(queue_)C,c</td> 
   <td>用来存放乘法运算中的结果</td> 
  </tr> 
  <tr> 
   <td>count</td> 
   <td>记录输出的组数</td> 
  </tr> 
 </tbody> 
</table>

## 将数据输入 ##

int n = input.nextInt();
            for(int i=0;i<n;i++)
            { 
                tempA = input.nextInt();
                queue_a.add(tempA);
                tempB = input.nextInt();
                queue_A.add(tempB);
            }
            int m = input.nextInt();
            for(int i=0;i<m;i++)
            { 
                tempA = input.nextInt();
                queue_b.add(tempA);
                tempB = input.nextInt();
                queue_B.add(tempB);
            }
            input.close();

## 实现乘法操作 ##

**注意：队列A，a，B，b在取出数据之后，一定要记得放回去，之后的加法运算还需要用到**

for(int i=0;i<m;i++)
            { 
                tempB = queue_b.remove();//先取出b队列队首的数
                for(int j=0;j<n;j++)
                { 
                    tempA = queue_a.remove();//循环乘一遍a队列的数并存到c队列中
                    queue_c.add(tempA*tempB);//在多项式乘法中系数相乘
                    queue_a.add(tempA);
                }
                queue_b.add(tempB);//记得把之前取出的b队列德数字存放回队列尾部
                tempB = queue_B.remove();//取B队列队首的数
                for(int j=0;j<n;j++)
                { 
                    tempA = queue_A.remove();//循环加一遍A队列的数并存到C队列中
                    queue_C.add(tempA+tempB);//多项式乘法中指数相加
                    queue_A.add(tempA);
                }        
                queue_B.add(tempB);//将取出的B队列的数存回B队尾
            }

**这里我们发现为什么我们要采用队列这种方法**

方便进行数据的一一对应的操作（但是要注意大小写队列中元素同时移除，我在写程序时出现了这个问题，出现了空指针异常），而且方便迭代操作(可以将数据结构中的数据遍历一遍，使用栈就没这么方便)将移除的数据重新添加不会影响到下一个数据的提取。

**但是出现了一个问题**，如果相同指数两组数据存放在（queue\_）C，c中的情况，队列不能自动识别  
在测试点第二组数据中，直接输出Cc组的结果是`1 4 -1 2 1 2 -1 0`,这与结果`1 4 -1 0`的不同就在于这个自动识别并处理的过程。下面我们来介绍

## 乘法结果队列的调整 ##

**在不经过简化算式的情况下，两个多项式乘积的项数等于这两个多项式项数之积**

int k = 0;
            int [] zhishu = new int [m*n];
            int [] xishu  = new int [m*n];
            while(!queue_C.isEmpty()&&!queue_c.isEmpty())
            { 
                xishu[k] = queue_c.remove();
                zhishu[k] = queue_C.remove();
                k++;
            }
            for(int i=0;i<m*n;i++)
            { 
                for(int j=0;j<i;j++)
                { 
                    if(zhishu[j]==zhishu[i])
                    {     
                       /*前后对应的指数相同时，前 面对应系数变成为前后对应系 的和，后面的系数改变成0就好了*/                    
                       
                        xishu[j] = xishu[i]+xishu[j];
                        xishu[i] = 0;
                    }
                }
            }
            for(int i=0;i<m*n;i++)
            { 
                queue_C.add(xishu[i]);
                queue_c.add(zhishu[i]);
            }

**不要问我为什么一开始不用数组承接数据，在将数据导入队列或直接输出，因为我一开始根本没想到指数相同的情况。之后改觉得还是直接往上添加操作方便，不想做大的修改（还是懒） (￣\_,￣)**

## 输出结果 ##

while(!queue_C.isEmpty()&&!queue_c.isEmpty())
            { 
                if(queue_C.peek()!=0) 
                { 
                    System.out.print(queue_C.remove()+" "+queue_c.remove()+" ");
                    count++;//一旦输出一组数据，记录
                }
                else
                { 
                    queue_C.remove();
                    queue_c.remove();//当系数为零，移除这组数据但是不输出
                                     //知道刚刚为什么只用把系数改为0就行了吧？
                }
            }
            if(count==0)
            { 
                System.out.println("0 0");//当一组数据都没输出时，结果肯定为零
                                         //只用输出一组（0 0）就行了.
            }
            else
            { 
                System.out.println();
            }

## 实现加法操作（同时输出） ##

实现加法操作相对简单，只要寻找指数相同的累加后输出，没有相同直接输出，这里就不需要新建一组队列用来装结果了。

count=0;//计数器归零
            while(!queue_A.isEmpty()||!queue_B.isEmpty())
            { 
                tempA=-1000000000;
                tempB=-1000000000;
                if(!queue_A.isEmpty())
                { 
                    tempA = queue_A.peek();
                }
                if(!queue_B.isEmpty()) 
                { 
                    tempB = queue_B.peek();
                }//先查看一下指数，看看是否相同
                //<注意>因为题目中的指数顺序为一直相同，所以可以这样操作
                if(tempA==tempB)
                { 
                    queue_B.remove();
                    temp = queue_a.remove()+queue_b.remove();
                    if(temp!=0) 
                    { 
                        System.out.print(temp+" "+queue_A.remove()+" ");
                        count++;
                    }
                    if(temp==0) queue_A.remove();
                    
                    //这个地方第一次没有写上导致空指针异常
                }
                else if(tempA>tempB)
                { 
                    if(queue_a.peek()!=0)
                    { 
                        System.out.print(queue_a.remove()+" "+queue_A.remove()+" ");
                        count++;
                    }
                    else 
                    { 
                        if(!queue_A.isEmpty()) queue_A.remove();
                        if(!queue_a.isEmpty()) queue_a.remove();
                    }
                }
                else if(tempA<tempB)
                { 
                    if(queue_b.peek()!=0) 
                    { 
                        System.out.print(queue_b.remove()+" "+queue_B.remove()+" ");
                        count++;
                    }
                    else
                    { 
                        if(!queue_B.isEmpty()) queue_B.remove();
                        if(!queue_b.isEmpty()) queue_b.remove();
                    }
                }
            }
            if(count==0)
            { 
                System.out.println("0 0");
            }
        }

## 总代码 ##

import java.util.Queue;
    import java.util.Scanner;
    import java.util.concurrent.LinkedBlockingQueue;
    public class TestA  
    { 
        public static void main(String[] arg)
        { 
            Scanner input = new Scanner(System.in);
            Queue<Integer> queue_a = new LinkedBlockingQueue<Integer>();
            Queue<Integer> queue_A = new LinkedBlockingQueue<Integer>();
            Queue<Integer> queue_b = new LinkedBlockingQueue<Integer>();
            Queue<Integer> queue_B = new LinkedBlockingQueue<Integer>();
            Queue<Integer> queue_c = new LinkedBlockingQueue<Integer>();    
            Queue<Integer> queue_C = new LinkedBlockingQueue<Integer>();
            int tempA,tempB,temp;
            int count = 0;
            //输入
            int n = input.nextInt();
            for(int i=0;i<n;i++)
            { 
                tempA = input.nextInt();
                queue_a.add(tempA);
                tempB = input.nextInt();
                queue_A.add(tempB);
            }
            int m = input.nextInt();
            for(int i=0;i<m;i++)
            { 
                tempA = input.nextInt();
                queue_b.add(tempA);
                tempB = input.nextInt();
                queue_B.add(tempB);
            }
            input.close();
            //实现多项式累乘
            for(int i=0;i<m;i++)
            { 
                tempB = queue_b.remove();
                for(int j=0;j<n;j++)
                { 
                    tempA = queue_a.remove();
                    queue_c.add(tempA*tempB);
                    queue_a.add(tempA);
                }
                queue_b.add(tempB);
                tempB = queue_B.remove();
                for(int j=0;j<n;j++)
                { 
                    tempA = queue_A.remove();
                    queue_C.add(tempA+tempB);
                    queue_A.add(tempA);
                }        
                queue_B.add(tempB);
            }
            //实现调整累乘
            int k = 0;
            int [] zhishu = new int [m*n];
            int [] xishu  = new int [m*n];
            while(!queue_C.isEmpty()&&!queue_c.isEmpty())
            { 
                xishu[k] = queue_c.remove();
                zhishu[k] = queue_C.remove();
                k++;
            }
            for(int i=0;i<m*n;i++)
            { 
                for(int j=0;j<i;j++)
                { 
                    if(zhishu[j]==zhishu[i])
                    { 
                        xishu[j] = xishu[i]+xishu[j];
                        xishu[i] = 0;
                    }
                }
            }
            for(int i=0;i<m*n;i++)
            { 
                queue_C.add(xishu[i]);
                queue_c.add(zhishu[i]);
            }
            //输出
            while(!queue_C.isEmpty()&&!queue_c.isEmpty())
            { 
                if(queue_C.peek()!=0) 
                { 
                    System.out.print(queue_C.remove()+" "+queue_c.remove()+" ");
                    count++;
                }
                else
                { 
                    queue_C.remove();
                    queue_c.remove();
                }
            }
            if(count==0)
            { 
                System.out.println("0 0");
            }
            else
            { 
                System.out.println();
            }
            //实现多项式累加
            count=0;
            while(!queue_A.isEmpty()||!queue_B.isEmpty())
            { 
                tempA=-1000000000;
                tempB=-1000000000;
                if(!queue_A.isEmpty())
                { 
                    tempA = queue_A.peek();
                }
                if(!queue_B.isEmpty()) 
                { 
                    tempB = queue_B.peek();
                }
                if(tempA==tempB)
                { 
                    queue_B.remove();
                    temp = queue_a.remove()+queue_b.remove();
                    if(temp!=0) 
                    { 
                        System.out.print(temp+" "+queue_A.remove()+" ");
                        count++;
                    }
                    if(temp==0) queue_A.remove();//这个地方第一次没有写上导致空指针异常
                }
                else if(tempA>tempB)
                { 
                    if(queue_a.peek()!=0)
                    { 
                        System.out.print(queue_a.remove()+" "+queue_A.remove()+" ");
                        count++;
                    }
                    else 
                    { 
                        if(!queue_A.isEmpty()) queue_A.remove();
                        if(!queue_a.isEmpty()) queue_a.remove();
                    }
                }
                else if(tempA<tempB)
                { 
                    if(queue_b.peek()!=0) 
                    { 
                        System.out.print(queue_b.remove()+" "+queue_B.remove()+" ");
                        count++;
                    }
                    else
                    { 
                        if(!queue_B.isEmpty()) queue_B.remove();
                        if(!queue_b.isEmpty()) queue_b.remove();
                    }
                }
            }
            if(count==0)
            { 
                System.out.println("0 0");
            }
        }

## 到此结束，感谢大家观看 ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MTI4MjM1MA_size_16_color_FFFFFF_t_70]: /images/20220829/256ea98fc02d417c9c1ee73e7becb309.png