ACM常用算法打印版.docx
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 .判断两线段是否相交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 .链栈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;j<=m;j+)(aU=aj*i+c;c=aO10000;aj=aO%10000;)if(c>O)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 .精度计算一一乘法(大数乘小数)语法：mult(charczchart,intm);参数：c:被乘数，用字符串表示，位数不限t：结果，用字符串表示m：乘数，限定10以内返回值：null注意：需要string.h源程序：voidmult(charczchartJntm)inti,lzkzflagzadd=O;chars100;l=strlen(c);for(i=0;i<l;i+)sl-i-l=ci-,O'for(i=0;i<l;i+)(k=si*m+add;if(k>=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;i<l;i+)tl-l-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;i<alen;i+)for(j=O;j<blen;j+)resij=(ai-'O')*(bj-,O,);for(i=alen-l;i>=O;i-)(for(j=blen-lJ>=Oj-)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<k;i+)resulti+="O'for(i=k-l;i>=0;i-)si=resultk-l-i;sk=,O,;while(l)(if(strlen(s)!=strlen(a)&&sO='O')strcpyszs+l);elsebreak;)4 .精度计算加法语法：add(charazcharb,chars);参数：a：被乘数，用字符串表示，位数不限b：乘数，用字符串表示，位数不限t：结果，用字符串表示返回值：null注意：空间复杂度为o(n2)需要string.h源程序：voidadd(chara,charbzcharback)(intij,k,up,x,y,z,l;char*c;if(strlena>strlen(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(i<0)x=,0,;elsex=ai;if(j<O)y='0'elsey=bj;z=x-'0'+y-,0,;if(up)z+=l;if(z>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-;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<O)slk+=10;slk-l-=l;k-;while(ll>=0)tll=slll;ll-;loop:if(t0=,0,)(Il=StrIen(Sl);for(i=O;i<ll-l;i+)ti=ti+l;tl-l='0'gotoloop;)ifstrlen(t)=O)tO=,Otl=,O')6任意进制转换语法：conversion(charslzchars2Jongdl,longd2);参数：s【l：原进制数字，用字符串表示s2:转换结果，用字符串表示dl：原进制数d2：需要转换到的进制数返回值：null注意：高于9的位数用大写7VZ表示，2、16位进制通过验证源程序：voidconversion(charszchars2JongdiJongd2)(longizjnum;charc;num=0;for(i=0;si!='0'i+)(if(si<=,9,Sasi>='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;j<i/2;j+)c=$20；s2j=s(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,inthead)参数：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(ml<011ml>nl)return;if(ml=nl)(for(i=0;i<m;i+)cout<<ai<<<,;/输出序列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
