第八章 数论算法及计算几何算法 243







步骤2:递归地在S1中找出其最接近点对(pi,pj),距离为d1; 步骤3:递归地在S2中找出其最接近点对(qi,qj),距离为d2; 步骤4: 取d=min{d1,d2};
步骤5:求S1中的最大值xp;求S2中的最小值xq; 步骤6:计算d3= xq -xp;
步骤7:取min{d,d3}且记录最接近点对的坐标,即求得S中的最接近点对。 (3)算法描述
bool CPAIR1(POINT S[], double &d,double &p,double &q) {
double p1,p2,q1,q2,p3,q3;//用来记录三种情况的最接近点对 n=|S|; if (n<2)
{d= ;return false;} else if(n==2)
{
d=|x[2]-x[1]| ;// x[1..n]存放的是S中n个点的坐标 p=x[2];q=x[1];
return true;
}
m=S中各点的横坐标值的中位数; 构造S1和S2; CPAIR1(S1,d1,p1,p2); CPAIR1(S2,d2,q1,q2); p3=max(S1); q3=min(S2); double d3=q3-p3; if(d1<=d2 && d1<=d3) {d=d1;p=p1;q=p2;} if(d1<d2)
{ d=d2;p=q1;q=q2;} else
{ d=d3;p=p3;q=q3;} return true; }
(4)算法分析
假设用T(n)表示从n个点中找出最接近点对所耗的时间,则每个子问题所耗的时间为T(n/2);找出中位数可以在线性时间O(n)实现;合并子问题的解所耗时间为线性时间O(n),故一维情形下时间的递归表达式为:
第8章 数论算法及计算几何算法_数学_自然科学_专业资料。数论算法及计算几何算法,凸包问题及最接近点对问题的分治法第八章 数论算法及计算几何算法 教学目标 ? ...
第8章 数论算法及计算几何算法_数学_自然科学_专业资料。第八章 数论算法及计算几何算法 教学目标 ? 理解求最大公约数的算法 ? 掌握欧几里德公式的推广 ? ...
第八章 数论算法及计算几何算法 8.5 凸包问题 1、问题提出 ? 给定一个点集S={P0,P1,…,Pn-1},它的凸包是一 个最小的凸多边形P,且满足S中的每个点...
数论和计算几何_数学_自然科学_专业资料。pascal数论和计算几何数论和计算几何 ... 第八章 数论算法及计算几... 28页 免费 数论计算 引言 57页 免费 计算与...
第八章 数论算法及计算几... 28页 免费 奥数几何,数论,行程专题 8页 7...快速幂是用来快速计算a^n mod p的一种方 法。 如果n是偶数则a^n=a^(n/...
离散数学--11.1-2初等数论 24页 免费 数论-第八章 14页 1财富值 108第八章数论及其猜想的意... 41页 1财富值 第八章 数论算法及计算几何... 暂无...
第八章 数论算法及计算几何... 第九章 NP完全理论1/2 相关文档推荐 第2章 贪心法 56页 5财富值 第2章 贪心法 暂无评价 42页 1财富值 第2章 贪心法 ...
[编辑本段] 算法分类 算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论 的算法、动态规划以及数值分析、加密算法、排序算法、检索...
三角形几何运算 7页 免费 第8章 数论算法及计算几何... 暂无评价 32页 免费 CAGD第八章曲线的几何处理... 5页 5财富值 计算几何 67页 免费喜欢此文档的...
224 第八章 数论算法及计算几何算法 ... 226 8.1 最大公约数......
热门文档