清华内部ACM培训资料,各类经典算法.docx

《清华内部ACM培训资料,各类经典算法.docx》由会员分享，可在线阅读，更多相关《清华内部ACM培训资料,各类经典算法.docx（55页珍藏版）》请在三一办公上搜索。

1、清华内部ACM培训资料,各类经典算法ACM小组内部预定函数 数学问题： 1.精度计算大数阶乘 4.精度计算加法 2.精度计算乘法 6.任意进制转换 数乘大数） 7.最大公约数、最小公倍数 5.精度计算减法 8.组合序列 12.求排列组合数 4.两点距离 8.判断线段与直线是否相交 12.Graham扫描法寻找凸包 4.求解模线性方程 9.快速傅立叶变换 10.Ronberg算法计算积分 11.行列式计算 字符串处理： 1.字符串替换 计算几何： 1.叉乘法求任意多边形面积 5.射向法判断点是否在多边形内部 9.点到线段最短距离 数论： 1.x的二进制长度 5.求解模线性方程组(中国余数定理)

2、图论： 1.Prim算法求最小生成树 排序/查找： 1.快速排序 数据结构： 2.字符串查找 2.求三角形面积 3.字符串截取 3.两矢量间角度 6.判断点是否在线段上 7.判断两线段是否相交 11.判断一个封闭图形是凹集还是凸集 3.模取幂运算 10.求两直线的交点 2.返回x的二进制表示中从低到高的第i位 6.筛法素数产生器 7.判断一个数是否素数 2.Dijkstra算法求单源最3.Bellman-ford算法求单4.Floyd算法求每对节点短路径 2.希尔排序 源最短路径 3.选择法排序 间最短路径 4.二分查找 1.顺序队列 5.二叉树 2.顺序栈 3.链表 4.链栈 一、数学问题

3、1.精度计算大数阶乘 语法：int result=factorial(int n); 参数： n： n 的阶乘 返回值： 阶乘结果的位数 注意： 本程序直接输出n!的结果，需要返回结果请保留long a 需要 math.h 源程序： int factorial(int n) long a10000; int i,j,l,c,m=0,w; a0=1; for(i=1;i=n;i+) c=0; for(j=0;j0) m+;am=c; w=m*4+log10(am)+1; printf(n%ld,am); for(i=m-1;i=0;i-) printf(%4.4ld,ai); return w;

4、 2.精度计算乘法 语法：mult(char c,char t,int m); 参数： c： 被乘数，用字符串表示，位数不限 t： 结果，用字符串表示 m： 乘数，限定10以内 返回值： null 注意： 需要 string.h 源程序： void mult(char c,char t,int m) int i,l,k,flag,add=0; char s100; l=strlen(c); for (i=0;il;i+) sl-i-1=ci-0; for (i=0;i=10) si=k%10;add=k/10;flag=1; else si=k;flag=0;add=0; if (flag)

5、l=i+1;si=add; else l=i; for (i=0;il;i+) tl-1-i=si+0; tl=0; 3.精度计算乘法 语法：mult(char a,char b,char s); 参数： a： 被乘数，用字符串表示，位数不限 b： 乘数，用字符串表示，位数不限 t： 结果，用字符串表示 返回值： null 注意： 空间复杂度为 o(n2) 需要 string.h 源程序： void mult(char a,char b,char s) int i,j,k=0,alen,blen,sum=0,res6565=0,flag=0; char result65; alen=strle

6、n(a);blen=strlen(b); for (i=0;ialen;i+) for (j=0;j=0;i-) for (j=blen-1;j=0;j-) sum=sum+resi+blen-j-1j; resultk=sum%10; k=k+1; sum=sum/10; for (i=blen-2;i=0;i-) for (j=0;j=i;j+) sum=sum+resi-jj; resultk=sum%10; k=k+1; sum=sum/10; if (sum!=0) resultk=sum;k=k+1; for (i=0;i=0;i-) si=resultk-1-i; sk=0; w

