《ascal经典算法》PPT课件

《《ascal经典算法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、经典算法语言与计算机递归调用向前引用随机化指针类型按位运算排序（一）冒泡排序（起泡排序）选择排序插入排序★Shell排序快速排序排序（二）线性时间排序查找第k大元素带第二关键字的排序数论（一）素性判断筛选建立素数表分解质因数进制转换二分取幂★二分求解线性递推方程数论（二）求最大公约数求最小公倍数★扩展的辗转相除★求解一元一次同余式★中国剩余定理★高斯消元四则运算表达式计算高精度加法高精度减法高精度乘法★高精度除法图论：最小生成树Prim算法Kruskal算法★Boruvka算法次小生成树图论：求最短路Dijkstr

2、a算法Bellman-Ford算法Floyd-Warshall算法次短路★差分约束系统图论：DFS遍历深度优先搜索欧拉回路求弱连通分量★求强连通分量★求割点★求桥图论：BFS遍历广度优先搜索（宽度优先搜索）求不带权的最短路求图的直径AOV问题（拓扑排序）AOE问题图论：二分图验证二分图匈牙利算法★KM算法★稳定婚姻系统树求树的最短链二叉树的四种遍历已知先序中序求后序已知中序后序求先序★已知先序后序求中序★LCA问题的Tarjan离线算法★Huffman编码数据结构（一）表和栈Hash表与开散列★分段Hash并查集堆

3、二叉查找树数据结构（二）★平衡二叉树★树状数组★线段树★块状链表排列与组合生成所有排列生成所有组合生成下一个排列生成下一个组合计算几何（一）计算斜率计算点积计算余弦计算平面两点的距离计算空间两点的距离★计算广义空间两点的距离判断三点是否共线计算几何（二）计算叉积判断两向量的左右关系判断两点是否在直线同侧判断两线段是否相交计算多边形面积计算点到直线的距离计算几何（三）★计算交点坐标★判断点是否在多边形内★半平面相交★求点集的凸包计算几何（四）计算带权中位数求多边形的重心判断点是否在圆内线段的延长离散化与扫描0-1背包

4、完全背包乘法问题数塔问题装箱问题动态规划（一）动态规划（二）最长上升序列（LIS）最长公共子串（LCM）最小代价子母树分治与递归二分查找归并排序最近点对问题求最大子序列和的O(nlogn)算法Hanoi塔问题及其变种棋盘覆盖问题循环赛日程表问题贪心最优装载问题部分背包问题独立区间的选择覆盖区间的选择区间的最小点覆盖点的最小区间覆盖递推Fibonacci数的若干应用Catalan数的若干应用拆分数差分序列其它★网络流★置换群★KMP算法