多项式乘积算法设计与分析.docx
- 文档编号:18313293
- 上传时间:2023-08-15
- 格式:DOCX
- 页数:12
- 大小:91.73KB
多项式乘积算法设计与分析.docx
《多项式乘积算法设计与分析.docx》由会员分享,可在线阅读,更多相关《多项式乘积算法设计与分析.docx(12页珍藏版)》请在冰点文库上搜索。
多项式乘积算法设计与分析
算法设计与分析课程设计论文
课题名称:
多项式乘积的分治算法设计与实现
院系:
计算机科学与信息工程学院
专业:
计算机科学与技术(信息方向)11-1
姓名学号:
潘强201103020005
指导教师:
冯慧玲
2013年12月
目录
一、算法介绍3
二、问题描述3
三、相关概念和数据结构介绍4
四、算法设计与流程图4
1.算法设计4
2.流程控制图5
五、算法分析7
六、应用举例与程序代码7
1.应用举例7
2.核心代码7
七、运行截图10
八、总结11
多项式乘积算法设计与分析
一、算法介绍
在计算机科学中,分治法是一种很重要的算法。
字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)等。
分治法在每一层递归上都有三个步骤:
分解:
将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
解决:
若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题;
合并:
将各个子问题的解合并为原问题的解。
它的一般的算法设计模式如下:
Divide-and-Conquer(P)
1.if|P|≤n0
2.thenreturn(ADHOC(P))
3.将P分解为较小的子问题P1,P2,...,Pk
4.fori←1tok
5.doyi←Divide-and-Conquer(Pi)△递归解决Pi
6.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的解。
二、问题描述
用分治算法解决多项式乘积问题
由于任意大整数都可以看作是一多项式,所以大整数相乘是多项式乘积的一个特例,通过解决大整数乘积,即是解决了多项式的乘积问题。
三、相关概念和数据结构介绍
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/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)+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。
但在本实验中类似这种情况是不可能出现的,原因是:
在求大整数乘积时传入的各项系数均为非负,于是总有高位满足被借1当10后高位仍为非负的。
2.流程控制图
设计流程控制图如下所示:
五、算法分析
很显然算法的时间复杂度由求各系数时调用voidpro(intp[],intq[],intr[],intn)所决定
类似多项式的算法时间复杂度分析
f
(2)=7n=2
f(n)=3f(n/2)+5nn>2
通过换名是可以求出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.核心代码
#include
#include
#include
#defineMAXSIZE51
voidproduct1(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];
}
voidplus(floatp[],floatq[],floatc[],intk)/*数组p[]与数组q[]对应相加并把结果对应放到数组c[]上*/
{
inti;
for(i=0;i c[i]=p[i]+q[i]; } voidmins(floatp[],floatq[],intk)/*数组p[]与数组q[]对应相减并把结果对应放到数组p[]上*/ { inti; for(i=0;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;i<2*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,结果放在r2 plus(q,q+k,r3,k);//求q0+q1,结果放在r3 product(r2,r3,r2+k,k);//递归计算r2; mins(r2+k,r,2*k-1);//求r2-r0-r1,结果放到r+k mins(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[]) { 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(i>k&&i<=m) break; } } else { for(l=0;;l++) { k=(int)pow(2,l); m=(int)pow(2,l+1); if(j>k&&j<=m) break; } } if(i! =m||j! =m) { if(i for(;i p[i]=0; if(j for(;j q[j]=0; } returnm; } intmain() { floatp[MAXSIZE];floatq[MAXSIZE];float*r; intk,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;r[k]==0;k--); printf("两个多项式A,B乘积的多项式的系数如下\n注意: 按低次向高次项的系数排列\n"); for(i=0;i<=k;i++) printf("%f",r[i]); printf("\n其典型数学形式如下\n"); printf("%f",r[0]); for(i=1;i<=k;i++) printf("(+)%.3fx^(%d)",r[i],i); printf("\n"); free(r); return0; } 七、运行截图 运行结果截图如下图7-1所示 图7-1 八、总结 通过这次实验,我进一步理解了用分治法求解大整数乘法的算法。 大整数乘法是一个十分实用的问题,它通过减少两数相乘的次数,来达到降低间复杂度,提高算法效率的目的。 解决大整数乘积的问题,让我对多项式乘积的实现与应用有了更多的了解与认识,对分治算法的在改进程序时间复杂度以及优化程序方面的优点有了更多的了解。 通过查阅书籍以及上网查询,另外通过和同学的交流,我最终完成了这次的期末课程设计论文,但也让我明白自己有很多不足,不能很好的讲所学知识与实例相结合,对实例的实现还不够熟悉和明白,需要多加学习。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 多项式 乘积 算法 设计 分析
![提示](https://static.bingdoc.com/images/bang_tan.gif)