ACM常用算法打印版.docx

《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=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