两个n位大整数相乘算法

求最大元和次大元1.问题描述从多个数中一次性查找出元素最大的值和最小值，查找元素规模即元素的个数n,用分治的思想编制程序，实现分治的最大元和最小元求法。进一步改进算法，使之能一次性求出最大和和次大元（即第二大元素）。2.算法设计思想及描述分治发的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立与原问题相同。递归地解决这些问题，然后将各个子问题的解合并得到原问题的解。基于课堂的分析知道，对于本问题k的值取为2，这样可以使子问题的规模是相同的，有利于算法实现。为平衡分治时子问题的规模，这里约定需要查找元素的规模n是2的幂次方。用数组存储需要查找的元素，用结构体存储返回的最大元和最小元。每次得到局部的最大元和局部次大元，然后局部最大元和最大元比较得到新的局部最大元，次大元和次大元比较得到新的局部次大元。深入分析，这种方式局部次大元是错误的。如两组元素中，a1b1,a2b2,当然a1和a2中较大的是新的局部最大元，但是b1和b2中较大的元素不是这四个元素中第二大的。这样的方法漏掉了b1可能是次大元的情况，也就是说所有的元素中的次大元可能在与最大元比较的时候被漏掉了。弥补的方法就是每次将每个元素比自身小的元素都用一个淘汰数组保存起来，最后次大元就是最大元的淘汰数组中第二大的那个元素。3.算法分析运用分治算法解决此问题，是因为这种方法的优越行，下面通过时间复杂度的比较来说明。通常算法，设置一个变量，等于需要比较的数组的第一个元素，然后依次与后面的n-1经行比较，需要比较n-1次得到最大元。同理，求得最小元的比较次数仍然是n-1次。设()nT表示比较的次数则对于这种算法得到()nT的值为()22nTn分治算法求最大元比较1()2()22TnnT解方程结果为()1.52Tnn,虽然二者都是线性增长的，可是增长率要小一些。实际编程时的实现有细微差距。另外，求最大元，次大元的时候次大元总是在最大元的淘汰数组中，所以求次大元时，多了从最大元数组中找次大元的情形，n取对数，增长率仍然是比较小的。4.代码#includeiostream.h#defineN10intmax(inta,intb){return((ab)?a:b);}intmin(inta,intb){return((ab)?a:b);}voidSearch(inta[],int*max0,int*second0,intn){intg[30];inti,m;intmax1,max2,second1,second2;if(n==1){*max0=a[0];*second0=a[0];}elseif(n==2){*max0=max(a[0],a[1]);*second0=min(a[0],a[1]);}else{m=n/2;for(i=0;im;i++)g[i]=a[i];Search(g,&max1,&second1,m);for(i=0;in-m;i++)g[i]=a[i+m];Search(g,&max2,&second2,n-m);*max0=max(max1,max2);*second0=max(min(max1,max2),max(second1,second2));}}voidmain(){cout用分治法同时求最大元和次大元\n;inta[N];inti,max,second;cout输入N个数:\n;for(i=0;iN;i++)cina[i];Search(a,&max,&second,N);cout输出结果:\n;coutmax=max\n;coutsecond=second\n;}两个n位大整数相乘算法（1）问题的描述通过分治法求两个大整数的乘法（2）算法设计思想及算法分析设X和Y都是n位的二进制整数，现在要计算它们的乘积XY。我们可以用小学所学的方法来设计一个计算乘积XY的算法，但是这样做计算步骤太多，显得效率较低。如果将每2个1位数的乘法或加法看作一步运算，那么这种方法要作O(n2)步运算才能求出乘积XY。下面我们用分治法来设计一个更有效的大整数乘积算法。x=|A|B|y=|C|D|大整数X和Y的分段我们将n位的二进制整数X和Y各分为2段，每段的长为n/2位(为简单起见，假设n是2的幂)，如上由此，X=A2n/2+B，Y=C2n/2+D。这样，X和Y的乘积为：XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD(1)如果按式(1)计算XY，则我们必须进行4次n/2位整数的乘法(AC，AD，BC和BD)，以及3次不超过n位的整数加法(分别对应于式(1)中的加号)，此外还要做2次移位(分别对应于式(1)中乘2n和乘2n/2)。所有这些加法和移位共用O(n)步运算。设T(n)是2个n位整数相乘所需的运算总数，则由式(1)，我们有:T(1)=1(2)由此可得T(n)=O(n2)。因此，用(1)式来计算X和Y的乘积并不比小学生的方法更有效。要想改进算法的计算复杂性，必须减少乘法次数。为此我们把XY写成另一种形式:XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD(3)虽然，式(3)看起来比式(1)复杂些，但它仅需做3次n/2位整数的乘法(AC，BD和(A-B)(D-C))，6次加、减法和2次移位。由此可得:T(1)=1T(n)=3T(n/2)+cn(4)用解递归方程的套用公式法马上可得其解为T(n)=O(nlog3)=O(n1.59)。利用式(3)，并考虑到X和Y的符号对结果的影响，我们给出大整数相乘的完整算法MULT如下:functionMULT(X，Y，n);{X和Y为2个小于2n的整数，返回结果为X和Y的乘积XY}beginS:=SIGN(X)*SIGN(Y);{S为X和Y的符号乘积}X:=ABS(X);Y:=ABS(Y);{X和Y分别取绝对值}ifn=1thenif(X=1)and(Y=1)thenreturn(S)elsereturn(0)elsebeginA:=X的左边n/2位;B:=X的右边n/2位;C:=Y的左边n/2位;D:=Y的右边n/2位;ml:=MULT(A,C,n/2);m2:=MULT(A-B,D-C,n/2);m3:=MULT(B,D,n/2);S:=S*(m1*2n+(m1+m2+m3)*2n/2+m3);return(S);end;end;上述二进制大整数乘法同样可应用于十进制大整数的乘法以提高乘法的效率减少乘法次数。下面的例子演示了算法的计算过程。设X=314l,Y=5327，用上述算法计算XY的计算过程可列表如下，其中带'号的数值是在计算完成AC，BD，和(A-B)(D-C)之后才填入的。X=3141A=31B=41A-B=-10Y=5327C=53D=27D-C=-26AC=(1643)'BD=(1107)'(A-B)(D-C)=(260)'XY=(1643)'104+[(1643)'+(260)'+(1107)']102+(1107)'=(16732107)'A=31A1=3B1=1A1-B1=2C=53C1=5D1=3D1-C1=-2A1C1=15B1D1=3(A1-B1)(D1-C1)=-4AC=1500+(15+3-4)10+3=1643B=41A2=4B2=1A2-B2=3D=27C2=2D2=7D2-C2=5A2C2=8B2D2=7(A2-B2)(D2-C2)=15BD=800+(8+7+15)10+7=1107|A-B|=10A3=1B3=0A3-B3=1|D-C|=26C3=2D3=6D3-C3=4A3C3=2B3D3=0(A3-B3)(D3-C3)=4(A-B)(D-C)=200+(2+0+4)10+0=260（3）代码/************************************************************************///函数功能：分治法求两个N为的整数的乘积//输入参数：X,Y分别为两个N为整数//算法思想：//时间复杂度为：T(n)=O(nlog3)=O(n1.59)/************************************************************************/#defineSIGN(A)((A0)?1:-1)doubledoubleegerMultiply(doubleX,doubleY,doubleN){doublesign=SIGN(X)*SIGN(Y);doublex=abs(X);doubley=abs(Y);if((0==x)||(0==y))return0;if(1==N)returnx*y;else{doubleXL=x/(double)pow(10.,(double)N/2);doubleXR=x-XL*(double)pow(10.,N/2);doubleYL=y/(double)pow(10.,(double)N/2);doubleYR=y-YL*(double)pow(10.,N/2);doubleXLYL=IntegerMultiply(XL,YL,N/2);doubleXRYR=IntegerMultiply(XR,YR,N/2);doubleXLYRXRYL=IntegerMultiply(XL-XR,YR-YL,N/2)+XLYL+XRYR;returnsign*(XLYL*(double)pow(10.,N)+XLYRXRYL*(double)pow(10.,N/2)+XRYR);}}double_tmain(doubleargc,_TCHAR*argv[]){doublex=1234;doubley=4321;coutx*y=IntegerMultiply(x,y,4)endl;coutx*y=x*yendl;return0;}