考试网 >> IT认证 >> 水平 >> 软件指导 >> 软考常用算法设计方法(二)

发布时间：2006-06-28 04:49     点击：

　　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次移位。由此可得：

　　 （4）

　　用解递归方程的套用公式法马上可得其解为T(n)=O(nlog3)=O(n1.59)。利用式（3），并考虑到X和Y的符号对结果的影响，我们给出大整数相乘的完整算法MULT如下：

　　function MULT(X，Y，n); {X和Y为2个小于2n的整数，返回结果为X和Y的乘积XY}

　　begin

　　S=SIGN(X)*SIGN(Y); {S为X和Y的符号乘积}

　　X=ABS(X);

　　Y=ABS(Y); {X和Y分别取绝对值}

　　if n=1 then

　　if (X=1)and(Y=1) then return(S)

　　else return(0)

　　else begin

　　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*2n+(m1+m2+m3)*2n/2+m3);

　　return(S); 

　　end;

　　end;

　　上述二进制大整数乘法同样可应用于十进制大整数的乘法以提高乘法的效率减少乘法次数。

【问题】 最接近点对问题

　　问题描述：

　　在应用中，常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉及这些几何对象的问题中，常需要了解其邻域中其他几何对象的信息。例如，在空中交通控制问题中，若将飞机作为空间中移动的一个点来看待，则具有最大碰撞危险的2架飞机，就是这个空间中最接近的一对点。这类问题是计算几何学中研究的基本问题之一。下面我们着重考虑平面上的最接近点对问题。

　　最接近点对问题的提法是：给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。

　　严格地说，最接近点对可能多于1对。为了简单起见，这里只限于找其中的一对。

　　这个问题很容易理解，似乎也不难解决。我们只要将每一点与其他n-1个点的距离算出，找出达到最小距离的两个点即可。然而，这样做效率太低，需要O(n2)的计算时间。我们能否找到问题的一个O (nlogn)算法。

发表评论： 匿名发表 用户名: 查看评论

您将承担一切因您的行为、言论而直接或间接导致的民事或刑事法律责任 留言板管理人员有权保留或删除其管辖留言中的任意内容 本站提醒：不要进行人身攻击。谢谢配合。