多项式乘积算法设计与分析

算法设计与分析课程设计论文课题名称：多项式乘积的分治算法设计与实现院系：计算机科学与信息工程学院专业：计算机科学与技术（信息方向）11-1姓名学号：潘强201103020005指导教师：冯慧玲2013年12月2目录一、算法介绍····································································3二、问题描述····································································3三、相关概念和数据结构介绍···············································4四、算法设计与流程图························································41.算法设计····································································42.流程控制图·································································5五、算法分析····································································7六、应用举例与程序代码·····················································71.应用举例····································································72.核心代码····································································7七、运行截图··································································10八、总结·········································································113多项式乘积算法设计与分析一、算法介绍在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)等。分治法在每一层递归上都有三个步骤：分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；合并：将各个子问题的解合并为原问题的解。它的一般的算法设计模式如下：Divide-and-Conquer(P)1.if|P|≤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)其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(P)求解。算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1,P2,...,Pk的相应的解y1,y2,...,yk合并为P的解。二、问题描述用分治算法解决多项式乘积问题由于任意大整数都可以看作是一多项式，所以大整数相乘是多项式乘积的一个特例，通过解决大整数乘积，即是解决了多项式的乘积问题。4三、相关概念和数据结构介绍1.因为两个数可以任意大，所以通过数组实现，这个大整数乘积的实现运用整型数组来实现，这样就把两个数据转化为两个数组的操作。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+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*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实际是-99。但在本实验中类似这种情况是不可能5出现的，原因是：在求大整数乘积时传入的各项系数均为非负，于是总有高位满足被借1当10后高位仍为非负的。2.流程控制图设计流程控制图如下所示：6开始voidproduct1（）函数递归计算多项式的系数用voidplus（）函数和voidmins函数进行多项式系数的相加和相减voidproduct（）函数求两个多项式相乘的系数并按从小到大存放得到的系数i=0;i2*n;i++;r[i]=r1[i]=r2[i]=r3[i]=0输出相乘后多项式的各个系数，以及这个多项式的数学表示方式结束以系数方式，输入两个多项式7五、算法分析很显然算法的时间复杂度由求各系数时调用voidpro(intp[],intq[],intr[],intn)所决定类似多项式的算法时间复杂度分析f(2)=7n=2f(n)=3f(n/2)+5nn2通过换名是可以求出f(n)=O(nlog3)的这个算法通过对大整数的乘积的解决来体现多项式乘积的实现与运用其中函数voidproduct1(floatp[],floatq[],floatc[])完成多项式的系数的计算，函数voidplus(floatp[],floatq[],floatc[],intk)完成数组p[]与数组q[]对应相加并把结果对应放到数组c[]上，函数voidmins(floatp[],floatq[],intk)数组p[]与数组q[]对应相减并把结果对应放到数组p[]上，函数voidproduct(floatp[],floatq[],floatr[],intn)求多项式p[]与多项式q[]的乘积的各项系数，并按指数由小到大储放对应系数在数组r[]。通过以上几个函数即可求解出两个多项式相乘后的各个系数，进而得到最终的大整数。六、应用举例与程序代码1.应用举例实例问题：大整数乘积以行输入方式输入两个大整数（不限正、负），用分治法计算两个大整数的乘积，并输出计算结果。2.核心代码#includestdio.h#includestdlib.h#includemath.h#defineMAXSIZE51voidproduct1(floatp[],floatq[],floatc[])//递归的基础步，即计算多项式的系数{c[0]=p[0]*q[0];c[2]=p[1]*q[1];c[1]=(p[0]+p[1])*(q[1]+q[0])-c[0]-c[2];}8voidplus(floatp[],floatq[],floatc[],intk)/*数组p[]与数组q[]对应相加并把结果对应放到数组c[]上*/{inti;for(i=0;ik;i++)c[i]=p[i]+q[i];}voidmins(floatp[],floatq[],intk)/*数组p[]与数组q[]对应相减并把结果对应放到数组p[]上*/{inti;for(i=0;ik;i++)p[i]=p[i]-q[i];}voidproduct(floatp[],floatq[],floatr[],intn)/*求多项式p[]与多项式q[]的乘积的各项系数，并按指数由小到大储放对应系数在数组r[]*/{float*r1,*r2,*r3;r1=(float*)malloc(sizeof(float)*(2*n-1));//申请缓冲区r2=(float*)malloc(sizeof(float)*(2*n-1));r3=(float*)malloc(sizeof(float)*(2*n-1));inti;intk;for(i=0;i2*n-1;i++)r[i]=r1[i]=r2[i]=r3[i]=0;if(n==2)//剩余两项时直接计算product1(p,q,r);else{k=n/2;product(p,q,r,k);product(p+k,q+k,r1+2*k,k);//递归计算r1;plus(p,p+k,r2,k);//求P0+P1,结果放在r2plus(q,q+k,r3,k);//求q0+q1,结果放在r3product(r2,r3,r2+k,k);//递归计算r2;mins(r2+k,r,2*k-1);//求r2-r0-r1,结果放到r+kmins(r2+k,r1+2*k,2*k-1);plus(r+k,r2+k,r+k,2*k-1);//合并各项系数，结果放到r上plus(r+2*k,r1+2*k,r+2*k,2*k-1);}free(r1);//销毁缓冲区free(r2);free(r3);}intadjust(floatp[],floatq[])9{inti,j,k,l,m;printf(输入多项式的两个多项式的系数，按从低次项向高次项的系数输入！\n以小写字母a结束输入如：\n);printf(4+2x+3x^2-6x^3则输入423-6a,注意输入顺序\n);printf(请输入第一个多项式A的系数，注意输入规则\n);for(i=0;;i++){scanf(%f,&p[i]);m=getchar();if(m=='a')break;}printf(请输入第二个多项式B的系数，注意输入规则\n);for(j=0;;j++){scanf(%f,&q[j]);m=getchar();if(m=='a')break;}if(i=j){for(l=0;;l++){k=(int)pow(2,l);m=(int)pow(2,l+1);if(ik&&i=m)break;}}else{for(l=0;;l++){k=(int)pow(2,l);m=(int)pow(2,l+1);if(jk&&j=m)break;}}if(i!=m||j!=m){if(im)10for(;im;i++)p[i]=0;if(jm)for(;jm;j++)q[j]=0;}returnm;}intmain(){floatp[MAXSIZE];floatq[MAXSIZE];float*r;intk,