ACM常用模板代碼

1、ACM常用代碼/模板匯總一、數(shù)學(xué)問題1.精度計算大數(shù)階乘語法：int result=factorial(int n);參數(shù)：n：n 的階乘返回值：階乘結(jié)果的位數(shù)注意：  本程序直接輸出n!的結(jié)果，需要返回結(jié)果請保留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; j<=m; j+) aj=aj*i+c; c=aj/10000; aj=aj%10000; if(c>

2、0) 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; 2.精度計算乘法（大數(shù)乘小數(shù)）語法：mult(char c,char t,int m);參數(shù)：c：被乘數(shù)，用字符串表示，位數(shù)不限t：結(jié)果，用字符串表示m：乘數(shù)，限定10以內(nèi)返回值：Null注意：  需要 string.h源程序：  void mult(char c,char t,int m) int i,l

3、,k,flag,add=0; char s100; l=strlen(c); for (i=0; i<l; i+) sl-i-1=ci-'0' for (i=0; i<l; i+) k=si*m+add; if (k>=10) si=k%10; add=k/10; flag=1; else si=k; flag=0; add=0; if (flag) l=i+1; si=add; else l=i; for (i=0; i<l; i+) tl-1-i=si+'0' tl='0'3.精度計算乘法（大數(shù)乘大數(shù)）語法：mult(

4、char a,char b,char s);參數(shù)：a：被乘數(shù)，用字符串表示，位數(shù)不限b：乘數(shù)，用字符串表示，位數(shù)不限t：結(jié)果，用字符串表示返回值：Null注意：  空間復(fù)雜度為 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;    a

5、len=strlen(a);blen=strlen(b);     for (i=0;i<alen;i+)    for (j=0;j<blen;j+) resij=(ai-'0')*(bj-'0');    for (i=alen-1;i>=0;i-)              

6、0;     for (j=blen-1;j>=0;j-) sum=sum+resi+blen-j-1j;            resultk=sum%10;            k=k+1;         

7、   sum=sum/10;            for (i=blen-2;i>=0;i-)                    for (j=0;j<=i;j+) sum=sum+resi-jj;   

8、;         resultk=sum%10;            k=k+1;            sum=sum/10;           

9、60;if (sum!=0) resultk=sum;k=k+1;    for (i=0;i<k;i+) resulti+='0'    for (i=k-1;i>=0;i-) si=resultk-1-i;    sk='0'    while(1)            

10、;    if (strlen(s)!=strlen(a)&&s0='0')             strcpy(s,s+1);        else            break; 

11、60;      4.精度計算加法語法：add(char a,char b,char s);參數(shù)：a：被乘數(shù)，用字符串表示，位數(shù)不限b：乘數(shù)，用字符串表示，位數(shù)不限t：結(jié)果，用字符串表示返回值：Null注意：  空間復(fù)雜度為 o(n2) 需要 string.h源程序：  void add(char a,char b,char back)    int i,j,k,up,x,y,z,l;    char *c

12、;    if (strlen(a)>strlen(b) l=strlen(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)&#

13、160;                   if(i<0) x='0' else x=ai;            if(j<0) y='0' else y=bj;     

14、       z=x-'0'+y-'0'            if(up) z+=1;            if(z>9) up=1;z%=10; else up=0;      

15、;      ck+=z+'0'            i-;j-;            if(up) ck+='1'    i=0;    ck='0' &#

16、160;  for(k-=1;k>=0;k-)        backi+=ck;    backi='0' 5.精度計算減法語法：sub(char s1,char s2,char t);參數(shù)：s1：被減數(shù)，用字符串表示，位數(shù)不限s2：減數(shù)，用字符串表示，位數(shù)不限t：結(jié)果，用字符串表示返回值：Null注意：  默認s1>=s2，程序未處理負數(shù)情況 需要 string.h源程序：  

17、;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-)              

18、;  if (s1l1-s2i>=0)             tl1=s1l1-s2i+'0'        else                    

19、;    tl1=10+s1l1-s2i+'0'            s1l1-1=s1l1-1-1;                        k=l1;  

