基本算法正式稿.docVIP

《基本算法正式稿》一、数论算法1．求两数的最大公约数function??gcd(a,b:integer):integer;??begin?????if?b=0?then?gcd:=a??????else?gcd:=gcd?(b,a?mod?b);??end?; 2．求两数的最小公倍数function??lcm(a,b:integer):integer;??begin????if?ab?then?swap(a,b);????lcm:=a;????while?lcm?mod?b0?do?inc(lcm,a);??end; 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以内的素数表）：????procedure?getprime;??????var?????????i,j:longint;????????p:array[1..50000]?of?boolean;???????begin?????????fillchar(p,sizeof(p),true);??p[1]:=false;??i:=2;??while?i50000?do?begin????if?p[i]?then?begin??????j:=i*2;??????while?j50000?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} 二、图论算法1．最小生成树??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;??beg