多项式乘法的实现.doc

《多项式乘法的实现.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、目录一、设计目的1二、设计内容11)问题描述12)基本要求11.需求分析12.问题求解13、总体设计34.详细设计45.调试与测试46.关键源程序清单4三、系统测试5四、总结6五、附件（系统测试的图表）8多项式乘法的实现一、设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。二、设计内容一元多项式乘法1)问题描述已知A(x)=a0+a1x+a2x2+……+amxm和B(x)=b0+b1x+b2x2+……+bnxn，并且在A(x)和B(x)中指数相差很多，求A(x)=A(x)*B(x)。2)基本要求(1)设计存

2、储结构表示一元多项式；(2)设计算法实现一元多项式乘法；(3)分析算法的时间复杂度和空间复杂度。1.需求分析程序是要完成两个一元多项式乘法的功能。要求输入两个多项式中每个数据项的系数和指数，从而得到一个新的多项式，这个多项式是输入的两个多项式的乘积。多项式的乘法规则：多次运用单项式与多项式相乘的法则得到的．计算时(a+b)(m+n)，先把(m+n)看成一个单项式，(a+b)是一个多项式，运用单项式与多项式相乘的法则，得到(a+b)(m+n)=a(m+n)+b(m+n),然后再次运用单项式与多项式相乘的法则。2.问题求解一元多项式的

3、乘法是在初中学到的数学知识，我们当时是这样做的：用第一个数据项的每一项去乘另一个多项式，得到的结果加起来，然后合并同类项，按照升序，或者降序的方法给得到的多项式进行排序，这样就得到了结果。用数据结构来解决这个问题的话，首先要设计多项式的存储结构，然后设计算法，这个时候要注意的就是算法的时间复杂度和空间复杂度。在本次实验里，我用的是一维数组来表示一个一元多项式。其中数组中每个数据的下标表示多项式中数据项的指数，数据的值来表示此数据项的系数。通过分析多项式的特征，不难看出多项式是由单项式构成的，而每个单项式都具有系数和指数，当系数为0

4、时，该项就失去了意义，在计算机内要表示一个多项式，至少以下数据信息：系数信息、指数信息。第一个问题就是要定义几个数组，因为是要对两个多项式计算乘积，所以，我定义了三个数组，两个数组表示要计算的两个多项式，第三个数组用来表示求得的数组。第二个问题就是怎么定义数组的长度。为了便于验证试验，我给要输入的两个数组的长度分别定义为M、N，既它们的数据项中指数最两个指数为M-1、N-1的数据项相乘，其结果数据项的指数为M+N-2，所以目标多项式中出现的最大指数就是M+N-2，因此定义目标数组的长度为M+N-1（0~M+N-1）。第三个问题为了

5、美观，系数为0的数据项就不要显示出来了。在输出结果时，用到一个条件结构。只输出系数不为0的数据项。3、总体设计开始输入a[M],b[N]定义c[M+N-1],且都初始化为0C[m+n]=a[m]+b[n]输出c[M+N-1]结束4、详细设计用数组a表示第一个多项式，其中a[i]表示多项式A中的指数为m的系数，数组b表示第二个多项式，其中b[i]表示多项式B中的指数为n的系数。A中指数为m的项与B中指数为n的项相乘，结果是得到指数为m+n的项，而且这个项的系数为a[m]*b[n].把这个系数保存在数组c的c[m+n]中。5.调试与测

6、试方案一：初始化两个一元多项式的时候输入几个系数为0的数据项，检验程序是否正常运行。方案二：初始化数组的时候，输入负数，检验程序是否出现错误。6.关键源程序清单源程序：#include#defineM2#defineN2voidmain(){inta[M],b[N],c[M+N-1];//a[i]表示多项式A中指数为i的系数。printf("请输入多项式A中依次的系数");/*创建第一个多项式*/for(inti=0;i

7、);/*打印第一个多项式*/for(i=0;i

8、1;i++)c[i]=0;/*计算两个多项式的乘积*/for(intm=0;m