有哪些信誉好的足球投注网站- 1、本文档共10页，可阅读全部内容。
- 2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
查看更多
NOIP2010 基础算法整理
NOIP2010 基础算法整理（Pascal 版） I
Koala.Guan 2010-10-7 修正
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]}
{修正各点的l
文档评论（0）