计算几何常用算法概览
本站原创：怒火之袍一、引言
计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。
二、目录
本文整理的计算几何基本概念和常用算法包括如下内容：
矢量的概念
三、算法介绍
矢量的概念：
如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点，我们可以把它称为矢量(vector)p2。
矢量加减法：
设二维矢量P = ( x1,y1 ) ，Q = ( x2 , y2 ) ，则矢量加法定义为：P + Q = ( x1 + x2 , y1 + y2 )，同样的，矢量减法定义为：P - Q = ( x1 - x2 , y1 - y2 )。显然有性质P + Q = Q + P , P - Q = - ( Q - P )。
矢量叉积：
计算矢量叉积是与直线和线段相关算法的核心部分。设矢量P =
（x1,y1），Q = (x2,y2)，则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面积，即：P ×Q = x1*y2 - x2*y1，其结果是一个标量。显然有性质P ×Q = - ( Q ×P ) 和P ×( - Q ) = - ( P ×Q )。一般在不加说明的情况下，本文下述算法中所有的点都看作矢量，两点的加减法就是矢量相加减，而点的乘法则看作矢量叉积。
叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的
顺逆时针关系：
若P ×Q > 0 , 则P在Q的顺时针方向。
若P ×Q < 0 , 则P在Q的逆时针方向。
若P ×Q = 0 , 则P与Q共线，但可能同向也可能反向。
折线段的拐向判断：
折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段p0p1和p1p2，通过计算(p2 - p0) ×(p1 - p0)的符号便可以确定折线段的拐向：
若(p2 - p0) ×(p1 - p0) > 0,则p0p1在p1点拐向右侧后得到p1p2。
若(p2 - p0) ×(p1 - p0) < 0,则p0p1在p1点拐向左侧后得到p1p2。
若(p2 - p0) ×(p1 - p0) = 0,则p0、p1、p2三点共线。
具体情况可参照下图：
判断点是否在线段上：
设点为Q，线段为P1P2 ，判断点Q在该线段上的依据是：( Q - P1 ) ×( P2 - P1 ) = 0 且Q 在以P1，P2为对角顶点的矩形内。前者保证Q点在直线P1P2上，后者是保证Q点不在线段P1P2的延长线或反向延长线上，对于这一步骤的判断可以用以下过程实现：
ON-SEGMENT(pi,pj,pk)
if min(xi,xj)<=xk<=max(xi,xj) and min(yi,yj)<=yk<=max(yi,yj)
then return true;
else return false;
特别要注意的是，由于需要考虑水平线段和垂直线段两种特殊情况，min(xi,xj)<=xk<=max(xi,xj)和min(yi,yj)<=yk<=max(yi,yj)两个条件必须同时满足才能返回真值。
判断两线段是否相交：
我们分两步确定两条线段是否相交：
(1)快速排斥试验
设以线段P1P2 为对角线的矩形为R，设以线段Q1Q2 为对角线的矩形为T，如果R和T不相交，显然两线段不会相交。
(2)跨立试验
如果两线段相交，则两线段必然相互跨立对方。若P1P2跨立Q1Q2 ，则矢量( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧，即( P1 - Q1 ) ×( Q2 - Q1 ) * ( P2 - Q1 ) ×( Q2 - Q1 ) < 0。上式可改写成( P1 - Q1 ) ×( Q2 - Q1 ) * ( Q2 - Q1 ) ×( P2 - Q1 ) > 0。当( P1 - Q1 ) ×( Q2 - Q1 ) = 0 时，说明( P1 - Q1 ) 和( Q2 - Q1 )共线，但是因为已经通过快速排斥试验，
所以P1 一定在线段Q1Q2上；同理，( Q2 - Q1 ) ×(P2 - Q1 ) = 0 说明P2 一定在线段Q1Q2上。所以判断P1P2跨立Q1Q2的依据是：( P1 - Q1 ) ×( Q2 - Q1 ) * ( Q2 - Q1 ) ×( P2 - Q1 ) >= 0。同理判断Q1Q2跨立P1P2的依据是：( Q1 - P1 ) ×( P2 - P1 ) * ( P2 - P1 ) ×( Q2 - P1 ) >= 0。具体情况如下图所示：
在相同的原理下，对此算法的具体的实现细节可能会与此有所不同，除了这种过程外，大家也可以参考《算法导论》上的实现。
判断线段和直线是否相交：
有了上面的基础，这个算法就很容易了。如果线段P1P2和直线Q1Q2相交，则P1P2跨立Q1Q2，即：( P1 - Q1 ) ×( Q2 - Q1 ) * ( Q2 - Q1 ) ×( P2 - Q1 ) >= 0。
判断矩形是否包含点：
只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。
判断线段、折线、多边形是否在矩形中：
因为矩形是个凸集，所以只要判断所有端点是否都在矩形中就可以了。
判断矩形是否在矩形中：
只要比较左右边界和上下边界就可以了。
判断圆是否在矩形中：
很容易证明，圆在矩形中的充要条件是：圆心在矩形中且圆的半径小于等于圆心到矩形四边的距离的最小值。
判断点是否在多边形中：
判断点P是否在多边形中是计算几何中一个非常基本但是十分重要的算法。以点P为端点，向左方作射线L，由于多边形是有界的，所以射线L 的左端一定在多边形外，考虑沿着L从无穷远处开始自左向右移动，遇到和多边形的第一个交点的时候，进入到了多边形的内部，遇到第二个交点的时候，离开了多边形，……所以很容易看出当L和多边形的交点数目C 是奇数的时候，P在多边形内，是偶数的话P在多边形外。
但是有些特殊情况要加以考虑。如图下图(a)(b)(c)(d)所示。在图(a)中，L 和多边形的顶点相交，这时候交点只能计算一个；在图(b)中，L和多边形
顶点的交点不应被计算；在图(c)和(d) 中，L和多边形的一条边重合，这条边应该被忽略不计。如果L和多边形的一条边重合，这条边应该被忽略不计。
为了统一起见，我们在计算射线L和多边形的交点的时候，1。对于多边形的水平边不作考虑；2。对于多边形的顶点和L相交的情况，如果该顶点是其所属的边上纵坐标较大的顶点，则计数，否则忽略；3。对于P在多
边形边上的情形，直接可判断P属于多边行。由此得出算法的伪代码如下：
count ←0;
以P为端点，作从右向左的射线L;
for 多边形的每条边s
do if P在边s上
then return true;
if s不是水平的
then if s的一个端点在L上
if 该端点是s两端点中纵坐标较大的端点
then count ←count+1
else if s和L相交
then count ←count+1;
if count mod 2 = 1
then return true;
else return false;
其中做射线L的方法是：设P'的纵坐标和P相同，横坐标为正无穷大（很大的一个正数），则P和P'就确定了射线L。
判断点是否在多边形中的这个算法的时间复杂度为O(n)。
另外还有一种算法是用带符号的三角形面积之和与多边形面积进行比较，这种算法由于使用浮点数运算所以会带来一定误差，不推荐大家使用。
判断线段是否在多边形内：
线段在多边形内的一个必要条件是线段的两个端点都在多边形内，但由于多边形可能为凹，所以这不能成为判断的充分条件。如果线段和多边形的某条边内交（两线段内交是指两线段相交且交点不在两线段的端点），因为多边形的边的左右两侧分属多边形内外不同部分，所以线段一定会有一部分在多边形外(见图a)。于是我们得到线段在多边形内的第二个必要条件：线段和多边形的所有边都不内交。
线段和多边形交于线段的两端点并不会影响线段是否在多边形内；但是如果多边形的某个顶点和线段相交，还必须判断两相邻交点之间的线段是否包含于多边形内部（反例见图b)。
因此我们可以先求出所有和线段相交的多边形的顶点，然后按照X-Y坐标排序(X坐标小的排在前面，对于X坐标相同的点，Y坐标小的排在前面，这种排序准则也是为了保证水平和垂直情况的判断正确)，这样相邻的两个点就是在线段上相邻的两交点，如果任意相邻两点的中点也在多边形内，则该线段一定在多边形内。
证明如下：
命题1：
如果线段和多边形的两相邻交点P1 ，P2的中点P' 也在多边形内，则P1, P2之间的所有点都在多边形内。
证明：
假设P1,P2之间含有不在多边形内的点，不妨设该点为Q，在P1, P'之间，因为多边形是闭合曲线，所以其内外部之间有界，而P1属于多边行内部，Q属于多边性外部，P'属于多边性内部，P1-Q-P'完全连续，所以P1Q 和QP'一定跨越多边形的边界，因此在P1,P'之间至少还有两个该线段和多边形的交点，这和P1P2是相邻两交点矛盾，故命题成立。证毕。
由命题1直接可得出推论：
推论2：
设多边形和线段PQ的交点依次为P1,P2,……Pn，其中Pi和Pi+1是相
邻两交点，线段PQ在多边形内的充要条件是：P，Q在多边形内且对于i =1, 2,……, n-1，Pi ,Pi+1的中点也在多边形内。
在实际编程中，没有必要计算所有的交点，首先应判断线段和多边形的边是否内交，倘若线段和多边形的某条边内交则线段一定在多边形外；如果线段和多边形的每一条边都不内交，则线段和多边形的交点一定是线段的端点或者多边形的顶点，只要判断点是否在线段上就可以了。
至此我们得出算法如下：
if 线端PQ的端点不都在多边形内
then return false;
点集pointSet初始化为空;
for 多边形的每条边s
do if 线段的某个端点在s上
then 将该端点加入pointSet;
else if s的某个端点在线段PQ上
then 将该端点加入pointSet;
else if s和线段PQ相交// 这时候已经可以肯定是内交了
then return false;
将pointSet中的点按照X-Y坐标排序;
for pointSet中每两个相邻点pointSet[i] , pointSet[ i+1]
do if pointSet[i] , pointSet[ i+1] 的中点不在多边形中
then return false;
return true;
这个过程中的排序因为交点数目肯定远小于多边形的顶点数目n，所以最多是常数级的复杂度，几乎可以忽略不计。因此算法的时间复杂度也是O(n)。
判断折线是否在多边形内：
只要判断折线的每条线段是否都在多边形内即可。设折线有m条线段，多边形有n个顶点，则该算法的时间复杂度为O(m*n)。
判断多边形是否在多边形内：
只要判断多边形的每条边是否都在多边形内即可。判断一个有m个顶点的多边形是否在一个有n个顶点的多边形内复杂度为O(m*n)。
判断矩形是否在多边形内：
将矩形转化为多边形，然后再判断是否在多边形内。
判断圆是否在多边形内：
只要计算圆心到多边形的每条边的最短距离，如果该距离大于等于圆半径则该圆在多边形内。计算圆心到多边形每条边最短距离的算法在后文阐述。
判断点是否在圆内：
计算圆心到该点的距离，如果小于等于半径则该点在圆内。
判断线段、折线、矩形、多边形是否在圆内：
因为圆是凸集，所以只要判断是否每个顶点都在圆内即可。
判断圆是否在圆内：
设两圆为O1,O2，半径分别为r1, r2，要判断O2是否在O1内。先比较r1，r2的大小，如果r1 计算点到线段的最近点： 如果该线段平行于X轴（Y轴），则过点point作该线段所在直线的垂线，垂足很容易求得，然后计算出垂足，如果垂足在线段上则返回垂足，否则返回离垂足近的端点；如果该线段不平行于X轴也不平行于Y轴，则斜率存在且不为0。设线段的两端点为pt1和pt2，斜率为：k = ( pt2.y - pt1. y ) / (pt2.x - pt1.x );该直线方程为：y = k* ( x - pt1.x) + pt1.y。其垂线的斜率为- 1 / k，垂线方程为：y = (-1/k) * (x - point.x) + point.y 。 联立两直线方程解得：x = ( k^2 * pt1.x + k * (point.y - pt1.y ) + point.x ) / ( k^2 + 1) ，y = k * ( x - pt1.x) + pt1.y;然后再判断垂足是否在线段上，如果 在线段上则返回垂足；如果不在则计算两端点到垂足的距离，选择距离垂足较近的端点返回。 计算点到折线、矩形、多边形的最近点： 只要分别计算点到每条线段的最近点，记录最近距离，取其中最近距离最小的点即可。 计算点到圆的最近距离及交点坐标： 如果该点在圆心，因为圆心到圆周任一点的距离相等，返回UNDEFINED。 连接点P和圆心O，如果PO平行于X轴，则根据P在O的左边还是右边计算出最近点的横坐标为centerPoint.x - radius 或centerPoint.x + radius。如果PO平行于Y轴，则根据P在O的上边还是下边计算出最近点的纵坐标为centerPoint.y -+radius或centerPoint.y - radius。如果PO不平行于X 轴和Y轴，则PO的斜率存在且不为0，这时直线PO斜率为k = （P.y - O.y ）/ ( P.x - O.x )。直线PO的方程为：y = k * ( x - P.x) + P.y。设圆方程为:(x - O.x ) ^2 + ( y - O.y ) ^2 = r ^2，联立两方程组可以解出直线PO和圆的交点，取其中离P点较近的交点即可。 计算两条共线的线段的交点： 对于两条共线的线段，它们之间的位置关系有下图所示的几种情况。图(a)中两条线段没有交点；图(b) 和(d) 中两条线段有无穷焦点；图(c) 中 两条线段有一个交点。设line1是两条线段中较长的一条，line2是较短的一条，如果line1包含了line2的两个端点，则是图(d)的情况，两线段有无穷交点；如果line1只包含line2的一个端点，那么如果line1的某个端点等于被line1包含的line2的那个端点，则是图(c)的情况，这时两线段只有一个交点，否则就是图(b)的情况，两线段也是有无穷的交点；如果line1不包含line2的任何端点，则是图(a)的情况，这时两线段没有交点。 计算线段或直线与线段的交点: 设一条线段为L0 = P1P2，另一条线段或直线为L1 = Q1Q2 ，要计算的就是L0和L1的交点。 1．首先判断L0和L1是否相交（方法已在前文讨论过），如果不相交则没有交点，否则说明L0和L1一定有交点，下面就将L0和L1都看作直线来考虑。 2．如果P1和P2横坐标相同，即L0平行于Y轴 a) 若L1也平行于Y轴， i. 若P1的纵坐标和Q1的纵坐标相同，说明L0和L1共线，假如L1是直线的话他们有无穷的交点，假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点（该方法在前文已讨论过）； ii. 否则说明L0和L1平行，他们没有交点； b) 若L1不平行于Y轴，则交点横坐标为P1的横坐标，代入到L1的直线方程中可以计算出交点纵坐标； 3．如果P1和P2横坐标不同，但是Q1和Q2横坐标相同，即L1平行于Y轴，则交点横坐标为Q1的横坐标，代入到L0的直线方程中可以计算出交点纵坐标； 4．如果P1和P2纵坐标相同，即L0平行于X轴 a) 若L1也平行于X轴， i. 若P1的横坐标和Q1的横坐标相同，说明L0和L1共线，假如L1是直线的话他们有无穷的交点，假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点（该方法在前文已讨论过）； ii. 否则说明L0和L1平行，他们没有交点； b) 若L1不平行于X轴，则交点纵坐标为P1的纵坐标，代入到L1的直线方程中可以计算出交点横坐标； 5．如果P1和P2纵坐标不同，但是Q1和Q2纵坐标相同，即L1平行于X轴，则交点纵坐标为Q1的纵坐标，代入到L0的直线方程中可以计算出交点横坐标； 6．剩下的情况就是L1和L0的斜率均存在且不为0的情况 a) 计算出L0的斜率K0，L1的斜率K1 ； b) 如果K1 = K2 i. 如果Q1在L0上，则说明L0和L1共线，假如L1是直线的话有无穷交点，假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点（该方法在前文已讨论过）； ii. 如果Q1不在L0上，则说明L0和L1平行，他们没有交点。 c) 联立两直线的方程组可以解出交点来 这个算法并不复杂，但是要分情况讨论清楚，尤其是当两条线段共线的 情况需要单独考虑，所以在前文将求两条共线线段的算法单独写出来。另外，一开始就先利用矢量叉乘判断线段与线段（或直线）是否相交，如果结果是相交，那么在后面就可以将线段全部看作直线来考虑。需要注意的是，我们可以将直线或线段方程改写为ax+by+c=0的形式，这样一来上述过程的部分步骤可以合并，缩短了代码长度，但是由于先要求出参数，这种算法将花费更多的时间。 求线段或直线与折线、矩形、多边形的交点： 分别求与每条边的交点即可。 求线段或直线与圆的交点: 设圆心为O，圆半径为r，直线（或线段）L上的两点为P1,P2。 1. 如果L是线段且P1，P2都包含在圆O内，则没有交点；否则进行下一步。 2. 如果L平行于Y轴， a) 计算圆心到L的距离dis； b) 如果dis > r 则L和圆没有交点； c) 利用勾股定理，可以求出两交点坐标，但要注意考虑L和圆的相切情况。 3. 如果L平行于X轴，做法与L平行于Y轴的情况类似； 4. 如果L既不平行X轴也不平行Y轴，可以求出L的斜率K，然后列出L的点斜式方程，和圆方程联立即可求解出L和圆的两个交点； 5. 如果L是线段，对于2，3，4中求出的交点还要分别判断是否属于该线段的范围内。 凸包的概念： 点集Q的凸包(convex hull)是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。下图中由红色线段表示的多边形就是点集 Q={p0,p1,...p12}的凸包。 凸包的求法： 现在已经证明了凸包算法的时间复杂度下界是O(n*logn),但是当凸包的顶点数h也被考虑进去的话，Krikpatrick和Seidel的剪枝搜索算法可以达 计算几何基础知识整理 一、序言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。 二、本基础目录 本文整理的计算几何基本概念和常用算法包括如下内容： 1. 矢量的概念 2. 矢量加减法 3. 矢量叉积 4. 折线段的拐向判断 5. 判断点是否在线段上 6. 判断两线段是否相交 7. 判断线段和直线是否相交 8. 判断矩形是否包含点 9. 判断线段、折线、多边形是否在矩形中 10. 判断矩形是否在矩形中 11. 判断圆是否在矩形中 12. 判断点是否在多边形中 13. 判断线段是否在多边形内 14. 判断折线是否在多边形内 15. 判断多边形是否在多边形内 16. 判断矩形是否在多边形内 17. 判断圆是否在多边形内 18. 判断点是否在圆内 19. 判断线段、折线、矩形、多边形是否在圆内 20. 判断圆是否在圆内 21. 计算点到线段的最近点 22. 计算点到折线、矩形、多边形的最近点 23. 计算点到圆的最近距离及交点坐标 24. 计算两条共线的线段的交点 25. 计算线段或直线与线段的交点 26. 求线段或直线与折线、矩形、多边形的交点 27. 求线段或直线与圆的交点 28. 凸包的概念 29. 凸包的求法 三、算法介绍 1.矢量的概念： 如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed POJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,p oj2255,poj3094) 初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序(poj1094) (5)二分图的最大匹配(匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) 三.数据结构. (1)串(poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) (5)哈夫曼树(poj3253) (6)堆 (7)trie树(静态建树、动态建树) (poj2513) 四.简单搜索 (1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251) (2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414) (3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129) 五.动态规划 (1)背包问题. (poj1837,poj1276) (2)型如下表的简单DP(可参考lrj的书page149): 1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533) 2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159) 3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题) 六.数学 (1)组合数学: 第一部分、计算机算法常用术语中英对照 Data Structures 基本数据结构 Dictionaries 字典 Priority Queues 堆 Graph Data Structures 图 Set Data Structures 集合 Kd-Trees 线段树 Numerical Problems 数值问题 Solving Linear Equations 线性方程组 Bandwidth Reduction 带宽压缩 Matrix Multiplication 矩阵乘法 Determinants and Permanents 行列式 Constrained and Unconstrained Optimization 最值问题Linear Programming 线性规划 Random Number Generation 随机数生成 Factoring and Primality Testing 因子分解/质数判定Arbitrary Precision Arithmetic 高精度计算Knapsack Problem 背包问题 Discrete Fourier Transform 离散Fourier变换Combinatorial Problems 组合问题 Sorting 排序 Searching 查找 Median and Selection 中位数 Generating Permutations 排列生成 Generating Subsets 子集生成 Generating Partitions 划分生成 Generating Graphs 图的生成 Calendrical Calculations 日期 Job Scheduling 工程安排 Satisfiability 可满足性 Graph Problems -- polynomial 图论-多项式算法Connected Components 连通分支 Topological Sorting 拓扑排序 Minimum Spanning Tree 最小生成树 Shortest Path 最短路径 Transitive Closure and Reduction 传递闭包Matching 匹配 Eulerian Cycle / Chinese Postman Euler回路/中国邮路Edge and Vertex Connectivity 割边/割点 Network Flow 网络流 Drawing Graphs Nicely 图的描绘 Drawing Trees 树的描绘 Planarity Detection and Embedding 平面性检测和嵌入 GIS算法的计算几何基础 矢量的概念： 如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed segment)。 如果有向线段p1p2的起点p1在坐标原点，我们可以把它称为矢量(vector)p2。 矢量加减法： 设二维矢量P = ( x1, y1 )，Q = ( x2 , y2 )， 则矢量加法定义为： P + Q = ( x1 + x2 , y1 + y2 )， 矢量减法定义为： P - Q = ( x1 - x2 , y1 - y2 )。 显然有性质 P + Q = Q + P，P - Q = - ( Q - P )。 矢量叉积： 计算矢量叉积是与直线和线段相关算法的核心部分。 设矢量P = ( x1, y1 )，Q = ( x2, y2 )， 则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面积， 即：P × Q = x1*y2 - x2*y1，其结果是一个标量。 显然有性质P × Q = - ( Q × P ) 和P × ( - Q ) = - ( P × Q )。 两点的加减法就是矢量相加减，而点的乘法则看作矢量叉积。 叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系： 若P × Q > 0 , 则P在Q的顺时针方向。 若P × Q < 0 , 则P在Q的逆时针方向。 若P × Q = 0 , 则P与Q共线，但可能同向也可能反向。 折线段的拐向判断： 折线段的拐向判断方法可以直接由矢量叉积的性质推出。 对于有公共端点的线段p0p1和p1p2，通过计算(p2 - p0) × (p1 - p0)的符号便可以确定折线段的拐向： 若(p2 - p0) × (p1 - p0) > 0,则p0p1在p1点拐向右侧后得到p1p2。 若(p2 - p0) × (p1 - p0) < 0,则p0p1在p1点拐向左侧后得到p1p2。 简介：计算机考研之家搜集的华为C语言经典面试题，来试试你的C语言水平吧。每道题都附有详细解答和讲解，很有参考价值的C语言面试题。 怎么判断链表中是否有环？ bool CircleInList(Link* pHead) { if(pHead = = NULL || pHead->next = = NULL)//无节点或只有一个节点并且无自环 return (false); if(pHead->next = = pHead)//自环 return (true); Link *pTemp1 = pHead;//step 1 Link *pTemp = pHead->next;//step 2 while(pTemp != pTemp1 && pTemp != NULL && pTemp->next != NULL) { pTemp1 = pTemp1->next; pTemp = pTemp->next->next; } if(pTemp = = pTemp1) return (true); return (false); } 两个字符串，s,t;把t字符串插入到s字符串中，s字符串有足够的空间存放t字符串 void insert(char *s, char *t, int i) { memcpy(&s[strlen(t)+i],&s[i],strlen(s)-i); memcpy(&s[i],t,strlen(t)); s[strlen(s)+strlen(t)]='\0'; } 1。编写一个C 函数，该函数在一个字符串中找到可能的最长的子字符串，且该字符串是由同一字符组成的。 char * search(char *cpSource, char ch) { char *cpTemp=NULL, *cpDest=NULL; int iTemp, iCount=0; while(*cpSource) { if(*cpSource == ch) { iTemp = 0; cpTemp = cpSource; while(*cpSource == ch) ++iTemp, ++cpSource; if(iTemp > iCount) 度。下图是个例子： 四、实验结果与分析（源程序及相关说明） 1)#include 平面几何图形的画法 按照能否通用，平面几何图形大致可以分为两类：一类是没有具体尺寸要求的相交线、平行线、角、三角形、四边形等等；另一类则是需要符合题目条件与结论，或有严格尺寸要求的图形。无论哪一类，都可以凭借Word页面的“绘图工具”画出来，再利用Windows自带的“画图”程序进行编辑。下面举两例予以说明，敬请同仁赐教。 例1、如图，在三角形纸片ABC中，∠C=90°，∠A=30°，AC=3，折叠该纸片，使点A 与点B重合，折痕与AB，AC分别相交于点D，E，求折痕DE的长。 〖画法〗： 1、点击“插入”→“形状”，选择直线形，插入一条水平直线和一条竖直直线，如图（1）； 2、右击直线，选“设置对象格式”，如图（2）； 3、在“颜色与线条”里，将两条直线均设置为黑色、0.75磅，如图（3）； 4、将水平直线复制成3条，如图（4）； 5、右击其中一条水平直线，在“设置对象格式”→“大小”→“旋转”右框内，输入数字“30”，如图（5）；这时所选直线顺时针旋转30°，如图（6）； 6、再选择一条水平直线，将其顺时针旋转60°，如图（7），图（8）； 7、插入一条水平直线，设置为黑色、0.75磅，并顺时针旋转120°，如图（9）； 8、按住“Ctrl”键依次点击排列好的每条直线，在“图片工具”里选择“组合”，并且“另存图片”到某个文件夹，如图（10）； 9、在Windows自带的“画图”程序中打开图片，如图（11）； 10、用“橡皮”工具擦掉图形中多余的部分，如图（12）； 11、用“铅笔”工具添加直角符号，并用“铅笔”工具将部分实线改成虚线，如图（13）； 12、用“画图”程序中的文本工具给图形各点添加大写字母，如图（14）； 13、剪切图片，另存到文件夹，如图（15）； VB程序设计的常用算法 算法（Algorithm）：计算机解题的基本思想方法和步骤。算法的描述：是对要解决一个问题或要完成一项任务所采取的方法和步骤的描述，包括需要什么数据（输入什么数据、输出什么结果）、采用什么结构、使用什么语句以及如何安排这些语句等。通常使用自然语言、结构化流程图、伪代码等来描述算法。 一、计数、求和、求阶乘等简单算法 此类问题都要使用循环，要注意根据问题确定循环变量的初值、终值或结束条件，更要注意用来表示计数、和、阶乘的变量的初值。 例：用随机函数产生100个[0，99]范围内的随机整数，统计个位上的数字分别为1，2，3，4，5，6，7，8，9，0的数的个数并打印出来。 本题使用数组来处理，用数组a(1 to 100)存放产生的确100个随机整数，数组x(1 to 10)来存放个位上的数字分别为1，2，3，4，5，6，7，8，9，0的数的个数。即个位是1的个数存放在x(1)中，个位是2的个数存放在x(2)中，……个位是0的个数存放在x(10)。 将程序编写在一个GetTJput过程中，代码如下： Public Sub GetTJput() Dim a(1 To 100) As Integer Dim x(1 To 10) As Integer Dim i As Integer, p As Integer '产生100个[0，99]范围内的随机整数，每行10个打印出来 For i = 1 To 100 a(i) = Int(Rnd * 100) If a(i) < 10 Then Form1.Print Space(2); a(i); Else Form1.Print Space(1); a(i); End If If i Mod 10 = 0 Then Form1.Print Next i '统计个位上的数字分别为1，2，3，4，5，6，7，8，9，0的数的个数，并将统计结果保存在数组x(1),x(2),...,x(10)中，将统计结果打印出来 For i = 1 To 100 p = a(i) Mod 10 ' 求个位上的数字 If p = 0 Then p = 10 x(p) = x(p) + 1 Next i Form1.Print "统计结果" For i = 1 To 10 p = i If i = 10 Then p = 0 Form1.Print "个位数为" + Str(p) + "共" + Str(x(i)) + "个" Next i End Sub 二、求两个整数的最大公约数、最小公倍数 分析：求最大公约数的算法思想：(最小公倍数=两个整数之积/最大公约数) (1) 对于已知两数m，n，使得m>n； (2) m除以n得余数r； (3) 若r=0，则n为求得的最大公约数，算法结束；否则执行(4)； (4) m←n，n←r，再重复执行(2)。 例如:求m=14 ,n=6的最大公约数. m n r 单片机常用的14个C语言算法，看过的都成了大神！ 算法（Algorithm）：计算机解题的基本思想方法和步骤。算法的描述：是对要解决一个问题或要完成一项任务所采取的方法和步骤的描述，包括需要什么数据（输入什么数据、输出什么结果）、采用什么结构、使用什么语句以及如何安排这些语句等。通常使用自然语言、结构化流程图、伪代码等来描述算法。一、计数、求和、求阶乘等简单算法此类问题都要使用循环，要注意根据问题确定循环变量的初值、终值或结束条件，更要注意用来表示计数、和、阶乘的变量的初值。例：用随机函数产生100个[0，99]范围内的随机整数，统计个位上的数字分别为1，2，3，4，5，6，7，8，9，0的数的个数并打印出来。本题使用数组来处理，用数组a[100]存放产生的确100个随机整数，数组x[10]来存放个位上的数字分别为1，2，3，4，5，6，7，8，9，0的数的个数。即个位是1的个数存放在x[1]中，个位是2的个数存放在x[2]中，……个位是0的个数存放在x[10]。 void main(){int a[101],x[11],i,p;for(i=0;in； (2) m除以n得余数r； (3) 若r=0，则n为求得的最大公约数，算法结束；否则执行(4)； (4) m←n，n←r，再重复执行(2)。例如: 求m="14" ,n=6 的最大公约数. m n r 14 6 2 6 2 0 void main() { int nm,r,n,m,t; printf("please input two numbers:\n"); scanf("%d,%d", nm=n*m; if (m{ t="n"; n="m"; m="t"; } r=m%n; while (r!=0) { m="n"; n="r"; r="m"%n; } printf("最大公约数:%d\n",n); printf("最小公倍数:%d\n",nm/n); } 三、判断素数只能被1或本身整除的数称为素数基本思想：把m作为被除数，将2—INT（）作为除数，如果都除不尽，m就是素数，否则就不是。（可用以下程序段实现） void main() { int m,i,k; printf("please input a number:\n"); scanf("%d", k=sqrt(m); for(i=2;iif(m%i==0) break; if(i>=k) printf("该数是素数"); else printf("该数不是素数"); } 将其写成一函数,若为素数返回1，不是则返回0 int prime( m%) {int i,k; k=sqrt(m); for(i=2;iif(m%i==0) return 0; return 1; } 四、验证哥德巴赫猜想（任意一个大于等于6的偶数都可以分解为两个素数之和）基本思想：n为大于等于6的任一偶数，可分解为n1和n2两个数，分别检查n1和n2是否为素数，如都是，则为一组解。如n1不是素数，就不必再检查n2是否素数。先从n1=3开始，检验n1和n2（n2=N-n1） 计算几何算法概览 [ 2001-03-23 ] 怒火之袍出处:放飞技术网 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。 一、引言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。 二、目录 本文整理的计算几何基本概念和常用算法包括如下内容： 1.矢量的概念 2.矢量加减法 3.矢量叉积 4.折线段的拐向判断 5.判断点是否在线段上 6.判断两线段是否相交 7.判断线段和直线是否相交 8.判断矩形是否包含点 9.判断线段、折线、多边形是否在矩形中 10.判断矩形是否在矩形中 11.判断圆是否在矩形中 12.判断点是否在多边形中 13.判断线段是否在多边形内 14.判断折线是否在多边形内 15.判断多边形是否在多边形内 16.判断矩形是否在多边形内 17.判断圆是否在多边形内 18.判断点是否在圆内 19.判断线段、折线、矩形、多边形是否在圆内 20.判断圆是否在圆内 五大常用算法之一：分治算法 分治算法 一、基本概念 在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)…… 任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。 二、基本思想及策略 分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。 如果原问题可分割成k个子问题，1 平面上有n个点，给定n个点的坐标，试找一个半径最小的圆，将n 个点全部包围，点可以在圆上。 1. 在点集中任取3点A,B,C。 2. 作一个包含A,B,C三点的最小圆,圆周可能通过这3点，也可能只通过其中两点,但包含第3点.后一种情况圆周上的两点一定是位于圆的一条直径的两端。 3. 在点集中找出距离第2步所建圆圆心最远的D点，若D点已在圆内或圆周上，则该圆即为所求的圆，算法结束.则，执行第4步。 4. 在A,B,C,D中选3个点,使由它们生成的一个包含这4个点的圆为最小，这3 点成为新的A,B,C，返回执行第2步。若在第4步生成的圆的圆周只通过A,B,C,D 中的两点，则圆周上的两点取成新的A 和B,从另两点中任取一点作为新的C。 程序设计题解上的解题报告： 对于一个给定的点集A，记MinCircle(A)为点集A的最小外接圆，显然，对于所有的点集情况A,MinCircle(A)都是存在且惟一的。需要特别说明的是，当A为空集时，MinCircle(A)为空集，当A={a}时，MinCircle(A)圆心坐标为a，半径为0；显然，MinCircle(A)可以有A 边界上最多三个点确定(当点集A中点的个数大于1时，有可能两个点确定了MinCircle(A))，也就是说存在着一个点集B，|B|<=3 且B 包含与A，有MinCircle(B)=MinCircle(A).所以，如果a不属于B，则MinCircle(A-{a})=MinCircle(A);如果MinCircle(A-{a})不等于 MinCircle(A),则a属于B。所以我们可以从一个空集R开始，不断的把题目中给定的点集中的点加入R，同时维护R的外接圆最小，这样就可以得到解决该题的算法。 不断添加圆，维护最小圆。如果添加的点i在圆内，不动，否则： 问题转化为求1~I的最小圆：求出1与I的最小圆，并且扫描j=2~I-1，维护（1）+（i）+(2~j)的最小圆，如果找到J不在最小圆内，问题转化为：求(1~J)+(i)的最小圆。求出I与J的最小圆，继续扫描K=1~j-1,找到第一个不在最小圆内的，求出I J K三者交点即可，此时找到了(1~j)+(i)的最小圆，可以回到上一步（三点定一圆，所以1~J-1一定都在求出的最小圆上）。 实际上利用了这么个定理： 若I不在1~I-1的最小圆上，则I在1~I的最小圆上。 若J不在(i)+(1~j-1)的最小圆上，则j在(i)+(1~J)的最小圆上。 证明可以考虑这么做：最小圆必定是可以通过不断放大半径，直到所有以任意点为圆心，半径为半径的圆存在交点，此时的半径就是最小圆。所以上述定理可以通过这个思想得到。 这个做法复杂度是O(n)的，当加入圆的顺序随机时，因为三点定一圆，所以不在圆内概率是3/i,求出期望可得是On. 常用算法 要使计算机能完成人们预定的工作，首先必须为如何完成预定的工作设计一个算法，然后再根据算法编写程序。计算机程序要对问题的每个对象和处理规则给出正确详尽的描述，其中程序的数据结构和变量用来描述问题的对象，程序结构、函数和语句用来描述问题的算法。算法数据结构是程序的两个重要方面。 算法是问题求解过程的精确描述，一个算法由有限条可完全机械地执行的、有确定结果的指令组成。指令正确地描述了要完成的任务和它们被执行的顺序。计算机按算法指令所描述的顺序执行算法的指令能在有限的步骤内终止，或终止于给出问题的解，或终止于指出问题对此输入数据无解。 通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性，简单性和易理解性。其次是算法所需要的存储空间少和执行更快等。 算法设计是一件非常困难的工作，经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外，为了更简洁的形式设计和藐视算法，在算法设计时又常常采用递归技术，用递归描述算法。 一、迭代法 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行： （1）选一个方程的近似根，赋给变量x0； （2）将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0； （3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为： 【算法】迭代法求方程的根 { x0=初始近似根； do { x1=x0； x0=g(x1)；/*按特定的方程计算新的近似根*/ 计算几何算法概览 一、引言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。 二、目录 本文整理的计算几何基本概念和常用算法包括如下内容： 矢量的概念 矢量加减法 矢量叉积 折线段的拐向判断 判断点是否在线段上 判断两线段是否相交 判断线段和直线是否相交 判断矩形是否包含点 判断线段、折线、多边形是否在矩形中 判断矩形是否在矩形中 判断圆是否在矩形中 判断点是否在多边形中 判断线段是否在多边形内 判断折线是否在多边形内 判断多边形是否在多边形内 判断矩形是否在多边形内 判断圆是否在多边形内 判断点是否在圆内 判断线段、折线、矩形、多边形是否在圆内判断圆是否在圆内 计算点到线段的最近点 计算点到折线、矩形、多边形的最近点 计算点到圆的最近距离及交点坐标 计算两条共线的线段的交点 计算线段或直线与线段的交点 求线段或直线与折线、矩形、多边形的交点 求线段或直线与圆的交点 凸包的概念 凸包的求法 三、算法介绍 矢量的概念： 如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点，我们可以把它称为矢量(vector)p2。 矢量加减法： 设二维矢量P = ( x1, y1 )，Q = ( x2 , y2 )，则矢量加法定义为：P + Q = ( x1 + x2 , y1 + y2 )，同样的，矢量减法定义为：P - Q = ( x1 - x2 , y1 - y2 )。显然有性质 六种常用算法 有条不紊——递推法破解难题 问：“我对数据结构有了一定了解，但还是不太懂程序。从经典公式“程序=算法+数据结构”得知，是因为不了解算法。能不能介绍几种简单的算法，当然从最容易懂的那种开始了？”答：“算法就是能够证明正确的解题步骤，算法有许多种，最简单的无非下面的六种：递推法、贪心法、列举法、递归法、分治法和模拟法。刚听名字挺吓人的，其实有好多程序我们平常都见过。这些算法当中，最最简单的莫过于递推算法了。下面举例说明。” 什么是递推法 递推法这种解题方法其实在我们编程的过程中用的很多，只不过没有将其上升到理论的高度罢了。所谓递推法，就是找出和时间先后相联系或和数的大小相联系的步骤，上一步和下一步和数字的增大或减小有一定的联系。我们要么从前向后（或从小到大）推导，也可从后向前（或从大到小）推导。由此得出两种推导方法：顺推法和倒推法。请看下面的示例。 示例：猴子分食桃子 五只猴子采得一堆桃子，猴子彼此约定隔天早起后再分食。不过，就在半夜里，一只猴子偷偷起来，把桃子均分成五堆后，发现还多一个，它吃掉这桃子，并拿走了其中一堆。第二只猴子醒来，又把桃子均分成五堆后，还是多了一个，它也吃掉这个桃子，并拿走了其中一堆。第三只，第四只，第五只猴子都依次如此分食桃子。那么桃子数最少应该有几个呢？ 编程简析 怎样编程呢？先要找一下第N只猴子和其面前桃子数的关系。如果从第1只开始往第5只找，不好找，但如果思路一变，从第N到第1去，可得出下面的推导式： 第N只猴第N只猴前桃子数目 5 s5=x 4 s4=s5*5/4+1 3 s3=s4*5/4+1 2 s2=s3*5/4+1 1 s1=s2*5/4+1 s1即为所求。上面的规律中只要将s1-s5的下标去掉： s=x s=s*5/4+1 s=s*5/4+1 s=s*5/4+1 s=s*5/4+1 所以可以用循环语句加以解决。 综观程序的整体结构，最外是一个循环，因为循环次数不定，可以使用While循环，其结束条件则是找到第一个符合条件的数。为了做出上面while循环的结束条件，还需进一步分析上述规律的特点，要符合题目中的要求，s1-s4四个数必须全部为整数，这个可作为条件。具体实现请参看源程序。 语言、界面、源程序 （1）语言 计算几何常用算法概览 本站原创：怒火之袍一、引言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。 二、目录 本文整理的计算几何基本概念和常用算法包括如下内容： 矢量的概念 三、算法介绍 矢量的概念： 如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点，我们可以把它称为矢量(vector)p2。 矢量加减法： 设二维矢量P = ( x1,y1 ) ，Q = ( x2 , y2 ) ，则矢量加法定义为：P + Q = ( x1 + x2 , y1 + y2 )，同样的，矢量减法定义为：P - Q = ( x1 - x2 , y1 - y2 )。显然有性质P + Q = Q + P , P - Q = - ( Q - P )。 矢量叉积： 计算矢量叉积是与直线和线段相关算法的核心部分。设矢量P = （x1,y1），Q = (x2,y2)，则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面积，即：P ×Q = x1*y2 - x2*y1，其结果是一个标量。显然有性质P ×Q = - ( Q ×P ) 和P ×( - Q ) = - ( P ×Q )。一般在不加说明的情况下，本文下述算法中所有的点都看作矢量，两点的加减法就是矢量相加减，而点的乘法则看作矢量叉积。 叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的 顺逆时针关系： 若P ×Q > 0 , 则P在Q的顺时针方向。 若P ×Q < 0 , 则P在Q的逆时针方向。 若P ×Q = 0 , 则P与Q共线，但可能同向也可能反向。 《计算机常用算法与程序设计案例教程》 习题解答提要 习题1 1-1 分数分解算法描述 把真分数a/b 分解为若干个分母为整数分子为“1”的埃及分数之和： （1） 寻找并输出小于a/b 的最大埃及分数1/c ； （2） 若c>900000000，则退出； （3） 若c ≤900000000，把差a/b-1/c 整理为分数a/b ，若a/b 为埃及分数，则输出后结束。 （4） 若a/b 不为埃及分数，则继续（1）、（2）、（3）。 试描述以上算法。 解：设)(int a b d = (这里int(x)表示取正数x 的整数)，注意到1+< if(c>900000000) return; else { print(1/c+); a=a*c-b; b=b*c; // a,b迭代，为选择下一个分母作准备 if(a==1) { print(1/b);return;} } } 1-2 求出以下程序段所代表算法的时间复杂度 （1）m=0; for(k=1;k<=n;k++) for(j=k;j>=1;j--) m=m+j; 解：因s=1+2+…+n=n(n+1)/2 时间复杂度为O(n2)。 （2）m=0; for(k=1;k<=n;k++) for(j=1;j<=k/2;j++) m=m+j; 解：设n=2u+1，语句m=m+1的执行频数为 s=1+1+2+2+3+3+…+u+u=u(u+1)=(n?1)(n+1)/4 设n=2u，语句m=m+1的执行频数为 s=1+1+2+2+3+3+…+u=u2=n2/4 时间复杂度为O(n2)。 （3）t=1;m=0; for(k=1;k<=n;k++) {t=t*k; for(j=1;j<=k*t;j++) m=m+j; } 解：因s=1+2×2!+ 3×3!+…+ n×n!=(n+1)!?1 时间复杂度为O((n+1)!). （4）for(a=1;a<=n;a++) 目录 ㈠点的基本运算 1. 平面上两点之间距离 1 2. 判断两点是否重合 1 3. 矢量叉乘 1 4. 矢量点乘 2 5. 判断点是否在线段上 2 6. 求一点饶某点旋转后的坐标 2 7. 求矢量夹角 2 ㈡线段及直线的基本运算 1. 点与线段的关系 3 2. 求点到线段所在直线垂线的垂足 4 3. 点到线段的最近点 4 4. 点到线段所在直线的距离 4 5. 点到折线集的最近距离 4 6. 判断圆是否在多边形内 5 7. 求矢量夹角余弦 5 8. 求线段之间的夹角 5 9. 判断线段是否相交 6 10.判断线段是否相交但不交在端点处 6 11.求线段所在直线的方程 6 12.求直线的斜率 7 13.求直线的倾斜角 7 14.求点关于某直线的对称点 7 15.判断两条直线是否相交及求直线交点 7 16.判断线段是否相交，如果相交返回交点 7 ㈢多边形常用算法模块 1. 判断多边形是否简单多边形 8 2. 检查多边形顶点的凸凹性 9 3. 判断多边形是否凸多边形 9 4. 求多边形面积 9 5. 判断多边形顶点的排列方向，方法一 10 6. 判断多边形顶点的排列方向，方法二 10 7. 射线法判断点是否在多边形内 10 8. 判断点是否在凸多边形内 11 9. 寻找点集的graham算法 12 10.寻找点集凸包的卷包裹法 13 11.判断线段是否在多边形内 14 12.求简单多边形的重心 15 13.求凸多边形的重心 17 14.求肯定在给定多边形内的一个点 17 15.求从多边形外一点出发到该多边形的切线 18 16.判断多边形的核是否存在 19 ㈣圆的基本运算 1 .点是否在圆内 20 2 .求不共线的三点所确定的圆 21 ㈤矩形的基本运算 1.已知矩形三点坐标，求第4点坐标 22 ㈥常用算法的描述 22 ㈦补充 1．两圆关系： 24 2．判断圆是否在矩形内： 24 3．点到平面的距离： 25 4．点是否在直线同侧： 25 5．镜面反射线： 25 6．矩形包含： 26 7．两圆交点： 27 8．两圆公共面积： 28 9. 圆和直线关系： 29 10. 内切圆： 30 11. 求切点： 31 12. 线段的左右旋： 31 13．公式： 32 代码: /* 需要包含的头文件 */ #include 计算几何基础知识整理
ACM经典算法及配套练习题
计算机编程及常用术语大全(英汉对照)
GIS算法的计算几何基础
计算机常见算法面试题
计算几何算法的实现
平面几何图形的画法
VB程序设计的常用算法
单片机常用的14个C语言算法,看过的都成了大神!
计算几何算法概览.
五大常用算法
ACM 计算几何 最小圆覆盖算法
计算机编程常用算法
计算几何算法概览叉积
6种常用算法
计算几何常用算法概览
《计算机常用算法及程序设计案例教程》习题解答
计算几何常用函数
相关主题
文本预览