算法设计总结.docx

发布时间：2022-06-13 发布人：admin 分类：说明书资料大小：3.59M 资料格式：docx 举报版权申诉

9953ecc8-e1a9-4121-b507-b0fb2e1ab89a.docx.pdf-第1页.png

第1页 / 共24页

9953ecc8-e1a9-4121-b507-b0fb2e1ab89a.docx.pdf-第2页.png

第2页 / 共24页

9953ecc8-e1a9-4121-b507-b0fb2e1ab89a.docx.pdf-第3页.png

第3页 / 共24页

9953ecc8-e1a9-4121-b507-b0fb2e1ab89a.docx.pdf-第4页.png

第4页 / 共24页

9953ecc8-e1a9-4121-b507-b0fb2e1ab89a.docx.pdf-第5页.png

第5页 / 共24页

9953ecc8-e1a9-4121-b507-b0fb2e1ab89a.docx.pdf-第6页.png

第6页 / 共24页

9953ecc8-e1a9-4121-b507-b0fb2e1ab89a.docx.pdf-第7页.png

第7页 / 共24页

9953ecc8-e1a9-4121-b507-b0fb2e1ab89a.docx.pdf-第8页.png

第8页 / 共24页

平面最接近点问题描述

大整数乘法问题描述通常，在分析一个算法的计算复杂性时，都将加法和乘法运算当作是基本运算来处理，即将执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的常数。这个假定仅在计算机硬件能对参加运算的整数直接表示和处理时才是合理的。然而，在某些情况下，我们要处理很大的整数，它无法在计算机硬件能直接表示的范围内进行处理。若用浮点数来表示它，则只能近似地表示它的大小，计算结果中的有效数字也受到限制。若要精确地表示大整数并在计算结果中要求精确地得到所有位数上的数字，就必须用软件的方法来实现大整数的算术运算。请设计一个有效的算法，可以进行两个n 位大整数的乘法运算。参考解答大整数的乘法问题描述参考解答设X 和Y 都是n 位的二进制整数，现在要计算它们的乘积XY。我们可以用小学所学的方法来设计一个计算乘积XY 的算法，但是这样做计算步骤太多，显得效率较低。如果将每2 个1 位数的乘法或加法看作一步运算，那么这种方法要作O(n2) 步运算才能求出乘积XY。下面我们用分治法来设计一个更有效的大整数乘积算法。

图6-3 大整数X 和Y 的分段我们将n 位的二进制整数X 和Y 各分为2 段，每段的长为n/2 位(为简单起见，假设n 是2 的幂)，如图6-3 所示。由此，X=A*2^n/2+B ，Y=C*2^n/2+D。这样，X 和Y 的乘积为： (1) XY=(A*2^n/2+B)(C*2n/2+D)=AC*2^n+(AD+CB)*2^n+BD 如果按式(1)计算XY，则我们必须进行4 次n/2 位整数的乘法(AC，AD，BC 和 BD)，以及3 次不超过n 位的整数加法(分别对应于式(1)中的加号)，此外还要做2 次移位(分别对应于式(1)中乘2n 和乘2n/2)。所有这些加法和移位共用O(n)步运算。设T(n)是2 个n 位整数相乘所需的运算总数，则由式(1)，我们有: (2) 由此可得T(n)=O(n^2)。因此，用(1)式来计算X 和Y 的乘积并不比小学生的方法更有效。要想改进算法的计算复杂性，必须减少乘法次数。为此我们把XY 写成另一种形式: XY=AC*2^n+[(A-B)(D-C)+AC+BD]*2^n+BD (3) 虽然，式(3)看起来比式(1)复杂些，但它仅需做3 次n/2 位整数的乘法(AC，BD 和(A-B)(D-C))，6 次加、减法和2 次移位。由此可得: (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=1then if(X=1)and(Y=1)thenreturn(S) elsereturn(0) elsebegin A:=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*2^n+(m1+m2+m3)*2^n/2+m3); return(S); end; end;上述二进制大整数乘法同样可应用于十进制大整数的乘法以提高乘法的效率减少乘设X=314l,Y=5327，用上述算法计算XY 的计算过程可列表如下，其中带' 号的数值是在计算完成AC，BD，和(A-B)(D-C)之后才填入的。 X=3141 A=31 B=41 D=27 C=53 Y=5327 AC=(1643)' BD=(1107)' (A-B)(D-C)=(260)' XY=(1643)'10^4+[(1643)'+(260)'+(1107)']102+(1107)' =(16732107)' A1-B1=2 B1=1 A1=3 A=31 D1-C1=-2 C=53 C1=5 D1=3 A1C1=15 B1D1=3 (A1-B1)(D1-C1)=-4 AC=1500+(15+3-4)10+3=1643 A2-B2=3 B=41 A2=4 B2=1 D2-C2=5 C2=2 D2=7 D=27 (A2-B2)(D2-C2)=15 A2C2=8 B2D2=7 A-B=-10 D-C=-26

A3=1 C3=2 BD=800+(8+7+15)10+7=1107 |A-B|=10 B3=0 A3-B3=1 D3=6 |D-C|=26 D3-C3=4 A3C3=2 B3D3=0 (A3-B3)(D3-C3)=4 (A-B)(D-C)=200+(2+0+4)10+0=260 如果将一个大整数分成3 段或4 段做乘法，计算复杂性会发生会么变化呢?是否优于分成2 段做的乘法？这个问题请大家自己考虑。

分享到：

赞收藏

资料库

算法设计总结.docx

相关推荐

课程资源

热门标签

最新资料