ACM常用代码(1)

ACM小组内部预定函数数学问题：1.精度计算——大数阶乘2.精度计算——乘法（大数乘小数）3.精度计算——乘法（大数乘大数）4.精度计算——加法5.精度计算——减法6.任意进制转换7.最大公约数、最小公倍数8.组合序列9.快速傅立叶变换（FFT）10.Ronberg算法计算积分11.行列式计算12.求排列组合数字符串处理：1.字符串替换2.字符串查找3.字符串截取计算几何：1.叉乘法求任意多边形面积2.求三角形面积3.两矢量间角度4.两点距离（2D、3D）5.射向法判断点是否在多边形内部6.判断点是否在线段上7.判断两线段是否相交8.判断线段与直线是否相交9.点到线段最短距离10.求两直线的交点11.判断一个封闭图形是凹集还是凸集12.Graham扫描法寻找凸包数论：1.x的二进制长度2.返回x的二进制表示中从低到高的第i位3.模取幂运算4.求解模线性方程5.求解模线性方程组(中国余数定理)6.筛法素数产生器7.判断一个数是否素数图论：1.Prim算法求最小生成树2.Dijkstra算法求单源最短路径3.Bellman-ford算法求单源最短路径4.Floyd算法求每对节点间最短路径排序/查找：1.快速排序2.希尔排序3.选择法排序4.二分查找数据结构：1.顺序队列2.顺序栈3.链表4.链栈5.二叉树一、数学问题1.精度计算——大数阶乘语法：intresult=factorial(intn);参数：n：n的阶乘返回值：阶乘结果的位数注意：本程序直接输出n!的结果，需要返回结果请保留longa[]需要math.h源程序：intfactorial(intn){longa[10000];inti,j,l,c,m=0,w;a[0]=1;for(i=1;i=n;i++){c=0;for(j=0;j=m;j++){a[j]=a[j]*i+c;c=a[j]/10000;a[j]=a[j]%10000;}if(c0){m++;a[m]=c;}}w=m*4+log10(a[m])+1;printf(\n%ld,a[m]);for(i=m-1;i=0;i--)printf(%4.4ld,a[i]);returnw;}2.精度计算——乘法（大数乘小数）语法：mult(charc[],chart[],intm);参数：c[]：被乘数，用字符串表示，位数不限t[]：结果，用字符串表示m：乘数，限定10以内返回值：null注意：需要string.h源程序：voidmult(charc[],chart[],intm){inti,l,k,flag,add=0;chars[100];l=strlen(c);for(i=0;il;i++)s[l-i-1]=c[i]-'0';for(i=0;il;i++){k=s[i]*m+add;if(k=10){s[i]=k%10;add=k/10;flag=1;}else{s[i]=k;flag=0;add=0;}}if(flag){l=i+1;s[i]=add;}elsel=i;for(i=0;il;i++)t[l-1-i]=s[i]+'0';t[l]='\0';}3.精度计算——乘法（大数乘大数）语法：mult(chara[],charb[],chars[]);参数：a[]：被乘数，用字符串表示，位数不限b[]：乘数，用字符串表示，位数不限t[]：结果，用字符串表示返回值：null注意：空间复杂度为o(n^2)需要string.h源程序：voidmult(chara[],charb[],chars[]){inti,j,k=0,alen,blen,sum=0,res[65][65]={0},flag=0;charresult[65];alen=strlen(a);blen=strlen(b);for(i=0;ialen;i++)for(j=0;jblen;j++)res[i][j]=(a[i]-'0')*(b[j]-'0');for(i=alen-1;i=0;i--){for(j=blen-1;j=0;j--)sum=sum+res[i+blen-j-1][j];result[k]=sum%10;k=k+1;sum=sum/10;}for(i=blen-2;i=0;i--){for(j=0;j=i;j++)sum=sum+res[i-j][j];result[k]=sum%10;k=k+1;sum=sum/10;}if(sum!=0){result[k]=sum;k=k+1;}for(i=0;ik;i++)result[i]+='0';for(i=k-1;i=0;i--)s[i]=result[k-1-i];s[k]='\0';while(1){if(strlen(s)!=strlen(a)&&s[0]=='0')strcpy(s,s+1);elsebreak;}}4.精度计算——加法语法：add(chara[],charb[],chars[]);参数：a[]：被乘数，用字符串表示，位数不限b[]：乘数，用字符串表示，位数不限t[]：结果，用字符串表示返回值：null注意：空间复杂度为o(n^2)需要string.h源程序：voidadd(chara[],charb[],charback[]){inti,j,k,up,x,y,z,l;char*c;if(strlen(a)strlen(b))l=strlen(a)+2;elsel=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';elsex=a[i];if(j0)y='0';elsey=b[j];z=x-'0'+y-'0';if(up)z+=1;if(z9){up=1;z%=10;}elseup=0;c[k++]=z+'0';i--;j--;}if(up)c[k++]='1';i=0;c[k]='\0';for(k-=1;k=0;k--)back[i++]=c[k];back[i]='\0';}5.精度计算——减法语法：sub(chars1[],chars2[],chart[]);参数：s1[]：被减数，用字符串表示，位数不限s2[]：减数，用字符串表示，位数不限t[]：结果，用字符串表示返回值：null注意：默认s1=s2，程序未处理负数情况需要string.h源程序：voidsub(chars1[],chars2[],chart[]){inti,l2,l1,k;l2=strlen(s2);l1=strlen(s1);t[l1]='\0';l1--;for(i=l2-1;i=0;i--,l1--){if(s1[l1]-s2[i]=0)t[l1]=s1[l1]-s2[i]+'0';else{t[l1]=10+s1[l1]-s2[i]+'0';s1[l1-1]=s1[l1-1]-1;}}k=l1;while(s1[k]0){s1[k]+=10;s1[k-1]-=1;k--;}while(l1=0){t[l1]=s1[l1];l1--;}loop:if(t[0]=='0'){l1=strlen(s1);for(i=0;il1-1;i++)t[i]=t[i+1];t[l1-1]='\0';gotoloop;}if(strlen(t)==0){t[0]='0';t[1]='\0';}}6.任意进制转换语法：conversion(chars1[],chars2[],longd1,longd2);参数：s[]：原进制数字，用字符串表示s2[]：转换结果，用字符串表示d1：原进制数d2：需要转换到的进制数返回值：null注意：高于9的位数用大写'A'～'Z'表示，2～16位进制通过验证源程序：voidconversion(chars[],chars2[],longd1,longd2){longi,j,t,num;charc;num=0;for(i=0;s[i]!='\0';i++){if(s[i]='9'&&s[i]='0')t=s[i]-'0';elset=s[i]-'A'+10;num=num*d1+t;}i=0;while(1){t=num%d2;if(t=9)s2[i]=t+'0';elses2[i]=t+'A'-10;num/=d2;if(num==0)break;i++;}for(j=0;ji/2;j++){c=s2[j];s2[j]=s[i-j];s2[i-j]=c;}s2[i+1]='\0';}7.最大公约数、最小公倍数语法：resulet=hcf(inta,intb)、result=lcd(inta,intb)参数：a：inta，求最大公约数或最小公倍数b：intb，求最大公约数或最小公倍数返回值：返回最大公约数（hcf）或最小公倍数（lcd）注意：lcd需要连同hcf使用源程序：inthcf(inta,intb){intr=0;while(b!=0){r=a%b;a=b;b=r;}return(a);}lcd(intu,intv,inth){return(u*v/h);}8.组合序列语法：m_of_n(intm,intn1,intm1,int*a,inthead)参数：m：组合数C的上参数n1：组合数C的下参数m1：组合数C的上参数，递归之用*a：1～n的整数序列数组head：头指针返回值：null注意：*a需要自行产生初始调用时，m=m1、head=0调用例子：求C(m,n)序列：m_of_n(m,n,m,a,0);源程序：voidm_of_n(intm,intn1,intm1,int*a,inthead){inti,t;if(m10||m1n1)return;if(m1==n1){for(i=0;im;i++)couta[i]'';//输出序列cout'\n';return;}m_of_n(m,n1-1,m1,a,head);//递归调用t=a[head];a[head]=a[n1-1+head];a[n1-1+head]=t;m_of_n(m,n1-1,m1-1,a,head+1);//再次递归调用t=a[head];a[head]=a[n1-1+head];a[n1-1+head]=t;}9.快速傅立叶变换（FFT）语法：kkfft(doublepr[],doublepi[],intn,intk,doublefr[],doublefi[],intl,intil);参数：pr[n]：输入的实部pi[n]：数入的虚部n，k：满足n=2^kfr[n]：输出的实部fi[n]：输出的虚部l：逻辑开关，0FFT，1ifFTil：逻辑开关，0输出按实部/虚部；1输出按模/幅角返回值：null注意：需要math.h源程序：voidkkfft(pr,pi,n,k,fr,fi,l,il)intn,k,l,il;doublepr[],pi[],fr[],fi[];{intit,m,is,i,j,nv,l0;doublep,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;}fr[it]=pr[is];fi[it]=pi[is];}pr[0]=1.0;pi[0]=0.0;p=6.283185306/(1.0*n);pr[1]=cos(p);pi[1]=-sin(p);if(l!=0)pi[1]=-pi[1];for(i=2;i=n-1;i++){p=pr[i-1]*pr[1];q=pi[i-1]*pi[1];s=(pr[i-1]+pi[i-1])*(pr[1]+pi[1]);pr[i]=p-q;pi[i]=s-p-q;}for(it=0;it=n-2;it=it+2