一元多项式乘法算法
一般的,一元多项式相乘有两种算法:
令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)+Bh(0)=2 + 1 = 3故2是尚未计算和结果中最小的一个。
2) 因为Ah(0)+Bh(1) = 1 + 2 = 3 ==Ah(1)+Bh(0)=2 + 1 = 3,Ah(2)+Bh(0) = 5+1= 6
所以3是尚未计算和结果中最小的一个。
3) Ah(0)+Bh(3) = 1 + 5 = 6 < Ah(1)+Bh(2)=2 + 5 = 7, Ah(2)+Bh(0) = 5+1= 6
所以6是尚未计算和结果中最小的一个。
4) Ah(1)+Bh(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,可以保存亦可直接输出,这里省略。
}
}
指数问题一旦解决了,那么计算系数时,只要加上计算对应系数乘积和便可。
附:附件中有其简单的基本实现程序。
分享到:
相关推荐
(2)设计算法实现一元多项式乘法; (3)分析算法的时间复杂度和空间复杂度 一、总体设计 1 二、详细设计 1 2.1存储结构 1 2.2建立链表 1 2.3遍历操作 1 2.4多项式相乘算法 2 三、调试与测试 2 3.1方案一 2 3.2...
在计算机科学和数学中,一元多项式乘法是一个基础且重要的操作,特别是在数值计算、符号计算以及算法设计中有着广泛的应用。本文将详细探讨如何实现两个一元多项式的乘法,重点在于采用二维数组来存储多项式的系数和...
一元多项式乘法可以使用传统的乘法算法,如竖式乘法,也可以采用更高效的算法,如Karatsuba或FFT(快速傅里叶变换)。这些算法在复杂度上有所不同,比如Karatsuba算法的时间复杂度为O(n^1.585),而FFT为O(n log n)。...
标题中的“一元多项式乘法”是指在数学中,两个一元多项式相乘得到新的多项式的过程。这个过程通常涉及到将一个多项式的每个项与另一个多项式的每个项相乘,然后将结果合并,去除相同的项并进行加法运算。在计算机...
本话题将探讨如何使用单链表来实现一元多项式的乘法操作,这是一种常见且实用的算法,尤其在数学和计算领域。我们将在C++语言环境下进行讨论。 一元多项式通常表示为 \( a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x +...
在计算机科学中,一元多项式算法是一种处理数学上的一元多项式问题的算法,它通常涉及加法、减法、乘法以及求幂等运算。C语言是一种强大的编程语言,特别适合用来实现这种底层的算法,因为它允许直接操作内存和数据...
**一元多项式乘法**: 多项式乘法相对复杂,常见的方法有基于长乘法(直接展开乘积)和Karatsuba算法。长乘法的时间复杂度为O(n^2),而Karatsuba算法的复杂度为O(n^1.585),在大规模乘法时更有效率。Karatsuba算法的...
总结,这个项目通过链表数据结构实现了对一元多项式进行加法和乘法运算的功能,提供了灵活的数据操作和算法应用。通过学习和实践,学生可以深入理解链表的操作和多项式运算的逻辑,提升编程技能。
标题中的“一元多项式的加、减、乘法实现”是指在编程中处理一元多项式(即只含一个变量的多项式)的基本运算。在数学中,一元多项式通常表示为`ax^n + bx^(n-1) + ... + cz^0`的形式,其中a、b、c是常数,n是正整数...
【一元多项式的相关算法】涉及的是在计算机科学中如何用数据结构和算法来表示和操作一元多项式。在本问题中,一元多项式被抽象为一个链表结构,其中每个节点存储了多项式的系数和指数。下面将详细讨论相关知识点: ...
已经运行出来了,可执行,非常好用
* 一元多项式的相乘的算法实现 * 程序设计思路和实现 这个实现中,我们使用了链表来存储多项式,每个结点包含系数、指数和指针三个部分。我们使用结构体来定义结点的结构体,并使用函数Creat(int k,char c)来输入并...
一元多项式是由常数、变量以及它们的系数组成的数学表达式,如 \( ax^n + bx^{n-1} + ... + cz^0 \),其中 \( a, b, c, ..., n \) 是系数,\( x \) 是变量。 一元多项式的抽象数据结构(ADT)设计通常包括以下关键...
本文档是关于一元多项式加法、减法和乘法实现的课程设计报告,主要关注在顺序结构和动态链表结构下的实现方法。设计目标是加深对数据结构的理解,尤其是如何选择合适的数据结构来解决问题,并能编写相关算法。设计...
4. **一元多项式乘法**: 乘法稍微复杂,可以使用笛卡尔积(Cartesian product)或者Karatsuba算法等高效方法。在笛卡尔积中,将一个多项式的每一项与另一个多项式的每一项相乘,然后将结果相加。Karatsuba算法是一...
// 多项式乘法 polynomial* mulitPloyn(polynomial* p1, polynomial* p2) { // 实现逻辑... } // 输出多项式 void printPloyn(polynomial* p) { for (int i = 0; i <= p->last; i++) { printf("%f*x^%d ", p->...
// 一元多项式乘法 Polynomial multiply(const Polynomial& other) { // 实现代码... } }; ``` 对于一元多项式的加法,我们可以通过遍历两个多项式的链表并合并它们的项来实现。如果两项的指数相同,那么我们...
在本压缩包中,我们关注的是C语言...总之,这个压缩包提供的内容涉及C语言编程、线性数据结构(链表)、一元多项式运算(加法和乘法)以及算法设计。掌握这些知识对于学习计算机科学,尤其是编程和算法设计至关重要。