acm常用算法介绍及实用模板

《acm常用算法介绍及实用模板》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、2008河南大学河南大学ACM常用算法介绍及模板河南大学计算机与信息工程学院1472008河南大学目录一、数学问题41.精度计算——大数阶乘42.精度计算——乘法（大数乘小数）43.精度计算——乘法（大数乘大数）54.精度计算——加法65.精度计算——减法76.精度计算——除法约分87.任意进制转换118.最大公约数、最小公倍数119.组合序列1210.Ronberg算法计算积分1411.行列式计算1412.求排列组合数15二、计算几何151.叉乘法求任意多边形面积152.求三角形面积163.求多边形重心174.两矢量间角度175.两点距离（2D、3D）186.射向法判断点是否在多边

2、形内部187.判断点是否在线段上198.判断两线段是否相交209.判断线段与直线是否相交2110.点到线段最短距离2211.求两直线的交点2212.判断一个封闭图形是凹集还是凸集2313.Graham扫描法寻找凸包24三、数论271.x的二进制长度272.返回x的二进制表示中从低到高的第i位273.模取幂运算（反复平方法求数的幂）284.求解模线性方程295.求解模线性方程组(中国余数定理)306.筛法素数产生器317.判断一个数是否素数328.初等数论里的欧拉公式：329.数的分解3510.关于数的阶乘3611.母函数37四、图论391.深度优先搜索392.边分类算法4014720

3、08河南大学3.连通性414.Kosaraju算法求强连通分支425.无向图的割顶和桥456.欧拉图481）消圈法（逐步插入回路法）482）Fleury算法（能不走桥就不走桥）：517.最小生成树561).Prim算法（邻接矩阵，无优化）:562).Prim算法（邻接表+Heap优先队列优化）:573)Kruskal算法：618.Dijkstra算法求单源最短路径631）.邻接矩阵，无优化632）.邻接链表，用优先队列（STL）优化659.Bellman-ford算法求单源最短路径6810.Floyd-Warshall算法求每对节点间最短路径69五、最大流701．最大流算法（Ford

4、-Fulkerson）702．最大二分匹配（最大流算法）723．最大二分匹配（匈牙利算法）734．最佳二分匹配（KM算法）755．最小路径覆盖（最大流算法）786．最小路径覆盖（匈牙利算法）807.关于匹配82六、排序/查找821.快速排序822.希尔排序833.选择法排序844.二分查找84七．数据结构851.并查集852.串的匹配（KMP算法）:903.字典树（字符串的储存与查找）:914.二叉堆（用二叉堆排序及构建优先队列）935.二叉查找树（可作为优先队列）966.红黑树997.树状数组1071）.一维数组代码（子段和）：1072）.二维数组代码（子阵和）：1088.线段树1

5、109.归并树11310.后缀数组(SuffixArray)116八．博弈问题例题分析119例1.POJ1740ANewStoneGame120例2.MIPT100NimGame--whoisthewinner?1201472008河南大学例3.POJ1704GeorgiaandBob121例4.取石子游戏121例4的另种解法：122九．其它算法1231.LCS算法1232.背包问题1243.回溯法1274.RMQ问题的ST算法1295.最近公共祖先（LCA）问题1311）.RMQ求法1312）.Tarjan的脱机（离线）算法132十．杂谈1351.国际象棋1352.STL常用结构简

6、单用法1353.图的度序列1381472008河南大学一、数学问题1.精度计算——大数阶乘返回值：阶乘结果的位数注意：本程序直接输出n!的结果，需要返回结果请保留longa[]需要头文件：cmath源程序：intfactorial(intn){longa[10000];inti,j,l,c,m=0,w;a[0]=1;for(i=1;i<=n;i++){c=0;for(j=0;j<=m;j++){a[j]=a[j]*i+c;c=a[j]/10000;a[j]=a[j]%10000;}if(c>0){m++;a[m]=c;}}w=m*4+(int)log10((double)a[m])+

7、1;//阶乘的位数printf("%ld",a[m]);for(i=m-1;i>=0;i--)printf("%4.4ld",a[i]);printf("");returnw;}2.精度计算——乘法（大数乘大数）#include#includeusingnamespacestd;1472008河南大学stringmuling(strings1,strings2){stringcheng(s1.length()+s2