一元多项式乘法算法
一元多项式乘法算法一般的，一元多项式相乘有两种算法：
令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 =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<bnum){
data1 = a+b];
j = data -1 ;
k = i + 1;
temp = data1;
while(j>=0&&k<anum){
data2=a + b];
if(data2>temp){
if((k+1)==anum||data2<a+b])
break;
else{
data2 = a+b];
k ++;
j--;
}
}
if(data2==temp){
data++;
k++;
}
else{
temp = data2;
tp = k;
k++;
j--;
}
}//内层while
if(temp>=data1)
data++;
else{
data1 = temp;
data++;
}
if(data>bnum-1)
i++;
//处理结果最小指数和data1，可以保存亦可直接输出，这里省略。
}
}
指数问题一旦解决了，那么计算系数时，只要加上计算对应系数乘积和便可。
附：附件中有其简单的基本实现程序。
页:
[1]