数论算法及计算几几何算法.ppt

第八章数论算法及计算几何算法 教学目标 理解求最大公约数的算法 掌握欧几里德公式的推广 掌握求解同余方程的算法 掌握运用中国剩余定理解决实际问题 理解线段相交的概念 掌握线段是否相交的判定算法 理解凸包的概念及穷举搜索的解决方法 掌握凸包问题及最接近点对问题的分治法 8.1最大公约数 定义1设a,b是整数,b0,如果存在整数c,使得 a=bc成立.则称a被b整除,a是b的倍数,b是a的 约数因数