清华内部acm培训资料_各类经典算法

《清华内部acm培训资料_各类经典算法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、ACM小组内部预定函数   数学问题：   1.精度计算——大数阶乘2.精度计算——乘法（大数乘小数）3.精度计算——乘法（大数乘大数）4.精度计算——加法5.精度计算——减法6.任意进制转换7.最大公约数、最小公倍数8.组合序列9.快速傅立叶变换（FFT）10.Ronberg算法计算积分11.行列式计算12.求排列组合数    字符串处理：   1.字符串替换2.字符串查找3.字符串截取     计算几何：   1.叉乘法求任意多边形面积2.求三角形面积3.两矢量间角度4.两点距离（2D、3D）5.射向法判断点是否在多边

2、形内部6.判断点是否在线段上7.判断两线段是否相交8.判断线段与直线是否相交9.点到线段最短距离10.求两直线的交点11.判断一个封闭图形是凹集还是凸集12.Graham扫描法寻找凸包    数论：   1.x的二进制长度2.返回x的二进制表示中从低到高的第i位3.模取幂运算4.求解模线性方程5.求解模线性方程组(中国余数定理)6.筛法素数产生器7.判断一个数是否素数     图论：   1.Prim算法求最小生成树2.Dijkstra算法求单源最短路径3.Bellman-ford算法求单源最短路径4.Floyd算法求每对

3、节点间最短路径    排序/查找：   1.快速排序2.希尔排序3.选择法排序4.二分查找    数据结构：   1.顺序队列2.顺序栈3.链表4.链栈5.二叉树   一、数学问题1.精度计算——大数阶乘语法：intresult=factorial(intn);参数：n：n的阶乘返回值：阶乘结果的位数注意：  本程序直接输出n!的结果，需要返回结果请保留longa[] 需要math.h源程序：  intfactorial(intn){longa[10000];inti,j,l,c,m=0,w;a[0]=1;for(i=1;

4、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.精度计算——乘法（大数乘小数）语法：mult

5、(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

6、        k=s[i]*m+add;           if(k>=10){s[i]=k%10;add=k/10;flag=1;}else{s[i]=k;flag=0;add=0;}           }    if(flag){l=i+1;s[i]=add;}elsel=i;    for(i=0;i

7、数，用字符串表示，位数不限b[]：乘数，用字符串表示，位数不限t[]：结果，用字符串表示返回值：Null注意：  空间复杂度为o(n^2) 需要string.h源程序：  voidmult(chara[],charb[],chars[]){    inti,j,k=0,alen,blen,sum=0,res[65][65]={0},flag=0;    charresult[65];    alen=strlen(a);blen=strlen(b);    for(i=0;i

8、blen;j++)res[i][j]=(a[i]-'0')*(b[j]-'0');    for(i=alen-1;i>=0;i--)        {            for(j=blen-1;j>=0;j--)sum=sum+res[i+blen-j-1][j];            res