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

1、算法设计与分析课程设计论文课题名称：多项式乘积的分治算法设计与实现院系：计算机科学与信息工程学院专业：计算机科学与技术（信息方向）11-1姓名学号：潘强 201103020005指导教师：冯慧玲2013年12月目录一、算法介绍3二、问题描述3三、相关概念和数据结构介绍4四、算法设计与流程图41.算法设计42.流程控制图5五、算法分析7六、应用举例与程序代码71.应用举例72.核心代码7七、运行截图10八、总结11多项式乘积算法设计与分析一、算法介绍在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子

2、问题直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)等。分治法在每一层递归上都有三个步骤：分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；合并：将各个子问题的解合并为原问题的解。它的一般的算法设计模式如下：Divide-and-Conquer(P)1. if |P|n02. then return(ADHOC(P)3. 将P分解为较小的子问题 P1 ,P2 ,.,Pk4. for i1 to k5

3、. do yi 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-1a1xa0任意大整数都可以看作是一多项式

5、（其中X=10，an是第n+1位上的数字，个位用a0表示）。如：9876=6+7*101+8*102+9*103所以大整数相乘可以用多项式乘积的分治算法实现，实际上大整数相乘就是多项式乘积的一个特例。把一个多项式分为两个P (x)= P0(x)+ P1(x)xn/2 q(x)=q0(x)+q1(x)xn/2 P(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)

6、+q1(x)- P0 * q0 P1* q1于是上式可化简为P(x)*q(x)= R0 +（R2- R0- R1）* xn/2+ R1*xn上述过程可通过递归函数void pro(int p,int q,int r,int n)人来实现求各项系数。求出各系数后还要通过void fe(int A,int n)来处理各项系数，从而求出各乘积上各位的数字。需要指出的是在调用void fe(int A,int n)时，假设数组A上的元素依次为1 -20 1时，最后输出的结果将是: -101实际是-99。但在本实验中类似这种情况是不可能出现的，原因是：在求大整数乘积时传入的各项系数均为非负，于是总有高位

7、满足被借1当10后高位仍为非负的。2.流程控制图设计流程控制图如下所示：开始void product1（）函数递归计算多项式的系数用void plus（）函数和void mins函数进行多项式系数的相加和相减void product（）函数求两个多项式相乘的系数并按从小到大存放得到的系数i=0;i2通过换名是可以求出f(n)= O(nlog3)的这个算法通过对大整数的乘积的解决来体现多项式乘积的实现与运用其中函数void product1(float p,float q,float c)完成多项式的系数的计算，函数void plus(float p,float q,float c,int k)

8、完成 数组p与数组q对应相加并把结果对应放到数组c上，函数void mins(float p,float q,int k) 数组p与数组q对应相减并把结果对应放到数组p上，函数void product(float p,float q,float r,int n) 求多项式p与多项式q的乘积的各项系数，并按指数由小到大储放对应系数在数组r。通过以上几个函数即可求解出两个多项式相乘后的各个系数，进而得到最终的大整数。六、应用举例与程序代码1.应用举例实例问题：大整数乘积以行输入方式输入两个大整数（不限正、负），用分治法计算两个大整数的乘积，并输出计算结果。2.核心代码#include #inclu

9、de#include#define MAXSIZE 51void product1(float p,float q,float c) /递归的基础步，即计算多项式的系数c0=p0*q0;c2=p1*q1;c1=(p0+p1)*(q1+q0)-c0-c2;void plus(float p,float q,float c,int k) /*数组p与数组q对应相加并把结果对应放到数组c上*/int i;for(i=0;ik;i+)ci=pi+qi;void mins(float p,float q,int k) /*数组p与数组q对应相减并把结果对应放到数组p上*/int i;for(i=0;ik

10、;i+)pi=pi-qi;void product(float p,float q,float r,int n) /*求多项式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);int i;int k;for(i=0;i=j)for(l=0;l+)k=(int)pow(2,l);m=(

11、int)pow(2,l+1);if(ik&ik&j=m)break;if(i!=m|j!=m)if(im)for(;im;i+)pi=0;if(jm)for(;jm;j+)qj=0;return m;int main()float pMAXSIZE;float qMAXSIZE;float *r;int k,l,i;k=adjust(p,q);l=2*k-1;r=(float *)malloc(sizeof(float)*(2*k-1);product(p,q,r,k);for(k=l-1;rk=0;k-);printf(两个多项式A,B乘积的多项式的系数如下n注意:按低次向高次项的系数排列n);for(i=0;i=k;i+)printf(%f ,ri);printf(n其典型数学形式如下n);printf(%f ,r0);for(i=1;i=k;i+)printf(+) %.3fx(%d) ,ri,i);printf(n);free(r);return 0;七、运行截图运行结果截图如下图7-1所示图7-1八、总结通过这次实验，我进一步理解了用分治法求解大整数乘法的算法。大整数乘法是一个十分实用的问题，它通过减少两数相乘的次数，来达