常用的100个经典算法.pdf

100 个基本算法 1.数论算法 求两数的最大公约数 function gcd(a,b:integer):integer; begin if b 0 then gcd: a else gcd: gcd (b,a mod b); end ; 求两数的最小公倍数 function lcm(a,b:integer):integer; begin if a b then swap(a,b); lcm: a; while lcm mod b 0 do inc(lcm,a); end; 素数的求法 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 以内的素数表）： procedure getprime; var i,j:longint; p:array[1..50000] of boolean; begin fillchar(p,sizeof(p),true); p[1]: false; i: 2; while i 50000 do begin if p[i] then begin j: i*2; while j 50000 do begin p[j]: false; inc(j,i); end; end; inc(i); end; l: 0; for i: 1 to 50000 do if p[i] then begin inc(l);pr[l]: i; end; end;{getprime} function prime(x:longint):integer; var i:integer; begin prime: false; for i: 1 to l do if pr[i] x then break else if x mod pr[i] 0 then exit; prime: true; end;{prime} 2． 3． 4.求最小生成树 A.Prim算法： procedure prim(v0:integer); var lowcost,closest:array[1..maxn] of integer; i,j,k,min:integer; begin for i: 1 to n do begin lowcost[i]: cost[v0,i]; closest[i]: v0; end; for i: 1 to n-1 do begin {寻找离生成树最近的未加入顶点k} min:maxlongint; for j: 1 to n do if (lowcost[j] min) and (lowcost[j] 0) then begin min: lowcost[j]; k: j; end; lowcost[k]: 0; {将顶点k加入生成树} {生成树中增加一条新的边k到closest[k]} {修正各点的lowcost和closest值} for j: 1 to n do if cost[k,j] lwocost[j] then begin lowcost[j]: cost[k,j]; closest[j]: k; end; end; end;{prim} B.Kruskal算法：(贪心) 按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。 function find(v:integer):integer; {返回顶点v所在的集合} var i:integer; begin i: 1; while (i n) and (not v i