资源描述：
《多项式乘积算法设计与分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、算法设计与分析课程设计论文课题名称：多项式乘积的分治算法设计与实现院系：计算机科学与信息工程学院专业：计算机科学与技术（信息方向）11-1姓名学号：潘强201103020005指导教师：冯慧玲2013年12月11目录一、算法介绍3二、问题描述3三、相关概念和数据结构介绍4四、算法设计与流程图41.算法设计42.流程控制图5五、算法分析7六、应用举例与程序代码71.应用举例72.核心代码7七、运行截图10八、总结1111多项式乘积算法设计与分析一、算法介绍在计算机科学中，分治法是一种很重要的算法。字
2、面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)等。分治法在每一层递归上都有三个步骤：分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；合并：将各个子问题的解合并为原问题的解。它的一般的算法设
3、计模式如下：Divide-and-Conquer(P)1.if
4、P
5、≤n02.thenreturn(ADHOC(P))3.将P分解为较小的子问题P1,P2,...,Pk4.fori←1tok5.doyi←Divide-and-Conquer(Pi)△递归解决Pi6.T←MERGE(y1,y2,...,yk)△合并子问题7.return(T)其中
6、P
7、表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接
8、解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(P)求解。算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1,P2,...,Pk的相应的解y1,y2,...,yk合并为P的解。二、问题描述用分治算法解决多项式乘积问题由于任意大整数都可以看作是一多项式，所以大整数相乘是多项式乘积的一个特例，通过解决大整数乘积，即是解决了多项式的乘积问题。11三、相关概念和数据结构介绍1.因为两个数可以任意大，所以通过数组实现，这个大整数乘积的实现运用整型数组
9、来实现，这样就把两个数据转化为两个数组的操作。2.重载运算符“+”来实现两个数的相加，也就是连接，返回值是数组对象，实现合并，便于操作3.最重要的是函数product1，plus,mins,通过他们来实现多项式的相乘，应用递归调用，返回对象为数组对象，同样便于操作。四、算法设计与流程图1.算法设计因为多项式的表示是Pn(x)=anxn＋an-1xn-1＋…＋a1x＋a0任意大整数都可以看作是一多项式（其中X=10，an是第n+1位上的数字，个位用a0表示）。如：9876=6+7*101+8*102
10、+9*103所以大整数相乘可以用多项式乘积的分治算法实现，实际上大整数相乘就是多项式乘积的一个特例。把一个多项式分为两个P(x)=P0(x)+P1(x)xn/2q(x)=q0(x)+q1(x)xn/2P(x)*q(x)=P0(x)*q0(x)+P1(x)*P1(x)*xn+((P0(x)+P1(x))*(q0(x)+q1(x))-P0*q0–P1*q1)*xn/2令：R0=P0(x)*q0(x)R1=P1(x)*q1(x)R2=P0(x)+P1(x))*(q0(x)+q1(x))-P0*q0–P1
11、*q1于是上式可化简为P(x)*q(x)=R0+（R2-R0-R1）*xn/2+R1*xn上述过程可通过递归函数voidpro(intp[],intq[],intr[],intn)人来实现求各项系数。求出各系数后还要通过voidfe(intA[],intn)来处理各项系数，从而求出各乘积上各位的数字。需要指出的是在调用voidfe(intA[],intn)时，假设数组A[]上的元素依次为1-201时，最后输出的结果将是:-101实际是-9911。但在本实验中类似这种情况是不可能出现的，原因是：在求
12、大整数乘积时传入的各项系数均为非负，于是总有高位满足被借1当10后高位仍为非负的。2.流程控制图设计流程控制图如下所示：11开始voidproduct1（）函数递归计算多项式的系数用voidplus（）函数和voidmins函数进行多项式系数的相加和相减voidproduct（）函数求两个多项式相乘的系数并按从小到大存放得到的系数i=0;i<2*n;i++;r[i]=r1[i]=r2[i]=r3[i]=0输出相乘后多项式的各个系数，以及这个多项式的数学表示方式结束以系数方式，输入两
