这是一本具有启发性的很好的书，翻译的也还不错。
我们的实际生活中有很多的问题亟待解决，当问题很复杂的时候往往让人无从下手，这时候如果利用数学中的几何知识将之转化成为几何问题求解往往会出现出人意料的解决方案。
书中关于点的处理的部分有凸包、正交区域查找、点定位、voronoi图和delaunay三角剖分。
1、凸包：
1）平面凸包：计算平面上由n个点组成的有限集合P的凸包，利用“递增式算法”，逐一引入P中的各点，每增加一个点，观察多边形的外边界是向哪个方向改变，例如：对于点集的上凸包，当其多边形外边界向左转构成一个左拐时就删除当前引入的点。（这部分内容比较有用，待用到的时候再好好研究一下）
2）三维凸包：
选出三维点集中不共面的4个点，构成一个凸包四面体，然后将剩余的点随即加入，动态维护凸包。采用双向链接边表存储凸包。
2、正交区域查找
1）一维区域查找：采用平衡二分查找树从根节点开始，每向左前进一步，枚举出该处右子树中的所有叶子，同时每向右前进一步，枚举右该处左子树中的所有叶子，遍历整棵子树后，报告出所有叶子对应的点。
2）二维区域查找：
采用KD－树：先将点集沿x坐标方向划分，再沿y方向划分，再x方向，再y方向……直到达到给定的递归深度。
采用区域树：利用一维区域查找，先找出x坐标方向的区域内的所有点，对这些点再作y方向的一维区域查找。
3、点定位：
方法一：将包含n条线段的平面子区域划分为竖条带，先用二分查找找出待查点q所处的竖条带，然后在该竖条带所对应的数组重，再次进行二分查找，找出q下方紧挨着的那条线段。
方法二：梯形图，经过线段集中每条线段的每个端点，向上向下各作一条垂线构成梯形图。
4、voronoi图和delaunay三角剖分
二者互为对偶
文中提到构造delaunay三角剖分的准则来历。
书中提到的对偶概念也很有趣，尤其是抛物线的对偶有一些非常神奇的性质，因为和点无关，就在这里不提了
2023-03-17 21:54:14
7.5MB
1
汇总了计算机研究生复试有关算法分析与设计各章节简答题，使用了易于口头表达的语言进行了总结。包括算法分析与设计基本概念及各章节问题回答。可供研究生复试或相关专业岗位面试使用。
1. 简述算法定义、属性及指标；
2. 什么是算法分析，怎么做算法设计；
3. 什么是算法复杂性；
4. 枚举法算法的基本思想；
5. 枚举法算法解决的典型问题有哪些，举例说明算法处理过程？
6. 分治法算法的基本思想；
7. 分治法算法解决的典型问题有哪些，举例说明算法处理过程？
8. 动态规划算法的基本思想；
9. 动态规划算法解决的典型问题有哪些，举例说明算法处理过程？
10. 贪心算法的基本思想；
12. 分治法、贪心算法与动态规划算法的差异；
13. 回溯法的基本思想；
15. 分支限界法的基本思想；
17. 简述分支限界法与回溯法的不同点；
18. 基于分治法的排序算法有哪些？
2023-03-08 09:26:31
266KB
1
前言致学生既然你已经开始阅读本书，那么必定对计算机科学感兴趣。你可能也对Python这门编程语言感兴趣，并且已经通过之前的课程或自学有了一些编程经验。不论是何种
2023-01-30 09:16:03
10.42MB
1
算法分析 八枚硬币问题C语言源程序
在八枚外观相同的硬币中，有一枚是假的，并且已知假币与真币的重量不同，但不知道假币与真币相比较轻还是重。可以通过一架天平来任意比较两组硬币，设计一个高效的算法来检测出这枚假币
2023-01-20 21:35:17
2KB
1
这本书是王晓东老师《算法分析与设计》课后练习题的解题手册。涵盖了大量的实例和标准代码。绝对是初学者的首选用书。
2023-01-09 20:50:38
8.24MB
1
棋盘覆盖问题
void ChessBoard(int tr,int tc,int dr,int dc,int size)
{
if(size==1) return;
int t = tile++;
int s = size/2;
if(dr=tc+s)
{
ChessBoard(tr,tc+s,dr,dc,s);
}
else
{
Board[tr+s-1][tc+s] =t;
ChessBoard(tr,tc+s,tr+s-1,tc+s,s);
}
if(dr>=tr+s&&dc;=tr+s&&dc;>=tc+s)
ChessBoard(tr+s,tc+s,dr,dc,s);
else
{
Board[tr+s][tc+s] = t;
ChessBoard(tr+s,tc+s,tr+s,tc+s,s);
}
}
2023-01-06 18:12:40
1KB
1