ACM常用算法打印版.docx

上传人:p** 文档编号:336225 上传时间:2023-08-03 格式:DOCX 页数:25 大小:77.17KB
下载 相关 举报
ACM常用算法打印版.docx_第1页
第1页 / 共25页
ACM常用算法打印版.docx_第2页
第2页 / 共25页
ACM常用算法打印版.docx_第3页
第3页 / 共25页
ACM常用算法打印版.docx_第4页
第4页 / 共25页
ACM常用算法打印版.docx_第5页
第5页 / 共25页
ACM常用算法打印版.docx_第6页
第6页 / 共25页
ACM常用算法打印版.docx_第7页
第7页 / 共25页
ACM常用算法打印版.docx_第8页
第8页 / 共25页
ACM常用算法打印版.docx_第9页
第9页 / 共25页
ACM常用算法打印版.docx_第10页
第10页 / 共25页
亲,该文档总共25页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

《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

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > IT计算机 > 数据结构与算法

copyright@ 2008-2023 1wenmi网站版权所有

经营许可证编号:宁ICP备2022001189号-1

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。第壹文秘仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知第壹文秘网,我们立即给予删除!