一元多项式乘法算法

一元多项式乘法算法

 

       一般的，一元多项式相乘有两种算法：

令A（i）（0<=i<n）、B（j）(0<=j<m)表示多项式A、B所对应的第i、j项元素，C（i，j）表示A(i)*B(j)的结果。则有：

 

算法一：结果用链表存储

此算法用A（i）去乘B（j）(0<=j<m)，逐项把每个结果插入结果链表ResultNode中。此算法下，每次相乘所得结果即C（i，j）要正确的插入ResultNode中，则要遍历链表以便合并同类项或生成新节点（若ResultNode有序，遍历量会相对减少）。

       算法二：结果用大型数组存储

此算法会预先开辟一个很大的空间，如float result【10000】，数组长度会根据实际情况进行调整。操作时同样用多项式A中的每一项去乘多项式B中的每一项，每次相乘得到的结果C（i，j）都将加入下标与C（i，j）指数相同的数组元素。

 

算法一和算法二充分体现了时间与空间的矛盾：前者空间开销较小而时间开销较大，后者则恰恰相反。当然也有基于以上两种算法的变种算法，但其实质相同，并无较大改进。

 

下面，我们尝试一种空间与时间均较优的算法。

算法二造成空间浪费的主要原因在于无法预知最终多项式的项数，倘若可以预知结果多项式的项数，我们可以开辟较优的空间：若结果多项式的项数为num，我们可开辟空间

index1【num】和index2【num】，在index1中按序存放相乘中先出现的多项式指数，而与index2中相同下标数组元素则存放该指数相对应的系数，每计算出一个新结果时只需遍历数组index1即可，该法较上两法优，而在实现上，要确定最终多项式的项数，则必须先进行一次两个多项式相乘，随后再重复一次多项式相乘操作。显然，两次多项式相乘操作会使效率大打折扣。那可以仅进行一次多项式相乘便可以得到结果吗？可以！完全可以！

 

       注意到多项式相乘时，关键因素是多项式指数确定问题，故为了简便明了，这里我们暂不考虑系数因素。而多项式相乘时，对结果指数而言，等效于将A，B多项式的任意两个指数相加，故我们可建立等效该数学模型：已知两集合Ah，Bh,定义集合Ah+Bh=Ch，这里

“+”操作是Ah，Bh两多项式的任意两元素相加所得到的集合。

为了更好的理解该算法原理，令Ah={1，2，5}，Bh={1，2，5}，求Ch；

                                      编号： 0      1       2

                                                                      Bh： 1          2            5

                                        Ah： 1          2            5

如右图所示：

1）  因为Ah（0）+Bh(0) = 1 + 1 = 2 < Ah(1)＋Ｂh(0)=2 + 1 = 3故2是尚未计算和结果中最小的一个。

2）  因为Ah（0）+Bh(1) = 1 + 2 = 3 ==Ah(1)＋Ｂh(0)=2 + 1 = 3，Ah（2）+Bh(0) = 5+1= 6

所以3是尚未计算和结果中最小的一个。

3）  Ah（0）+Bh(3) = 1 + 5 = 6 < Ah(1)＋Ｂh(2)=2 + 5 = 7, Ah（2）+Bh(0) = 5+1= 6

所以6是尚未计算和结果中最小的一个。

4)  Ah(1)＋Ｂh(2)=2 + 5 = 7 ==  Ah（2）+Bh(1) = 5+2= 7

所以7是尚未计算和结果中最小的一个。

5） Ah（2）+Bh(2) = 5+5= 10

所以10是尚未计算和结果中最小的一个。

 

以上实例，并未模拟完全遍历Ah，Bh集合，但成功的求出了Ch。基于引例，我们可以得到其计算原则：

1）集合A，B均为升序，这是该算法的前提。

2）设立变量i=0，数组data【AhLength】用存放Ah中每个元素所对应的Bh中尚未进行计    算且计算结果不为最小和的元素的下标。

3）计算data1=Ah【i】+Bh【data【i】】，寻找满足Ah【j】+Bh【data【j】】<= data1且j>i的j是否存在，若不存在，则data1尚未计算和结果中最小的一个。否则，把j看做变量i，继续该操作，直到找到最大的j使其和最小。

4）若当前i多对应的data【i】<BhLength-1,则data【i】++，否则i++。

   若data[AhLength-1] =BhLength,则所有加法和已找到，否则继续操作2。

 

其算法描述如下：

Int main（）{

   int anum,bnum;                               //定义Ah,Bh多项式项数
   int i =0,j =0,k=0,tp = 0;
   int data1 = 0,data2=0,temp = 0;                    //存放所得指数和的变量
   
  input（anum）;                                //输入Ah多项式项数

input(a【anum】);                             //输入Ah多项式

init（data【anum】）;                          //初始化data【】数组

input（bnum）;                               //输入Bh多项式项数

input（b【bnum】）;                            //输入Bh多项式

 

//Ah,Bh按升序排列，如果有必要

sort（a）;

sort（b）;

//依次得到最小的指数和
   while(data[anum-1]<bnum){
      data1 =  a[i]+b[data[i]];
      j = data[i] -1 ;
      k = i + 1;
      temp = data1;
      while(j>=0&&k<anum){
           data2=a[k] + b[data[k]];
           if(data2>temp){
                 if((k+1)==anum||data2<a[k+1]+b[data[k+1]])
                       break;
                 else{
                       data2 = a[k+1]+b[data[k+1]];
                       k ++;
                       j--;
                 }      
         }
       if(data2==temp){
            data[k]++;
            k++;
       }
      else{
            temp = data2;
            tp = k;
            k++;
            j--;
      }

}//内层while
   if(temp>=data1)
        data[i]++;
    else{
        data1 = temp;
        data[tp]++;
     }

 if(data[i]>bnum-1)
       i++;

//处理结果最小指数和data1，可以保存亦可直接输出，这里省略。

}

}

 

指数问题一旦解决了，那么计算系数时，只要加上计算对应系数乘积和便可。

附：附件中有其简单的基本实现程序。