20、;  while(s1k<0) s1k+=10;s1k-1-=1;k-;    while(l1>=0) tl1=s1l1;l1-;loop:    if (t0='0')                 l1=strlen(s1);      

21、60; for (i=0;i<l1-1;i+) ti=ti+1;        tl1-1='0'        goto loop;            if (strlen(t)=0) t0='0't1='0' 6.任意進制轉(zhuǎn)換語法：conversi

22、on(char s1,char s2,long d1,long d2);參數(shù)：s：原進制數(shù)字，用字符串表示s2：轉(zhuǎn)換結(jié)果，用字符串表示d1：原進制數(shù)d2：需要轉(zhuǎn)換到的進制數(shù)返回值：Null注意：  高于9的位數(shù)用大寫'A''Z'表示，216位進制通過驗證源程序：  void conversion(char s,char s2,long d1,long d2) long i,j,t,num; char c; num=0; for (i=0; si!='0' i+) if (si<='9'

23、&&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; j<i/2; j+) c=s2j; s2j=si-j; s2i-j=c; s2i+1='0'7.最大公約數(shù)、最小公倍數(shù)語法：resulet=hcf(int a

24、,int b)、result=lcd(int a,int b)參數(shù)：a：int a，求最大公約數(shù)或最小公倍數(shù)b：int b，求最大公約數(shù)或最小公倍數(shù)返回值：返回最大公約數(shù)（hcf）或最小公倍數(shù)（lcd）注意：  a > b源程序：  int hcf(int a,int b)    return b=0 ? a : hcf(b, a % b); lcd(int a, int b) return(a * b / hcf(a, b);8.組合序列語法：m_of_n(int m, int n1, int m1, in

25、t* a, int head)參數(shù)：m：組合數(shù)C的上參數(shù)n1：組合數(shù)C的下參數(shù)m1：組合數(shù)C的上參數(shù)，遞歸之用*a：1n的整數(shù)序列數(shù)組head：頭指針返回值：Null注意：  *a需要自行產(chǎn)生 初始調(diào)用時，m=m1、head=0 調(diào)用例子：求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(m1&

26、lt;0 | m1>n1) return;     if(m1=n1)                  for(i=0;i<m;i+) cout<<ai<<' ' / 輸出序列         cout<<'n'   

27、      return;              m_of_n(m,n1-1,m1,a,head); / 遞歸調(diào)用     t=ahead;ahead=an1-1+head;an1-1+head=t;    m_of_n(m,n1-1,m1-1,a,head+1); / 再次遞歸調(diào)用     t

28、=ahead;ahead=an1-1+head;an1-1+head=t; 9.快速傅立葉變換（FFT）語法：kkfft(double pr,double pi,int n,int k,double fr,double fi,int l,int il);參數(shù)：prn：輸入的實部 pin：數(shù)入的虛部n，k：滿足n=2kfrn：輸出的實部fin：輸出的虛部l：邏輯開關(guān)，0 FFT，1 ifFTil：邏輯開關(guān)，0 輸出按實部/虛部；1 輸出按模/幅角 返回值：Null注意：  需要 math.h源程序：  void kkfft(pr,pi,n,k,fr,fi,

29、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=6.283185306/(1.0*n); pr1=cos(p); pi1=-sin(p); if (l!=0) pi1=-pi1; for (

30、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<=n-2; it=it+2) vr=frit; vi=fiit; frit=vr+frit+1; fiit=vi+fiit+1; frit+1=vr-frit+1; fiit+1=vi-fiit+1; m=n/2; nv=2; for (l0=k-2; l0>=0; l0-) m=m/2; nv=2*nv; for (it=0; it<=(m-1)*nv; it=i

31、t+nv) for (j=0; j<=(nv/2)-1; j+) p=prm*j*frit+j+nv/2; q=pim*j*fiit+j+nv/2; 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=fi

32、i/(1.0*n); if (il!=0) for (i=0; i<=n-1; i+) pri=sqrt(fri*fri+fii*fii); if (fabs(fri)<0.000001*fabs(fii) if (fii*fri)>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);參數(shù)：a：積分上限b：積分下限function f：積分函數(shù)返回值：f在（a,b）之

33、間的積分值注意：  function f(x)需要自行修改，程序中用的是sina(x)/x 需要 math.h 默認精度要求是1e-5源程序：  double f(double x) return sin(x)/x; /在這里插入被積函數(shù)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; wh

34、ile(x<b) s+=f(x); x+=h; t2=(t1+h*s)/2.0; s2=t2+(t2-t1)/3.0; if(k=1) k+; h/=2.0; t1=t2; s1=s2; goto loop; c2=s2+(s2-s1)/15.0; if(k=2) c1=c2; k+; h/=2.0; t1=t2; s1=s2; goto loop; r2=c2+(c2-c1)/63.0; if(k=3) r1=r2; c1=c2; k+; h/=2.0; t1=t2; s1=s2; goto loop; while(fabs(1-r1/r2)>1e-5) r1=r2; c1=c2

35、; k+; h/=2.0; t1=t2; s1=s2; goto loop; return r2;11.行列式計算語法：result=js(int s,int n)參數(shù)：s：行列式存儲數(shù)組n：行列式維數(shù)，遞歸用返回值：行列式值注意：  函數(shù)中常數(shù)N為行列式維度，需自行定義源程序：  int sN,n;int js(s,n) int z,j,k,r,total=0; int bNN;/*bNN用于存放，在矩陣sNN中元素s0的余子式*/ if(n>2) for(z=0; z<n; z+) for(j=0; j<n-1; j+) for(k

36、=0; k<n-1; k+) if(k>=z) bjk=sj+1k+1; else bjk=sj+1k; if(z%2=0) r=s0z*js(b,n-1); /*遞歸調(diào)用*/ else r=(-1)*s0z*js(b,n-1); total=total+r; else if(n=2) total=s00*s11-s01*s10; return total;12.求排列組合數(shù)語法：result=P(long n,long m); / result=long C(long n,long m);參數(shù)：m：排列組合的上系數(shù)n：排列組合的下系數(shù)返回值：排列組合數(shù)注意：  

37、;符合數(shù)學(xué)規(guī)則：m<n源程序：  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;

38、0;   while(i!=0)        c*=n;n-;i-;    while(m!=0)        c/=m;m-;    return c; 三、計算幾何1.叉乘法求任意多邊形面積語法：result=polygonarea(Point *polygon, int N);參數(shù)：*polygon：多變形頂點數(shù)組N：

39、多邊形頂點數(shù)目返回值：多邊形面積注意：  支持任意多邊形，凹、凸皆可 多邊形頂點輸入時按順時針順序排列源程序：  typedef struct     double x,y; Point; double polygonarea(Point *polygon,int N) int i,j; double area = 0; for (i=0; i<N; i+) j = (i + 1) % N; area += polygoni.x * polygonj.y; area -= polygoni.y *

40、polygonj.x; area /= 2; return(area < 0 ? -area : area);2.求三角形面積語法：result=area3(float x1,float y1,float x2,float y2,float x3,float y3);參數(shù)：x13：三角形3個頂點x坐標y13：三角形3個頂點y坐標返回值：三角形面積注意：  需要 math.h源程序：  float area3(float x1,float y1,float x2,float y2,float x3,float y3)   

41、; float a,b,c,p,s;    a=sqrt(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);    b=sqrt(x1-x3)*(x1-x3)+(y1-y3)*(y1-y3);    c=sqrt(x3-x2)*(x3-x2)+(y3-y2)*(y3-y2);    p=(a+b+c)/2;    s=sqrt(p*(p-a)*(p-b)*(p-c);

42、0;   return s;3.兩矢量間角度語法：result=angle(double x1, double y1, double x2, double y2);參數(shù)：x/y12：兩矢量的坐標返回值：兩的角度矢量注意：  返回角度為弧度制，并且以逆時針方向為正方向 需要 math.h源程序：  #define PI 3.1415926double angle(double x1, double y1, double x2, double y2)    double dthe

43、ta,theta1,theta2;     theta1 = atan2(y1,x1);    theta2 = atan2(y2,x2);    dtheta = theta2 - theta1;    while (dtheta > PI)        dtheta -= PI*2;    while (d

44、theta < -PI)        dtheta += PI*2;     return(dtheta);4.兩點距離（2D、3D）語法：result=distance_2d(float x1,float x2,float y1,float y2);參數(shù)：x/y/z12：各點的x、y、z坐標返回值：兩點之間的距離注意：  需要 math.h源程序：  float distance_2d(float x1,float x2,fl

45、oat y1,float y2)     return(sqrt(x1-x2)*(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.射向法判斷點是否在多邊形內(nèi)部語法：result=insidepolygon(Point *polygon,int N,

46、Point p);參數(shù)：*polygon：多邊形頂點數(shù)組N：多邊形頂點個數(shù)p：被判斷點返回值：0：點在多邊形內(nèi)部；1：點在多邊形外部注意：  若p點在多邊形頂點或者邊上，返回值不確定，需另行判斷 需要 math.h源程序：  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

47、<=N; i+) p2 = polygoni % N; if (p.y > min(p1.y, p2.y) && p.y <= max(p1.y,p2.y) && p.x <= max(p1.x,p2.x) && p1.y != p2.y) xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x; if (p1.x = p2.x | p.x <= xinters) counter+; p1 = p2; if (counter % 2 = 0) return(OUTSIDE)

48、; else return(INSIDE);6.判斷點是否在線段上語法：result=Pointonline(Point p1,Point p2,Point p);參數(shù)：p1、p2：線段的兩個端點p：被判斷點返回值：0：點在不在線段上；1：點在線段上注意：  若p線段端點上返回1 需要 math.h源程序：  typedef struct double x,y; Point;int Pointonline(Point p1, Point p2, Point p) double x1,y1,x2,y2; x1=p.x-p1.x; x2=p2.x-

49、p1.x; y1=p.y-p1.y; y2=p2.y-p1.y; if (fabs(x1*y2-x2*y1)>EPS) return 0; if (min(p1.x,p2.x)<=p.x && p.x<=max(p1.x,p2.x) && (min(p1.y,p2.y)<=p.y && p.y<=max(p1.y,p2.y) return 1; return 0;7.判斷兩線段是否相交語法：result= intersect3(Point aa, Point bb, Point cc, Point dd)源程序：&#

50、160;struct Point double x, y;double determinant(double v1, double v2, double v3, double v4) / 行列式return (v1*v3-v2*v4);bool intersect3(Point aa, Point bb, Point cc, Point dd)double delta = determinant(bb.x-aa.x, cc.x-dd.x, bb.y-aa.y, cc.y-dd.y);if ( fabs(delta)<=EPS ) / delta=0，表示兩線段重合或平行return fa

51、lse;double namenda = determinant(cc.x-aa.x, cc.x-dd.x, cc.y-aa.y, cc.y-dd.y) / delta;if ( namenda>1 | namenda<0 )return false;double miu = determinant(bb.x-aa.x, cc.x-aa.x, bb.y-aa.y, cc.y-aa.y) / delta;if ( miu>1 | miu<0 )return false;return true;8.判斷線段與直線是否相交語法：result=lineintersect(Poi

52、nt p1,Point p2,Point p3,Point p4);參數(shù)：p1、p2：線段的兩個端點p3、p4：直線上的兩個點返回值：0：線段直線不相交；1：線段和直線相交注意：  如線段在直線上，返回 1源程序：  typedef struct     double x,y; Point;int lineintersect(Point p1,Point p2,Point p3,Point p4)    Point tp1,tp2,tp3;   

53、 tp1.x=p1.x-p3.x;    tp1.y=p1.y-p3.y;    tp2.x=p4.x-p3.x;    tp2.y=p4.y-p3.y;    tp3.x=p2.x-p3.x;    tp3.y=p2.y-p3.y;    if (tp1.x*tp2.y-tp1.y*tp2.x)*(tp2.x*tp3.y-tp2.y*tp3.x)

54、>=0) return 1; else return 0;9.點到線段最短距離語法：result=mindistance(Point p1,Point p2,Point q);參數(shù)：p1、p2：線段的兩個端點q：判斷點返回值：點q到線段p1p2的距離注意：  需要 math.h源程序：  typedef struct double x,y; Point;double mindistance(Point p1,Point p2,Point q) int flag=1; double k; Point s; if (p1.x=p2.x) s.x=p1.

55、x; s.y=q.y; flag=0; if (p1.y=p2.y) s.x=q.x; s.y=p1.y; flag=0; if (flag) k=(p2.y-p1.y)/(p2.x-p1.x); s.x=(k*k*p1.x+k*(q.y-p1.y)+q.x)/(k*k+1); s.y=k*(s.x-p1.x)+p1.y; if (min(p1.x,p2.x)<=s.x && s.x<=max(p1.x,p2.x) return sqrt(q.x-s.x)*(q.x-s.x)+(q.y-s.y)*(q.y-s.y); else return min(sqrt(q.x

56、-p1.x)*(q.x-p1.x)+(q.y-p1.y)*(q.y-p1.y),sqrt(q.x-p2.x)*(q.x-p2.x)+(q.y-p2.y)*(q.y-p2.y);10.求兩直線的交點語法：result=mindistance(Point p1,Point p2,Point q);參數(shù)：p1p4：直線上不相同的兩點*p：通過指針返回結(jié)果返回值：1：兩直線相交；2：兩直線平行注意：  如需要判斷兩線段交點，檢驗k和對應(yīng)k1（注釋中）的值是否在01之間，用在01之間的那個求交點源程序：  struct Point double x,y;int l

57、inecorss(Point p1,Point p2,Point p3,Point p4,Point *p) double k; /同一直線 if (p4.x-p3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-p3.x)=0&& (p2.x-p1.x)*(p1.y-p3.y)-(p2.y-p1.y)*(p1.x-p3.x)=0) return 2; /平行，不同一直線 if (p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y)=0) return 0;k=(p4.x-p3.x)*(p1.y-p3.y)-(p4.y-

58、p3.y)*(p1.x-p3.x)/(p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y); (*p).x=p1.x+k*(p2.x-p1.x); (*p).y=p1.y+k*(p2.y-p1.y); return 1;/有交點11.判斷一個封閉圖形是凹集還是凸集語法：result=convex(Point *p,int n);參數(shù)：*p：封閉曲線頂點數(shù)組n：封閉曲線頂點個數(shù)返回值：1：凸集；-1：凹集；0：曲線不符合要求無法計算注意：  默認曲線為簡單曲線：無交叉、無圈源程序：  typedef struct &

59、#160;   double x,y; Point;int convex(Point *p,int n)    int i,j,k;    int flag = 0;    double z;    if (n < 3)        return(0);    for (i=0;i

60、<n;i+)         j = (i + 1) % n;        k = (i + 2) % n;        z = (pj.x - pi.x) * (pk.y - pj.y);        z -= (pj.y - pi.y) * (pk.x - pj.

61、x);        if (z < 0)            flag |= 1;        else if (z > 0)            flag |= 2; 

62、       if (flag = 3)            return 1; /CONCAVE            if (flag != 0)        return 1; /CONVEX

63、0;   else    return 0;12.Graham掃描法尋找凸包語法：Graham_scan(Point PointSet,Point ch,int n,int &len);參數(shù)：PointSet：輸入的點集ch：輸出的凸包上的點集，按照逆時針方向排列n：PointSet中的點的數(shù)目len：輸出的凸包上的點的個數(shù)返回值：null源程序：  struct Point    float x,y; float multiply(Point p1,Poi

64、nt p2,Point p0)    return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); float distance(Point p1,Point p2)    return(sqrt(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y); void Graham_scan(Point PointSet,Point ch,int n,int &len)    int i

65、,j,k=0,top=2;    Point tmp;   for(i=1;i<n;i+)    if (PointSeti.y<PointSetk.y)|(PointSeti.y=PointSetk.y)&&(PointSeti.x<PointSetk.x)    k=i;    tmp=PointSet0;    PointSet0=Poi

66、ntSetk;    PointSetk=tmp;     for (i=1;i<n-1;i+)                k=i;        for (j=i+1;j<n;j+)            if ( (multiply(PointSetj,PointSetk,PointSet0)>0) |    &#