河南大学_ACM常用算法模板解剖.doc

目录 一、数学问题 4 1. 精度计算——大数阶乘 4 2.精度计算——乘法（大数乘小数） 4 3.精度计算——乘法（大数乘大数） 5 4.精度计算——加法 6 5.精度计算——减法 7 6.精度计算——除法约分 8 7.任意进制转换 11 8.最大公约数、最小公倍数 11 9.组合序列 12 10.Ronberg算法计算积分 14 11.行列式计算 14 12.求排列组合数 15 二、计算几何 15 1.叉乘法求任意多边形面积 15 2.求三角形面积 16 3.求多边形重心 17 4.两矢量间角度 17 5.两点距离（2D、3D） 18 6.射向法判断点是否在多边形内部 18 7.判断点是否在线段上 19 8.判断两线段是否相交 20 9.判断线段与直线是否相交 21 10.点到线段最短距离 21 11.求两直线的交点 22 12.判断一个封闭图形是凹集还是凸集 23 13.Graham扫描法寻找凸包 24 三、数论 27 1.x的二进制长度 27 2.返回x的二进制表示中从低到高的第i位 27 3.模取幂运算（反复平方法求数的幂） 27 4.求解模线性方程 29 5.求解模线性方程组(中国余数定理) 29 6.筛法素数产生器 31 7.判断一个数是否素数 32 8.初等数论里的欧拉公式： 32 9.数的分解 35 10.关于数的阶乘 36 11.母函数 37 12.特殊的数 39 13. 组合公式 40 14. 置换群与Pólya定理 40 四、图论 43 1. 深度优先有哪些信誉好的足球投注网站 43 2. 边分类算法 45 3. 连通性 45 4. Kosaraju算法求强连通分支 46 5. 无向图的割顶和桥 50 6. 欧拉图 52 1）消圈法（逐步插入回路法） 53 2）Fleury算法（能不走桥就不走桥）： 55 7.最小生成树 60 1).Prim算法（邻接矩阵，无优化）: 60 2).Prim算法（邻接表+Heap优先队列优化）: 61 3) Kruskal算法： 65 8.Dijkstra算法求单源最短路径 67 1）.邻接矩阵，无优化 67 2）.邻接链表，用优先队列（STL）优化 70 9.Bellman-ford算法求单源最短路径 72 10.Floyd-Warshall算法求每对节点间最短路径 74 五、最大流 75 1．最大流算法（Ford-Fulkerson） 75 2．最大二分匹配（最大流算法） 76 3．最大二分匹配（匈牙利算法） 78 4．最佳二分匹配（KM算法） 79 5．最小路径覆盖（最大流算法） 83 6．最小路径覆盖（匈牙利算法） 85 7. 关于匹配 86 六、排序/查找 87 1.快速排序 87 2.希尔排序 88 3.选择法排序 88 4.二分查找 89 七．数据结构 90 1. 并查集 90 2. 串的匹配（KMP算法）: 95 3. 字典树（字符串的储存与查找）: 96 4. 二叉堆（用二叉堆排序及构建优先队列） 98 5. 二叉查找树（可作为优先队列） 100 6. 红黑树 104 7. 树状数组 111 1）.一维数组代码（子段和）： 112 2）.二维数组代码（子阵和）： 113 8. 线段树 114 9. 归并树 118 10. 后缀数组(Suffix Array) 121 八．博弈问题例题分析 124 例1.POJ1740 A New Stone Game 124 例2.MIPT100 Nim Game -- who is the winner? 125 例3.POJ1704 Georgia and Bob 126 例4.poj1067取石子游戏 126 例4的另种解法： 127 单堆博弈问题： 128 九．其它算法 129 1. LCS算法 129 2. 背包问题 130 3. 回溯法 133 4. RMQ问题的ST算法 134 5. 最近公共祖先（LCA）问题 136 1）.RMQ求法 137 2）.Tarjan的脱机（离线）算法 137 6. 扫描线 141 十．杂谈 144 1.国际象棋 144 2.STL常用结构简单用法 144 3.图的度序列 147 4.数学的转化 147 一、数学问题 1. 精度计算——大数阶乘 语法：int result=factorial(int n); 参数： n： n 的阶乘 返回值： 阶乘结果的位数 注意： 本程序直接输出n!的结果，需要返回结果请保留long a[] 需要 math.h 源程序： int factorial(int n) { long a[10000]; int i,j,l,c,m=0,w; a[0]=1; for(i=1;i=n;i++) { c=0; for(j=