ACM函数整理_ACM模板.doc

《ACM函数整理_ACM模板.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、目录一、数学问题41.精度计算——大数阶乘42.精度计算——乘法（大数乘小数）43.精度计算——乘法（大数乘大数）54.精度计算——加法65.精度计算——减法76.任意进制转换87.最大公约数、最小公倍数98.组合序列109.快速傅立叶变换（FFT）1010.Ronberg算法计算积分1211.行列式计算1412.求排列组合数1513.求某一天星期几1514.卡特兰(Catalan)数列原理1615.杨辉三角1616.全排列1717.匈牙利算法----最大匹配问题.1818.最佳匹配KM算法20二、字符串处理221.字符串替换222.字符串查找233.字符串截

2、取244.LCS-最大公共子串长度245.LCS-最大公共子串长度256.数字转换为字符26三、计算几何271.叉乘法求任意多边形面积272.求三角形面积273.两矢量间角度284.两点距离（2D、3D）285.射向法判断点是否在多边形内部296.判断点是否在线段上307.判断两线段是否相交318.判断线段与直线是否相交329.点到线段最短距离3210.求两直线的交点3311.判断一个封闭图形是凹集还是凸集3412.Graham扫描法寻找凸包3513.求两条线段的交点36四、数论371.x的二进制长度372.返回x的二进制表示中从低到高的第i位383.模取幂运

3、算384.求解模线性方程395.求解模线性方程组(中国余数定理)396.筛法素数产生器407.判断一个数是否素数418.求距阵最大和428.求一个数每一位相加之和4310.质因数分解4311.高斯消元法解线性方程组44五、图论451.Prim算法求最小生成树452.Dijkstra算法求单源最短路径463.Bellman-ford算法求单源最短路径474.Floyd-Warshall算法求每对节点间最短路径485.解欧拉图49六、排序/查找501.快速排序502.希尔排序513.选择法排序524.二分查找52七、数据结构531.顺序队列532.顺序栈563.链

4、表594.链栈635.二叉树66八、高精度运算专题681.专题函数说明682.高精度数比较693.高精度数加法694.高精度数减法705.高精度乘10716.高精度乘单精度717.高精度乘高精度728.高精度除单精度729.高精度除高精度73九、标准模板库的使用741.计算求和742.求数组中的最大值763.sort和qsort76九、其他781.运行时间计算.78一、数学问题1.精度计算——大数阶乘语法：intresult=factorial(intn);参数：n：n的阶乘返回值：阶乘结果的位数注意：本程序直接输出n!的结果，需要返回结果请保留longa[]

5、需要math.h源程序：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+log10(a[m])+1;printf("%ld",a[m]);for(i=m-1;i>=0;i--)printf("%4.4ld",a[i]);returnw;}2.精度计算——乘法（大数乘小数）语法

6、：mult(charc[],chart[],intm);参数：c[]：被乘数，用字符串表示，位数不限t[]：结果，用字符串表示m：乘数，限定10以内返回值：null注意：需要string.h源程序：voidmult(charc[],chart[],intm){inti,l,k,flag,add=0;chars[100];l=strlen(c);for(i=0;i=10){s[i]=k%10;add=k/10;flag=1;}else{s[i]

7、=k;flag=0;add=0;}}if(flag){l=i+1;s[i]=add;}elsel=i;for(i=0;i

8、en,blen,sum=0,res[6