《【数据结构】算法集锦》由会员分享，可在线阅读，更多相关《【数据结构】算法集锦（2页珍藏版）》请在金锄头文库上搜索。
1、 自考乐园-心境随缘，诚与天下自考人共勉！自考乐园-分享快乐，你的快乐老家！自考乐园-引领成功，你的精神乐园！ 自考乐园俱乐部，专注于自考，致力于成为全国最全，最优的自考学习交流，资料共享平台.俱乐部名称：自考乐园;俱乐部id：5346389（请牢记它哦在百度贴吧的搜索框中输入俱乐部id，可以直接进入俱 乐部）;俱乐部url地址：http:/ 【数据数据结结构构】 】算法集算法集锦锦一一数数论论算法算法 1 求两数的最大公约数 function gcd(a,b:integer):integer; begin if b=0 then gcd:=a else gcd:=gcd (b,a mod b
2、); end 2求两数的最小公倍数 function lcm(a,b:integer):integer; begin if a0 do inc(lcm,a); nd; 3素数的求法 A.小范围内判断一个数是否为质数： function prime (n: integer): Boolean; var I: integer; begin for I:=2 to trunc(sqrt(n) do if n mod I=0 then begin prime:=false; exit; end; prime:=true; end; B.判断longint范围内的数是否为素数（包含求50000以内的素数
3、表）： procedure getprime; var i,j:longint; p:array1.50000 of boolean; begin fillchar(p,sizeof(p),true); p1:=false; i:=2; while i=x then break else if x mod pri=0 then exit; prime:=true; end;prime2、图论图论算法算法 1最小生成树 A.Prim算法： procedure prim(v0:integer); var lowcost,closest:array1.maxn of integer; i,j,k,m
4、in:integer; begin for i:=1 to n do begin lowcosti:=costv0,i; closesti:=v0; end; for i:=1 to n-1 do begin 寻找离生成树最近的未加入顶点k min:=maxlongint; for j:=1 to n do if (lowcostj0) then begin min:=lowcostj; k:=j; end; lowcostk:=0; 将顶点k加入生成树 生成树中增加一条新的边k到closestk 修正各点的lowcost和closest值 for j:=1 to n do if costk,
5、j0 do begin i:=find(eq.v1);j:=find(eq.v2); if i0) then if (best=0) or (bi+ai,j0 then begin bbest_j:=best；markbest_j:=true; end; until best=0; end;bhf B.Floyed算法求解所有顶点对之间的最短路径： procedure floyed; begin for I:=1 to n do for j:=1 to n do if aI,j0 then pI,j:=I else pI,j:=0; pI,j表示I到j的最短路径上j的前驱结点 for k:=1
6、 to n do 枚举中间结点 for i:=1 to n do for j:=1 to n do if ai,k+aj,k0 then prei:=v0 else prei:=0; end; markv0:=true; repeat 每循环一次加入一个离1集合最近的结点并调整其他结点的参数 min:=maxint; u:=0; u记录离1集合最近的结点 for i:=1 to n do if (not marki) and (di0 then begin marku:=true; for i:=1 to n do if (not marki) and (au,i+du表示，则EeI = Ve
7、j; d. 边活动最晚开始时间 ElI, 若边I由表示，则ElI = Vlk wj,k; 若 Eej = Elj ，则活动j为关键活动，由关键活动组成的路径为关键路径。 求解方法： a. 从源点起topsort,判断是否有回路并计算Ve; b. 从汇点起topsort,求Vl; c. 算Ee 和 El;6拓扑排序 找入度为0的点，删去与其相连的所有边，不断重复这一过程。 例 寻找一数列，其中任意连续p项之和为正，任意q 项之和为负，若不存在则输出NO.7.回路问题 Euler回路(DFS) 定义：经过图的每条边仅一次的回路。（充要条件：图连同且无奇点） Hamilton回路 定义：经过图的每个
8、顶点仅一次的回路。 一笔画 充要条件：图连通且奇点个数为0个或2个。 9判断图中是否有负权回路 Bellman-ford 算法 xI,yI,tI分别表示第I条边的起点，终点和权。共n个结点和m条边。 procedure bellman-ford begin for I:=0 to n-1 do dI:=+infinitive; d0:=0; for I:=1 to n-1 do for j:=1 to m do 枚举每一条边 if dxj+tjdyj then dyj:=dxj+tj; for I:=1 to m do if dxj+tjdyj then return false else return true; end;以上资料由百度贴吧：以上资料由百度贴吧： -自考乐园俱乐部杨尚杰为你精心编辑自考乐园俱乐部杨尚杰为你精心编辑