7、hile(1) if (strlen(s)!=strlen(a)&s0=0) strcpy(s,s+1); else break; 4.精度计算加法 语法：add(char a,char b,char s); 参数： a： 被乘数，用字符串表示，位数不限 b： 乘数，用字符串表示，位数不限 t： 结果，用字符串表示 返回值： null 注意： 空间复杂度为 o(n2) 需要 string.h 源程序： void add(char a,char b,char back) int i,j,k,up,x,y,z,l; char *c; if (strlen(a)strlen(b) l=strlen(

8、a)+2; else l=strlen(b)+2; c=(char *) malloc(l*sizeof(char); i=strlen(a)-1; j=strlen(b)-1; k=0;up=0; while(i=0|j=0) if(i0) x=0; else x=ai; if(j9) up=1;z%=10; else up=0; ck+=z+0; i-;j-; if(up) ck+=1; i=0; ck=0; for(k-=1;k=0;k-) backi+=ck; backi=0; 5.精度计算减法 语法：sub(char s1,char s2,char t); 参数： s1： 被减数，用

9、字符串表示，位数不限 s2： 减数，用字符串表示，位数不限 t： 结果，用字符串表示 返回值： null 注意： 默认s1=s2，程序未处理负数情况 需要 string.h 源程序： void sub(char s1,char s2,char t) int i,l2,l1,k; l2=strlen(s2);l1=strlen(s1); tl1=0;l1-; for (i=l2-1;i=0;i-,l1-) if (s1l1-s2i=0) tl1=s1l1-s2i+0; else tl1=10+s1l1-s2i+0; s1l1-1=s1l1-1-1; k=l1; while(s1k=0) tl1=

10、s1l1;l1-; loop: if (t0=0) l1=strlen(s1); for (i=0;il1-1;i+) ti=ti+1; tl1-1=0; goto loop; if (strlen(t)=0) t0=0;t1=0; 6.任意进制转换 语法：conversion(char s1,char s2,long d1,long d2); 参数： s： 原进制数字，用字符串表示 s2： 转换结果，用字符串表示 d1： 原进制数 d2： 需要转换到的进制数 返回值： null 注意： 高于9的位数用大写AZ表示，216位进制通过验证 源程序： void conversion(char s,

11、char s2,long d1,long d2) long i,j,t,num; char c; num=0; for (i=0;si!=0;i+) if (si=0) t=si-0; else t=si-A+10; num=num*d1+t; i=0; while(1) t=num%d2; if (t=9) s2i=t+0; else s2i=t+A-10; num/=d2; if (num=0) break; i+; for (j=0;ji/2;j+) c=s2j;s2j=si-j;s2i-j=c; s2i+1=0; 7.最大公约数、最小公倍数 语法：resulet=hcf(int a,i

12、nt b)、result=lcd(int a,int b) 参数： a： int a，求最大公约数或最小公倍数 b： int b，求最大公约数或最小公倍数 返回值： 返回最大公约数或最小公倍数 注意： lcd 需要连同 hcf 使用 源程序： int hcf(int a,int b) int r=0; while(b!=0) r=a%b; a=b; b=r; return(a); lcd(int u,int v,int h) return(u*v/h); 8.组合序列 语法：m_of_n(int m, int n1, int m1, int* a, int head) 参数： m： 组合数C的

13、上参数 n1： 组合数C的下参数 m1： 组合数C的上参数，递归之用 *a： 1n的整数序列数组 head： 头指针 返回值： null 注意： *a需要自行产生 初始调用时，m=m1、head=0 调用例子：求C(m,n)序列：m_of_n(m,n,m,a,0); 源程序： void m_of_n(int m, int n1, int m1, int* a, int head) int i,t; if(m1n1) return; if(m1=n1) for(i=0;im;i+) coutai ; / 输出序列 coutn; return; m_of_n(m,n1-1,m1,a,head);

14、/ 递归调用 t=ahead;ahead=an1-1+head;an1-1+head=t; m_of_n(m,n1-1,m1-1,a,head+1); / 再次递归调用 t=ahead;ahead=an1-1+head;an1-1+head=t; 9.快速傅立叶变换 语法：kkfft(double pr,double pi,int n,int k,double fr,double fi,int l,int il); 参数： prn： 输入的实部 pin： 数入的虚部 n，k： 满足n=2k frn： 输出的实部 fin： 输出的虚部 l： 逻辑开关，0 FFT，1 ifFT il： 逻辑开关，

15、0 输出按实部/虚部；1 输出按模/幅角 返回值： null 注意： 需要 math.h 源程序： void kkfft(pr,pi,n,k,fr,fi,l,il) int n,k,l,il; double pr,pi,fr,fi; int it,m,is,i,j,nv,l0; double p,q,s,vr,vi,poddr,poddi; for (it=0; it=n-1; it+) m=it; is=0; for (i=0; i=k-1; i+) j=m/2; is=2*is+(m-2*j); m=j; frit=pris; fiit=piis; pr0=1.0; pi0=0.0; p=

16、6.283185306/(1.0*n); pr1=cos(p); pi1=-sin(p); if (l!=0) pi1=-pi1; for (i=2; i=n-1; i+) p=pri-1*pr1; q=pii-1*pi1; s=(pri-1+pii-1)*(pr1+pi1); pri=p-q; pii=s-p-q; for (it=0; it=0; l0-) m=m/2; nv=2*nv; for (it=0; it=(m-1)*nv; it=it+nv) for (j=0; j=(nv/2)-1; j+) p=prm*j*frit+j+nv/2; q=pim*j*fiit+j+nv/2;

17、s=prm*j+pim*j; s=s*(frit+j+nv/2+fiit+j+nv/2); poddr=p-q; poddi=s-p-q; frit+j+nv/2=frit+j-poddr; fiit+j+nv/2=fiit+j-poddi; frit+j=frit+j+poddr; fiit+j=fiit+j+poddi; if (l!=0) for (i=0; i=n-1; i+) fri=fri/(1.0*n); fii=fii/(1.0*n); if (il!=0) for (i=0; i=n-1; i+) pri=sqrt(fri*fri+fii*fii); if (fabs(fri

18、)0) pii=90.0; else pii=-90.0; else pii=atan(fii/fri)*360.0/6.283185306; return; 10.Ronberg算法计算积分 语法：result=integral(double a,double b); 参数： a： 积分上限 b： 积分下限 function f： 积分函数 返回值： f在之间的积分值 注意： function f(x)需要自行修改，程序中用的是sina(x)/x 需要 math.h 默认精度要求是1e-5 源程序： double f(double x) return sin(x)/x; /在这里插入被积函数

19、 double integral(double a,double b) double h=b-a; double t1=(1+f(b)*h/2.0; int k=1; double r1,r2,s1,s2,c1,c2,t2; loop: double s=0.0; double x=a+h/2.0; while(x1e-5) r1=r2;c1=c2;k+; h/=2.0; t1=t2;s1=s2; goto loop; return r2; 11.行列式计算 语法：result=js(int s,int n) 参数： s： 行列式存储数组 n： 行列式维数，递归用 返回值： 行列式值 注意：

20、函数中常数N为行列式维度，需自行定义 源程序： int js(s,n) int sN,n; int z,j,k,r,total=0; int bNN;/*bNN用于存放，在矩阵sNN中元素s0的余子式*/ if(n2) for(z=0;zn;z+) for(j=0;jn-1;j+) for(k=0;k=z) bjk=sj+1k+1; else bjk=sj+1k; if(z%2=0) r=s0z*js(b,n-1); /*递归调用*/ else r=(-1)*s0z*js(b,n-1); total=total+r; else if(n=2) total=s00*s11-s01*s10; re

21、turn total; 12.求排列组合数 语法：result=P(long n,long m); / result=long C(long n,long m); 参数： m： 排列组合的上系数 n： 排列组合的下系数 返回值： 排列组合数 注意： 符合数学规则：mn 源程序： long P(long n,long m) long p=1; while(m!=0) p*=n;n-;m-; return p; long C(long n,long m) long i,c=1; i=m; while(i!=0) c*=n;n-;i-; while(m!=0) c/=m;m-; return c;

22、二、字符串处理 1.字符串替换 语法：replace(char str,char key,char swap); 参数： str： 在此源字符串进行替换操作 key： 被替换的字符串，不能为空串 swap： 替换的字符串，可以为空串，为空串表示在源字符中删除key 返回值： null 注意： 默认str长度小于1000，如否，重新设定设定tmp大小 需要 string.h 源程序： void replace(char str,char key,char swap) int l1,l2,l3,i,j,flag; char tmp1000; l1=strlen(str); l2=strlen(ke

23、y); l3=strlen(swap); for (i=0;i=l1-l2;i+) flag=1; for (j=0;jl2;j+) if (stri+j!=keyj) flag=0;break; if (flag) strcpy(tmp,str); strcpy(&tmpi,swap); strcpy(&tmpi+l3,&stri+l2); strcpy(str,tmp); i+=l3-1; l1=strlen(str); 2.字符串查找 语法：result=strfind(char str,char key); 参数： str： 在此源字符串进行查找操作 key： 被查找的字符串，不能为空

24、串 返回值： 如果查找成功，返回key在str中第一次出现的位置，否则返回-1 注意： 需要 string.h 源程序： int strfind(char str,char key) int l1,l2,i,j,flag; l1=strlen(str); l2=strlen(key); for (i=0;i=l1-l2;i+) flag=1; for (j=0;jl) return 0; for (i=start;istart+len;i+) strbackk+=stri; strbackk=0; return 1; 三、计算几何 1.叉乘法求任意多边形面积 语法：result=polygon

25、area(Point *polygon,int N); 参数： *polygon： 多变形顶点数组 N： 多边形顶点数目 返回值： 多边形面积 注意： 支持任意多边形，凹、凸皆可 多边形顶点输入时按顺时针顺序排列 源程序： typedef struct double x,y; Point; double polygonarea(Point *polygon,int N) int i,j; double area = 0; for (i=0;iN;i+) j = (i + 1) % N; area += polygoni.x * polygonj.y; area -= polygoni.y *

26、polygonj.x; area /= 2; return(area PI) dtheta -= PI*2; while (dtheta -PI) dtheta += PI*2; return(dtheta); 4.两点距离 语法：result=distance_2d(float x1,float x2,float y1,float y2); 参数： x/y/z1各点的x、y、z坐标 2： 返回值： 两点之间的距离 注意： 需要 math.h 源程序： float distance_2d(float x1,float x2,float y1,float y2) return(sqrt(x1-x

27、2)*(x1-x2)+(y1-y2)*(y1-y2); float distance_3d(float x1,float x2,float y1,float y2,float z1,float z2) return(sqrt(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2); 5.射向法判断点是否在多边形内部 语法：result=insidepolygon(Point *polygon,int N,Point p); 参数： *polygon： 多边形顶点数组 N： 多边形顶点个数 p： 被判断点 返回值： 0：点在多边形内部；1：点在多边形外部 注

28、意： 若p点在多边形顶点或者边上，返回值不确定，需另行判断 需要 math.h 源程序： #define MIN(x,y) (x y ? x : y) typedef struct double x,y; Point; int insidepolygon(Point *polygon,int N,Point p) int counter = 0; int i; double xinters; Point p1,p2; p1 = polygon0; for (i=1;i MIN(p1.y,p2.y) if (p.y = MAX(p1.y,p2.y) if (p.x = MAX(p1.x,p2.x) if (p1.y != p2.y) xinters = (p.y-p1.y)*(p2.x-p1