《ACM常用算法打印版.docx》由会员分享，可在线阅读，更多相关《ACM常用算法打印版.docx（25页珍藏版）》请在课桌文档上搜索。
1、ACM小组内部预定函数Ver2.0byIcyFenix数学问题：1 .精度计算一一大数阶乘2 .精度计算一一乘法(大数乘小数)3 .精度计算一一乘法(大数乘大数)4 .精度计算加法5 .精度计算减法6 .任意进制转换7 .最大公约数、最小公倍数8 .组合序列9 .快速傅立叶变换(FFT)IO-Ronberg算法计算积分11 .行列式计算12 .求排列组合数字符串处理：1.字符串替换2 .字符串查找3 .字符串截取计算几何：1 .叉乘法求任意多边形面积2 .求三角形面积3 .两矢量间角度4 .两点距离(2D、3D)5 .射向法判断点是否在多边形内部6 .判断点是否在线段上7 .判断两线段是否相交
2、8 .判断线段与直线是否相交9 .点到线段最短距离10 .求两直线的交点IL判断一个封闭图形是凹集还是凸集12 .Graham扫描法寻找凸包数论：13 x的二进制长度14 返回X的二进制表示中从低到高的第i位15 模取箱运算16 求解模线性方程17 求解模线性方程组(中国余数定理)18 筛法素数产生器19 判断一个数是否素数图论：I-Prim算法求最小生成树2.Dijkstra算法求单源最短路径3.Bellman-ford算法求单源最短路径4.Floyd算法求每对节点间最短路径排序/查找：1 .快速排序2 .希尔排序3 .选择法排序4 .二分查找数据结构：1 .顺序队列2 .顺序栈3 .链表4
3、 .链栈5 .二叉树一、数学问题1.精度计算一一大数阶乘语法：intresult=factorial(intn);参数：n：n的阶乘返回值：阶乘结果的位数注意：本程序直接输出n!的结果，需要返回结果请保留onga需要math.h源程序：intfactorial(intn)(longa10000;inti,j,l,c,m=0,w;a0=l;for(i=l;i=n;i+)(c=0;for(j=0;jO)m+;am=c;)w=m*4+logl0(am)+l;printf(,n%ld,am);for(i=m-l;i=0;i-)printf(%4.4ld,ai);returnw;)2 .精度计算一一乘法
4、(大数乘小数)语法：mult(charczchart,intm);参数：c:被乘数，用字符串表示，位数不限t：结果，用字符串表示m：乘数，限定10以内返回值：null注意：需要string.h源程序：voidmult(charczchartJntm)inti,lzkzflagzadd=O;chars100;l=strlen(c);for(i=0;il;i+)sl-i-l=ci-,O;for(i=0;i=10)si=k%10;add=k/10;flag=l;elsesi=k;flag=O;add=O;if(flag)l=i+l;si=add;elsel=i;for(i=0;il;i+)tl-l-
5、i=si+,O;t=,0;)3 .精度计算乘法(大数乘大数)语法：mult(chara,charb,chars);参数：a：被乘数，用字符串表示，位数不限b:乘数，用字符串表示，位数不限t：结果，用字符串表示返回值：null注意：空间复杂度为o(n2)需要string.h源程序：voidmult(charazcharb,chars)(intiJ=0,alenzblen,sum=0,res6565=0,flag=0;charresult65;alen=strlen(a);blen=strlen(b);for(i=0;ialen;i+)for(j=O;j=O;i-)(for(j=blen-lJ=O
6、j-)sum=sum+resi+blen-j-lj;resultk=sum%10;k=k+l;sum=sum10;)for(i=blen-2;i=0;i-)(for(j=O;j=i;j+)sum=sum+resi-jj;resultk=sum%10;k=k+l;sum=sum10;if(sum!=0)resultk=sum;k=k+l;for(i=0;i=0;i-)si=resultk-l-i;sk=,O,;while(l)(if(strlen(s)!=strlen(a)&sO=O)strcpyszs+l);elsebreak;)4 .精度计算加法语法：add(charazcharb,char
7、s);参数：a：被乘数，用字符串表示，位数不限b：乘数，用字符串表示，位数不限t：结果，用字符串表示返回值：null注意：空间复杂度为o(n2)需要string.h源程序：voidadd(chara,charbzcharback)(intij,k,up,x,y,z,l;char*c;if(strlenastrlen(b)l=strlen(a)+2;elsel=strlen(b)+2;c=(char*)malloc(l*sizeof(char);i=strlen(a)-l;j=strlen(b)-l;k=O;up=O;while(i=0j=0)(if(i0)x=,0,;elsex=ai;if(j
8、9)up=l;z%=10;elseup=0;ck+=z+,O,;)if(up)ck+=,l,;i=0;ck=O;for(k-=l;k=0;k)backi+=ck;backi=,O,;)5.精度计算减法i吾法：sub(charslzchars2zchart);参数：sl):被减数，用字符串表示，位数不限s2：减数，用字符串表示，位数不限t：结果，用字符串表示返回值：null注意：默认sl=s2,程序未处理负数情况需要string.h源程序：voidSUb(CharSnLChars2,chart)(inti,l2,ll,k;I2=strlen(s2)jl=strlen(sl);tll=0;ll-;
9、for(i=l2-l;i=0;i-,ll-)(if(slll-s2i=0)tll=slll-s2(i+O;else(tll=10+slll-s2i+,0,;slll-l=slll-l-l;)k=ll;while(slk=0)tll=slll;ll-;loop:if(t0=,0,)(Il=StrIen(Sl);for(i=O;ill-l;i+)ti=ti+l;tl-l=0;gotoloop;)ifstrlen(t)=O)tO=,Otl=,O;)6任意进制转换语法：conversion(charslzchars2Jongdl,longd2);参数：s【l：原进制数字，用字符串表示s2:转换结果，用
10、字符串表示dl：原进制数d2：需要转换到的进制数返回值：null注意：高于9的位数用大写7VZ表示，2、16位进制通过验证源程序：voidconversion(charszchars2JongdiJongd2)(longizjnum;charc;num=0;for(i=0;si!=0;i+)(if(si=0,)t=si-O,;elset=si-,A,+10;num=num*dl+t;)i=0;while(l)(t=num%d2;if(t=9)s2(i=t+,0;elses2i=t+A-10;num=d2;if(num=0)break;i+；for(j=0;ji/2;j+)c=$20；s2j=s
11、(i-j;s2i-j=c;s2i+l=0;)7最大公约数、最小公倍数语法:resulethcf(inta,intb)、result=lcd(inta,intb)参数：a：inta,求最大公约数或最小公倍数b：intb,求最大公约数或最小公倍数返回值：返回最大公约数(hcf)或最小公倍数(Icd)注意：Icd需要连同hcf使用源程序：inthcf(inta,intb)(intr=0;while(b!=0)(r=a%b;a=b;b=r;)returna);)lcd(intUjntvJnth)returnu*vh);)8 .组合序列语法：m_of_n(intm,intnl,intml,int*a,i
12、nthead)参数：m：组合数C的上参数nl：组合数C的下参数ml：组合数C的上参数，递归之用*a：ln的整数序列数组head：头指针返回值：null注意：*a需要自行产生初始调用时，m=ml、head=O调用例子：求C(m,n)序列：m_of_n(m,n,m,a,0);源程序：voidm_of_n(intm,intnlzintmlzint*a,inthead)inti,t;if(mlnl)return;if(ml=nl)(for(i=0;im;i+)coutai,;/输出序列cout,n,;return;)m-of-n(mznl-l,mlza,head);/递归调用t=ahead;ahead
13、=anl-l+head;anl-l+head=t;m-of-n(m,nl-l,ml-l,a,head+l);/再次递归调用t=ahead;ahead=anl-l+head;anl-l+head=t;)9 .快速傅立叶变换(FFT)语法：kkfft(doublepr,doublepi,intn,intk,doublefrzdoublefi,intIJntil);参数：PIInh输入的实部pin：数入的虚部n,k：满足n=2kfr:输出的实部fin:输出的虚部I：逻辑开关，OFFT,IifFTil：逻辑开关，0输出按实部/虚部；1输出按模/幅角返回值：null注意：需要math.h源程序：void
14、kkfft(pr,pizn,kzfr,fiJJI)intn,k,l,il;doubleprLpi,frfi;(intitzmziszij,nvJ0;doublep,q,s,vr,vi,poddr,poddi;for(it=0;it=n-l;it+)(m=it;is=0;for(i=0;i=k-l;i+)j=m2;is=2*is+(m-2*j);m=j;frit=pris;fiit=piis;)pr0=1.0;pi0=0.0;p=6.283185306(1.0*n);prl=cos(p);pil=-sin(p);if(=0)pil=-pil;for(i=2;i=n-l;i+)(p=pri-l*p
15、rl;q=pii-l*pil;s=(pri-l+pii-l)*(prl+pil);pri=p-q;pii=s-p-q;)for(it=0;it=O;10-)(m=m2;nv=2*nv;for(it=0;it=(m-l)*nv;it=it+nv)for(j=0;j=(nv2)-l;j+)(p=prm*j*frit+j+nv2;q=pim*j*fiit+j+nv2;s=prm*j+pim*j;s=s*(frit+j+nv2+fiit+j+nv2);poddr=p-q;poddi=s-p-q;frit+j+nv2=frit+j-poddr;fiit+j+nv2=fiit+j-poddi;frit+j
16、=frit+j+poddr;fiit+j=fiit+j+poddi;)if(II=O)for(i=0;i=n-l;i+)(fri=fri(1.0*n);fii=fii(1,0*n);)if(il!=0)fori=0;i=n-l;i+)(pri=sqrt(fri*fri+fii*fii);if(fabs(friJ)O)pii=90.0;elsepii=-90.0;)elsepii=atan(fiifri)*360.06.283185306;return;10.Ronberg算法计算积分语法：result=integral(doubleazdoubleb);参数：a：积分上限b：积分下限funct
17、ionf：积分函数返回值：f在(a,b)之间的积分值注意:functionf(x)需要自行修改，程序中用的是需要math.h默认精度要求是le-5源程序：doublef(doblex)(returnsin(x)x;在这里插入被积函数doubleintegral(doubleazdoubleb)(doubleh=b-a;doubletl=(l+f(b)*h2.0;intk=l;doublerl,r2,sl,s2,cl,c2,t2;loop:doubles=0.0;double=a+h2.0;while(xle-5)rl=r2;cl=c2;k+;h=2.0;tl=t2;Sl=S2;gotoloop
18、;returnr2;11.行列式计算语法：result=js(ints,intn)参数：s:行列式存储数组n：行列式维数，递归用返回值：行列式值注意：函数中常数N为行列式维度，需自行定义源程序：intjs(s,n)intsN,n;intzzjzkztotal=0;intbNN;/*bNN用于存放,在矩阵sNN中元素S的余子式*/if(n2)(for(z=0;zn;z+)(for(j=0;jn-l;j+)for(k=0;k=z)bjk=sj+lk+l;elsebjk=sj+lk;if(z%2=0)r=sOz*js(b,n-l);*递归调用7elser=(-l)*sOz*js(b,n-l);tot
19、al=total+r;)elseif(n=2)total=s00*sll-s0l*sl0;returntotal;)12.求排列组合数语法：result=P(longnzlongm);/result=longC(longnjongm);参数：m：排列组合的上系数n：排列组合的下系数返回值：排列组合数注意：符合数学规则：m=n源程序：longP(longnjongm)(longp=l;while(m!=0)p*=n;n-;m-;returnp;)longC(longnjongm)(longi,c=l;i=m;while(i!=0)c*=n;n-;i-；while(m!=0)c/=m;m-;ret
20、urnc;)二、字符串处理1 .字符串替换语法：replace(charstrzcharkey,charswap);参数：str：在此源字符串进行替换操作key：被替换的字符串，不能为空串swap。：替换的字符串，可以为空串，为空串表示在源字符中删除key返回值：null注意：默认str长度小于1000,如否，重新设定设定tmp大小需要string.h源程序：voidreplace(charstr,charkey,charswap)(intII,12,13,ij,flag;chartmp1000;Il=StrIen(Str);I2=strlen(key);I3=strlen(swap);for
21、(i=0;i=ll-l2;i+)(fag=l;for(j=0;jl2;j+)if(stri+j!=keyj)flag=O;break;if(flag)(strcpy(tmpzstr);strcpy(&tmpi,swap);Strcpy(&tmpi+I3,&stri+I2);strcpy(str,tmp);i+=l3-l;Il=StrIen(Str);)2 .字符串查找语法:result=strfind(charstr,charkey);参数：str：在此源字符串进行查找操作key：被查找的字符串，不能为空串返回值：如果查找成功，返回key在str中第一次出现的位置，否则返回-1注意：需要str
22、ing.h源程序：intstrfind(charstr,charkey)intllJ2JJ,flag;Il=StrIen(Str);I2=strlen(key);for(i=0;i=ll-l2;i+)(fag=l;for(j=0;jl)return0;for(i=start;istart+len;i+)strbackk+=stri;strbackk=,O,;return1;)三、计算几何1.叉乘法求任意多边形面积语法：result=polygonarea(Point*polygonjntN);参数：polygon：多变形顶点数组N：多边形顶点数目返回值：多边形面积注意：支持任意多边形，凹、凸皆
23、可多边形顶点输入时按顺时针顺序排列源程序：typedefstructdoublexzy;Point;doublepolygonarea(Point*polygonzintN)(inti,j;doublearea=0;for(i=0;iN;i+)j=(i+l)%N;area+=polygoni.x*polygonj.y;area-=polygoni.y*polygonj.;)area/=2;return(areaPI)dtheta-=Pl*2;while(dtheta-PI)dtheta+=Pl*2;return(dtheta);)4 .两点距离(2D、3D)语法：result=distance
24、_2d(floatl,floatx2,floatylzfloaty2)；参数：xyzlv2:各点的x、y、Z坐标返回值：两点之间的距离注意：需要math.h源程序：floatdistance_2d(floatxl,floatx2,floatylzfloaty2)(return(sqrt(l-x2)*(xl-x2)+(yl-y2)*(yl-y2);)floatdistance_3d(floatxlzfloat2zfloatyljloaty2zfloatzl,floatz2)return(sqrt(xl-x2)*(l-2)+(yl-y2)*(yl-y2)+(zl-z2)*(zl-z2)；)5 .射
25、向法判断点是否在多边形内部语法：result=insidepolygon(Point*polygonjntN7Pointp);参数：polygon：多边形顶点数组N：多边形顶点个数P：被判断点返回值：0：点在多边形内部；1：点在多边形外部注意：若P点在多边形顶点或者边上，返回值不确定，需另行判断需要math.h源程序：#defineMIN(,y)(xy?x:y)typedefstructdoublex,y;Point;intinsidepolygon(Point*polygonjntNzPointp)(intcounter=0;inti;doublexinters;Pointpl,p2;pl=
26、polygon0;for(i=l;iMIN(pl.yzp2.y)if(py=MAX(pl.y,p2.y)if(p.=MAX(pl.xzp2.)if(pl.y!=p2.y)xinters(p.y-pl.y)*(p2.x-pl.)(p2.y-pl.y)+pl.;if(pl.=p2.11p.x=xinters)counter+;)pl=P2；if(counter%2=0)return(OUTSIDE);elsereturn(INSIDE);6判断点是否在线段上语法：result=Pointonline(PointplzPointp2,Pointp);参数：pl、p2：线段的两个端点P：被判断点返回值
27、：0：点在不在线段上；1：点在线段上注意：若P线段端点上返回1需要math.h源程序：#defineMIN(,y)(xy?x:y)typedefstructdoublex,y;Point;intFC(doublexlzdoublex2)if(xl-x2-0.000002)return1;elsereturn0;)intPointonline(PointplzPointp2zPointp)doublexl,yl,x2,y2;xl=p.x-pl.x;2=p2.x-pl.x;yl=p.y-pl.y;y2=p2.y-pl.y;if(FC(xl*y2-x2*ylz0)=0)return0;if(MlN(
28、PI.x,p2.x)=p.x&p.x=MAX(pl.x,p2.x)&(MIN(pl.y,p2.y)=p.y&p.y=MAX(pl.y,p2.y)return1;elsereturn0;)7 .判断两线段是否相交语法：result=sectintersect(PointplzPointp2,Pointp3,Pointp4);参数：p4:两条线段的四个端点返回值：0：两线段不相交；1：两线段相交；2两线段首尾相接注意：pl!=p2;p3!=p4;源程序：#defineMIN(zy)(y?:y)typedefstructdoublex,y;Point;intlineintersect(Pointpl
29、,Pointp2,Pointp3,Pointp4)(Pointtpl,tp2,tp3;if(pl.x=p3.x&pl.y=p3.y)(pl.x=p4.x&pl.y=p4.y)I(p2.x=p3.x&p2.y=p3.y)(p2.x=p4.x&p2.y=p4.y)return2;快速排斥试验if(MIN(pl.x,p2.x)p3.x&p3.xMAX(pl.x,p2.x)&MIN(pl.y,p2.y)p3.yMAX(pl.yzp2.y)(MIN(Pl.x,p2.x)p4.x&p3.xMAX(pl.x,p2.x)&MIN(pl.y,p2.y)p3.y=0)return1;elsereturn0;8 .
30、判断线段与直线是否相交语法：result=lineintersectPointplzPointp2zPointp3,PointP4)；参数：pl、p2：线段的两个端点P3、p4：直线上的两个点返回值：0：线段直线不相交；1：线段和直线相交注意：如线段在直线上，返回1源程序：typedefstructdoublex,y;Point;intlineintersect(PointplzPointp2,Pointp3,Pointp4)(Pointtplztp2,tp3;tpl.x=pl.x-p3.x;tpl.y=pl.y-p3.y;tp2.x=p4.x-p3.x;tp2.y=p4.y-p3.y;tp3
31、.x=p2.x-p3.x;tp3.y=p2.y-p3.y;if(tpl.x*tp2.y-tpl.y*tp2.)*(tp2.x*tp3.y-tp2.y*tp3.x)=0)return1;elsereturn0;)9 .点到线段最短距离语法：result=mindistance(Pointpl,Pointp2zPointq);参数：pl、p2：线段的两个端点q：判断点返回值：点q到线段plp2的距离注意：需要math.h源程序：#defineMIN(zy)(xy?x:y)typedefstructdoublex,y;Point;doublemindistance(PointplzPointp2,P
32、ointq)intflag=l;doublek;Points;if(pl.x=p2.)s.x=pl.x;s.y=q.y;flag=O;if(pl.y=p2.y)$,x=q.x;s.y=pl.y;flag=O;if(flag)(k=(p2.y-pl.y)(p2.x-pl.x);s.x=(k*k*pl.+k*(q.y-pl.y)+q.x)(k*k+l);s.y=k*(s.-pl.x)+pl.y;)if(MIN(pl.xzp2.x)=s.x88S.x=MAX(pl.xzp2.)returnsqrt(q.x-s.x)*(q.x-s.x)+(q.y-s.y)*(q.y-s.y);elsereturnMI
33、N(sqrt(q.x-pl.x)*q.x-pl.)+(q.y-pl.y)*(q.y-pl.y),sqrt(q.x-p2.x)*(q.x-p2.x)+(q.y-p2.y)*(q.y-p2.y);)10 .求两直线的交点语法：result=mindistance(Pointpl,Pointp2,Pointq);参数：plvp4:直线上不相同的两点*p:通过指针返回结果返回值：1：两直线相交；2：两直线平行注意：如需要判断两线段交点，检验k和对应kl(注释中)的值是否在OF之间，用在o之间的那个求交点源程序：typedefstructdoublex,y;Point;intlinecorss(Poin
34、tplzPointp2,Pointp3zPointp4,Point*p)(doublek;同一直线if(p4.x-p3.x)*(pl.y-p3.y)-(p4.y-p3.y)*(pl.x-p3.x)=0&(p2.x-pl.x)*(pl.y-p3.y)-(p2.y-pl.y)*pl.x-p3.x)=0)return2；平行，不同一直线if(p4.y-p3.y)*(p2.x-pl.x)-(p4.x-p3.x)*(p2.y-pl.y)=0)return0;k=(p4.x-p3.x)*(pl.y-p3.y)-(p4.y-p3.y)*(pl.-p3,)(p4.y-p3.y)*(p2.x-pl.x)-(p4.x-p3.x)*(p2.y-ply);/kl=(p2.x-pl.x)*(pl.y-p3.y)-(p2.y-pl.y)*(pl.x-p3.x)(p4.y-p3.y)*(p2.x-pl.x)-(p4.x-p3.x)*(p2.y-pl.y);(*p).x=pl.x+k*(p2.
