欢迎来到天天文库
浏览记录
ID:55594144
大小:161.50 KB
页数:55页
时间:2020-05-19
《算法大全(数据结构)(C版本).doc》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、算法大全(C,C++)一、数论算法1.求两数的最大公约数intgcd(inta,intb){intr;while(b!=0){r=a%b;a=b;b=r;}returna;}2.求两数的最小公倍数intlcm(inta,b);{returna*b/gcd(a,b);}3.素数的求法A.小范围内判断一个数是否为质数:boolprime(intn){inti;for(i=2;i2、lp[50001];memset(p,true,sizeof(p));p[1]=false;for(i=2;i<50001;i++){if(p[i]){for(j=i*2;j<50001;j+=i){p[j]=false;}}}二、图论算法1.最小生成树A.Prim算法:/*邻接矩阵cost[maxN][maxN]*/#definemaxLongInt#definemaxN10000intcost[maxN][maxN];//cost[i][i]=0;inttot;intlowcost[maxN],//点i到MST的当前最小距离,lowcost[i]==0表示/3、/点i已经加入MSTclosest[maxN];//点j到MST距离最小的边的另一个顶点prim(intv0,intn){inti,j,k,min;tot=0;for(i=0;i4、点k加入生成树//{生成树中增加一条新的边k到closest[k]}//{修正各点的lowcost和closest值}for(j=0;j5、v2为//边i所连接的两个顶点的序号,e[i].len为第I条边的长度intv1;intv2;intlen;}e[maxn*maxn/2];structvsets//森林集合{intv[maxn];//集合中的顶点intnum;//集合中树的个数}vset[maxn];intn;intfind(intv)//返回点v属于哪个森林集合{inti,j;for(i=0;i6、能生成返回true{inti,j,tot;//tot表示MST中所有边长度的总和intp,q;for(i=0;i0){if(q>=n*(n-1)/2)//n为顶点的数量,n*(n-1)/2为边的总数-》如果遍历所有边也无returnfalse;//法筛选出n-1条边,则不能生成最小生成树,返回false;i=find(e[q].v1);//返回点v1属于哪个7、森林集合j=find(e[q].v2);if(i!=j){tot+=e[q].len;for(intk=0;k8、{intbest,bes
2、lp[50001];memset(p,true,sizeof(p));p[1]=false;for(i=2;i<50001;i++){if(p[i]){for(j=i*2;j<50001;j+=i){p[j]=false;}}}二、图论算法1.最小生成树A.Prim算法:/*邻接矩阵cost[maxN][maxN]*/#definemaxLongInt#definemaxN10000intcost[maxN][maxN];//cost[i][i]=0;inttot;intlowcost[maxN],//点i到MST的当前最小距离,lowcost[i]==0表示/
3、/点i已经加入MSTclosest[maxN];//点j到MST距离最小的边的另一个顶点prim(intv0,intn){inti,j,k,min;tot=0;for(i=0;i4、点k加入生成树//{生成树中增加一条新的边k到closest[k]}//{修正各点的lowcost和closest值}for(j=0;j5、v2为//边i所连接的两个顶点的序号,e[i].len为第I条边的长度intv1;intv2;intlen;}e[maxn*maxn/2];structvsets//森林集合{intv[maxn];//集合中的顶点intnum;//集合中树的个数}vset[maxn];intn;intfind(intv)//返回点v属于哪个森林集合{inti,j;for(i=0;i6、能生成返回true{inti,j,tot;//tot表示MST中所有边长度的总和intp,q;for(i=0;i0){if(q>=n*(n-1)/2)//n为顶点的数量,n*(n-1)/2为边的总数-》如果遍历所有边也无returnfalse;//法筛选出n-1条边,则不能生成最小生成树,返回false;i=find(e[q].v1);//返回点v1属于哪个7、森林集合j=find(e[q].v2);if(i!=j){tot+=e[q].len;for(intk=0;k8、{intbest,bes
4、点k加入生成树//{生成树中增加一条新的边k到closest[k]}//{修正各点的lowcost和closest值}for(j=0;j5、v2为//边i所连接的两个顶点的序号,e[i].len为第I条边的长度intv1;intv2;intlen;}e[maxn*maxn/2];structvsets//森林集合{intv[maxn];//集合中的顶点intnum;//集合中树的个数}vset[maxn];intn;intfind(intv)//返回点v属于哪个森林集合{inti,j;for(i=0;i6、能生成返回true{inti,j,tot;//tot表示MST中所有边长度的总和intp,q;for(i=0;i0){if(q>=n*(n-1)/2)//n为顶点的数量,n*(n-1)/2为边的总数-》如果遍历所有边也无returnfalse;//法筛选出n-1条边,则不能生成最小生成树,返回false;i=find(e[q].v1);//返回点v1属于哪个7、森林集合j=find(e[q].v2);if(i!=j){tot+=e[q].len;for(intk=0;k8、{intbest,bes
5、v2为//边i所连接的两个顶点的序号,e[i].len为第I条边的长度intv1;intv2;intlen;}e[maxn*maxn/2];structvsets//森林集合{intv[maxn];//集合中的顶点intnum;//集合中树的个数}vset[maxn];intn;intfind(intv)//返回点v属于哪个森林集合{inti,j;for(i=0;i6、能生成返回true{inti,j,tot;//tot表示MST中所有边长度的总和intp,q;for(i=0;i0){if(q>=n*(n-1)/2)//n为顶点的数量,n*(n-1)/2为边的总数-》如果遍历所有边也无returnfalse;//法筛选出n-1条边,则不能生成最小生成树,返回false;i=find(e[q].v1);//返回点v1属于哪个7、森林集合j=find(e[q].v2);if(i!=j){tot+=e[q].len;for(intk=0;k8、{intbest,bes
6、能生成返回true{inti,j,tot;//tot表示MST中所有边长度的总和intp,q;for(i=0;i0){if(q>=n*(n-1)/2)//n为顶点的数量,n*(n-1)/2为边的总数-》如果遍历所有边也无returnfalse;//法筛选出n-1条边,则不能生成最小生成树,返回false;i=find(e[q].v1);//返回点v1属于哪个
7、森林集合j=find(e[q].v2);if(i!=j){tot+=e[q].len;for(intk=0;k8、{intbest,bes
8、{intbest,bes
此文档下载收益归作者所有