全国青少年信息学奥林匹克联赛NOI基础算法整理.pdfVIP

NOIP2010 基础算法整理（Pascal 版） I I. 排序算法 A. 快速排序(Quicksort) procedure qs(p,q:longint); var i,j,k,mid:longint; Begin mid:=a[(p+q) div 2];i:=p;j:=q; repeat while a[i]{!}mid do inc(i); while a[j]{!}mid do dec(j); if i=j{!} then begin k:=a[i];a[i]:=a[j];a[j]:=k; inc(i);dec(j); end; until ij; if pj then qs(p,j);{!} if iq then qs(i,q);{!} end; B. 堆排序(HeapSort) Procedure sift(i,m:longint); var k:longint; Begin a[0]:=a[i]; k:=2*i; {Son 1 of next storey.} while (k=m) do begin if (km) and (a[k]a[k+1]) theninc(k); {To find the maxnum of this storey.} if a[0]a[k] then begin a[i]:=a[k];i:=k;k:=2*i; end {Exchange.} else k:=m+1; {Break.} NOIP 2010 基础算法整理 - 1 - end; a[i]:=a[0]; {Place the correct leaf.} end; Begin readln(n); for i:= 1 to n do read(a[i]); for j:=n div 2 downto 1 do sift(j,n); {Arrange the tree.} for j:=n downto 2 do begin swap(1,j); {Make every leaf into the root.} sift(1,j-1); {Arrange the tree.} end; for i:= 1 to n-1 do write(a[i], ); writeln(a[n]); end. II. 数论算法 A. 最大公约数和最小公倍数 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 ab then swap(a,B); lcm:=a; while lcm mod b0 do inc(lcm,a); end; NOIP 2010 基础算法整理 - 2 - III.图论算法 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] the