cc算法实例.docx

C C++算法实例C C++,算法实例ー、数论算法1.求两数的最大公约数 function gcd(a,b:integer):integer; beginif b=0 then gcd:=a else gcd:=gcd (b, a mod b); end ;2,求两数的最小公倍数 function 1cm(a,b:integer):integer; beginif a0 do inc(1cm, a); end;3•素数的求法A.小范围内判断ー个数是否为质数: function prime (n: integer): Boolean; var I: integer;beginfor I:=2 to trunc(sqrt(n)) do if n mod 1=0 then begin prime:=false; exit;end;prime:=true;end;B,判断longint范围内的数是否为素数（包含求50000以内的素数表）： procedure getprime;vari,j:longint;p:array[1..50000] of boolean; beginfillchar(p, sizeof(p), true);p[l]:=false;i :=2;while i<50000 do begin if p[i] then begin j：=i*2;while j<50000 do beginp[j]:=false;inc(j, i);end;end;inc(i);end;1:=0;for i:=l to 50000 do if p[i] then begin inc(1);pr[1]:=i;end;end;{getprime)function prime(x:longint):integer; var i:integer;beginprime :=ia_tse;for i:=1 to 1 doif pr[i]>=x then breakelse if x mod pr[i]=0 then exit;prime:=true;end;{prime}二、图论算法1 .最小生成树A. Prim 算法:procedure prim(vO:integer);varlowcost,closest:array[1.. maxn] of integer;1, j, k, min: integer;beginfor i:=1 to n do beginlowcost[i]:=cost[vO, i];closest[i]:=v0;end;for i:=l to n-l do begin{寻找离生成树最近的未加入顶点k}min:=maxlongint;for j:=1 to n doif (lowcost[j]0) then begin min:=lowcost[j];k:=j;end;lowcost[k]:=0;{将顶点k加入生成树}｛生成树中增加一条新的边k到closest0]｝｛修正各点的lowcost和closest值｝for j:=1 to n doif cost[k,j]

function find (v: integer): integer;｛返回顶点 v 所在的集合｝var i:integer;begin1 :=1;while (iく=n) and (not v in vset[i]) do inc(i);if iく=n then find:=i else find:=0;end;procedure kruskal;vartot, i, j:integer;beginfor i:=l to n do vset [i]:=[i];｛初始化定义n个集合,第I个集合包含一个元素1｝p：=n-l; q:=l ； tot:=0;｛p为尚待加入的边数,q为边集指针｝ sort;｛对所有边按权值递增排序,存于e[口中,与e[I].v2为边I所连接的两个顶点的序号,e[I].len为第I条边的长度｝ while p>0 do begini :=find(e[q]. vl); j:=find(e[q]. v2);if iOj then begin inc (tot, e[q]. len);vset[i]:=vset[i]+vsetLj」;vset[j]:=[];dec(p);end;inc (q);end;writein(tot); end;2 .最短路径A.标号法求解单源点最短路径: vara:array[1.. maxn,1.. maxn] of integer;b:array[1.. maxn] of integer;｛b[i]指顶点i到源点的最短路径｝ mark:array[1.. maxn] of boolean;procedure bhf; varbest,best_j:integer;beginfillchar(mark, sizeof(mark), false);mark[l]:=true; b[l]:=0;｛1为源点｝repeatbest:=0;for i:=l to n doIf mark[i] then ｛对每ー个已计算出最短路径的点｝for j:=1 to n doif (not mark[j]) and (a[i, j]>0) thenif (best=0) or (b[i]+a[i, j]0 then beginb [best_j]:=best； mark[best j]:=true;end;until best=0;end;{bhf}B. Floyed算法求解所有顶点对之间的最短路径: procedure floyed;beginfor I:=1 to n dofor j:=l to n doif a[I, j]>0 then p[I, j]:=I else p[I, j]:=0;{p[L j]表示 I 至!J j 的最短路径上j的前驱结点} for k:=l to n do {枚举中间结点} for i:=1 to n do for j:=1 to n doif a[i, k]+a[j, k]0 then pre[i]:=v0 else pre[i]:=0;end;mark[v0]:=true;repeat ｛每循环一次加入一个离1集合最近的结点并调整其他结点的参数｝min:=maxint; u:=0;｛u记录离1集合最近的结点｝for i:=1 to n doif (not mark[i]) and (d[i]0 then beginmark[u]:=true;for i:=1 to n doif (not mark[i]) and (a[u, i]+d[u]

a.顶点事件最早发生时间 Ve[j], Ve [j]=max{Ve [j]+ w[I, j]},其中 Ve (1)=0;b.顶点事件最晚发生时间 VI [j]= min{ Vl[j]- w[I, j]],其中 VI (n)= Ve (n);c.边活动最早开始时间Ee[I],若边I由くj, k＞表示,则Ee[I]= Ve[j];d.边活动最晚开始时间若边I由くj,k＞表示,则E1[I]=VI [k]- w[j, k];若Ee[j]= El[j],则活动j为关键活动,由关键活动组成的路径为关键路径求解方法:a.从源点起topsort,判断是否有回路并计算Ve;b.从汇点起topsort,求VI;c,算 Ee 和 E1;6 .拓扑排序找入度为〇的点,删去与其相连的所有边,不断重复这ー过程例寻找ー数列,其中任意连续p项之和为正,任意q项之和为负,若不存在则输出N0.7 .回路问题Euler 回路(DFS)定义:经过图的每条边仅一次的回路充要条件:图连同且无奇点)Hamilton 回路定义：经过图的每个顶点仅一次的回路ー笔画充要条件：图连通且奇点个数为〇个或2个9 .判断图中是否有负权回路Bellman-ford算法t[l]分别表示第I条边的起点,终点和权。