ACM全部算法

ACM大赛算法 目录 一、数学问题.............................................................. 4 1.精度计算——大数阶乘.................................................. 4 2.精度计算——乘法（大数乘小数）........................................ 4 3.精度计算——乘法（大数乘大数）........................................ 5 4.精度计算——加法...................................................... 6 5.精度计算——减法...................................................... 7 6.任意进制转换.......................................................... 8 7.最大公约数、最小公倍数................................................ 9 8.组合序列............................................................. 10 9.快速傅立叶变换（FFT）................................................ 10 10.Ronberg 算法计算积分................................................. 12 11.行列式计算.......................................................... 14 12.求排列组合数........................................................ 15 13.求某一天星期几...................................................... 15 14.卡特兰(Catalan) 数列原理............................................ 16 15.杨辉三角............................................................ 16 16.全排列.............................................................. 17 17.匈牙利算法----最大匹配问题............................................ 18 18.最佳匹配KM 算法.................................................... 20 二、字符串处理........................................................... 22 1.字符串替换........................................................... 22 2.字符串查找........................................................... 23 3.字符串截取........................................................... 24 4.LCS-最大公共子串长度................................................. 24 5.LCS-最大公共子串长度................................................. 25 6.数字转换为字符....................................................... 26 三、计算几何............................................................. 27 我也可以做到.. 2 / 78 1.叉乘法求任意多边形面积............................................... 27 2.求三角形面积......................................................... 27 3.两矢量间角度......................................................... 28 4.两点距离（2D、3D）...................................................28 5.射向法判断点是否在多边形内部......................................... 29 6.判断点是否在线段上................................................... 30 7.判断两线段是否相交................................................... 31 8.判断线段与直线是否相交............................................... 32 9.点到线段最短距离..................................................... 32 10.求两直线的交点...................................................... 33 11.判断一个封闭图形是凹集还是凸集...................................... 34 12.Graham 扫描法寻找凸包............................................... 35 13.求两条线段的交点.................................................... 36 四、数论................................................................. 37 1.x 的二进制长度........................................................ 37 2.返回x 的二进制表示中从低到高的第i 位.................................. 38 3.模取幂运算........................................................... 38 4.求解模线性方程....................................................... 39 5.求解模线性方程组(中国余数定理)........................................ 39 6.筛法素数产生器....................................................... 40 7.判断一个数是否素数................................................... 41 8.求距阵最大和......................................................... 42 8.求一个数每一位相加之和............................................... 43 10.质因数分解.......................................................... 43 11.高斯消元法解线性方程组.............................................. 44 五、图论................................................................. 45 1.Prim 算法求最小生成树................................................. 45 2.Dijkstra 算法求单源最短路径............................................ 46 3.Bellman-ford 算法求单源最短路径........................................ 47 4.Floyd-Warshall 算法求每对节点间最短路径................................ 48 我也可以做到.. 3 / 78 5.解欧拉图............................................................. 49 六、排序/查找............................................................ 50 1.快速排序............................................................. 50 2.希尔排序............................................................. 51 3.选择法排序........................................................... 52 4.二分查找............................................................. 52 七、数据结构............................................................. 53 1.顺序队列............................................................. 53 2.顺序栈............................................................... 56 3.链表................................................................. 59 4.链栈................................................................. 63 5.二叉树............................................................... 66 八、高精度运算专题....................................................... 68 1.专题函数说明......................................................... 68 2.高精度数比较......................................................... 69 3.高精度数加法......................................................... 69 4.高精度数减法......................................................... 70 5.高精度乘10........................................................... 71 6.高精度乘单精度....................................................... 71 7.高精度乘高精度....................................................... 72 8.高精度除单精度....................................................... 72 9.高精度除高精度....................................................... 73 九、标准模板库的使用..................................................... 74 1.计算求和............................................................. 74 2.求数组中的最大值..................................................... 76 3. sort 和qsort........................................................... 76 九、其他................................................................. 78 1.运行时间计算.......................................................... 78 我也可以做到.. 5.精度计算——减法...................................................... 7 6.任意进制转换.......................................................... 8 7.最大公约数、最小公倍数................................................ 9 8.组合序列............................................................. 10 9.快速傅立叶变换（FFT）................................................ 10 10.Ronberg 算法计算积分................................................. 12 11.行列式计算.......................................................... 14 12.求排列组合数........................................................ 15 13.求某一天星期几...................................................... 15 14.卡特兰(Catalan) 数列原理............................................ 16 15.杨辉三角............................................................ 16 16.全排列.............................................................. 17 17.匈牙利算法----最大匹配问题............................................ 18 18.最佳匹配KM 算法.................................................... 20 二、字符串处理........................................................... 22 1.字符串替换........................................................... 22 2.字符串查找........................................................... 23 3.字符串截取........................................................... 24 4.LCS-最大公共子串长度................................................. 24 5.LCS-最大公共子串长度................................................. 25 6.数字转换为字符....................................................... 26 三、计算几何............................................................. 27 我也可以做到.. 2 / 78 1.叉乘法求任意多边形面积............................................... 27 2.求三角形面积......................................................... 27 3.两矢量间角度......................................................... 28 4.两点距离（2D、3D）...................................................28 5.射向法判断点是否在多边形内部......................................... 29 6.判断点是否在线段上................................................... 30 7.判断两线段是否相交................................................... 31 8.判断线段与直线是否相交............................................... 32 9.点到线段最短距离..................................................... 32 10.求两直线的交点...................................................... 33 11.判断一个封闭图形是凹集还是凸集...................................... 34 12.Graham 扫描法寻找凸包............................................... 35 13.求两条线段的交点.................................................... 36 四、数论................................................................. 37 1.x 的二进制长度........................................................ 37 2.返回x 的二进制表示中从低到高的第i 位.................................. 38 3.模取幂运算........................................................... 38 4.求解模线性方程....................................................... 39 5.求解模线性方程组(中国余数定理)........................................ 39 6.筛法素数产生器....................................................... 40 7.判断一个数是否素数................................................... 41 8.求距阵最大和......................................................... 42 8.求一个数每一位相加之和............................................... 43 10.质因数分解.......................................................... 43 11.高斯消元法解线性方程组.............................................. 44 五、图论................................................................. 45 1.Prim 算法求最小生成树................................................. 45 2.Dijkstra 算法求单源最短路径............................................ 46 3.Bellman-ford 算法求单源最短路径........................................ 47 4.Floyd-Warshall 算法求每对节点间最短路径................................ 48 我也可以做到.. 3 / 78 5.解欧拉图............................................................. 49 六、排序/查找............................................................ 50 1.快速排序............................................................. 50 2.希尔排序............................................................. 51 3.选择法排序........................................................... 52 4.二分查找............................................................. 52 七、数据结构............................................................. 53 1.顺序队列............................................................. 53 2.顺序栈............................................................... 56 3.链表................................................................. 59 4.链栈................................................................. 63 5.二叉树............................................................... 66 八、高精度运算专题....................................................... 68 1.专题函数说明......................................................... 68 2.高精度数比较......................................................... 69 3.高精度数加法......................................................... 69 4.高精度数减法......................................................... 70 5.高精度乘10........................................................... 71 6.高精度乘单精度....................................................... 71 7.高精度乘高精度....................................................... 72 8.高精度除单精度....................................................... 72 9.高精度除高精度....................................................... 73 九、标准模板库的使用..................................................... 74 1.计算求和............................................................. 74 2.求数组中的最大值..................................................... 76 3. sort 和qsort........................................................... 76 九、其他................................................................. 78 1.运行时间计算.......................................................... 78 我也可以做到..