复赛复习资料汇总.docx

NOIP复赛基础知识汇总（cxms）
(一) Math库实用汇总 1
(二) Turbo Pascal过程与函数调用 3
(三) 排序（快排、冒泡、堆排）： 4
(四) 常用数据类型 5
(五) 高精度 5
(六) 常用算法 7
(七) 普通树的遍历 8
(八) 二叉树 8
(九) 数论相关算法 10
(十) 排列组合 11
(十一) 图论 12
(一) Math库实用汇总
使用方法：在程序头用Uses语句加载Math库
例子：
Program Ex_Math;
Uses Math;
Begin
Writeln(hypot(3,4));
End.
函数介绍：
hypot
原型：function hypot(x:float;y:float):float
功能：返回直角三角形中较长边的长度，也就是sqrt(sqr(x)+sqr(y))
ceil
原型：function ceil(x:float):Integer
功能：返回比参数大的最小整数
引发错误：在x超出Integer的范围时会引发溢出错误
floor
原型：function floor(x:float):Integer
功能：返回比参数小的最大整数
引发错误：在x超出Integer的范围时会引发溢出错误
power
原型：function power(base:float;exponent:float):float
功能：返回base的exponent次方
引发错误：在base为负数且exponent为小数时
intpower
原型：function intpower(base:float;const exponent:Integer):float
功能：返回base的exponent次方
ldexp
原型：function ldexp(x:float;const p:Integer):float
功能：返回2的p次方乘以x
log10
原型：function log10(x:float):float
功能：返回x的常用对数
log2
原型：function log2(x:float):float
功能：返回x以2为底的对数
logn
原型：function logn(n:float;x:float):float
功能：返回x以n为底的对数
Max
原型：function Max(a:Integer;b:Integer):Integer
function Max(a:Int64;b:Int64):Int64
function Max(a:Extended;b:Extended):Extended
功能：返回a与b中较大的一个
Min
原型：function Min(a:Integer;b:Integer):Integer
function Min(a:Int64;b:Int64):Int64
function Min(a:Extended;b:Extended):Extended
功能：返回a与b中较小的一个
arcsin
原型：function arcsin(x:float):float
功能：返回x的反正弦值，返回的是弧度指单位
arccos
原型：function arccos(x:float):float
功能：返回x的反余弦值，返回的是弧度指单位
tan
原型：function tan(x:float):float
功能：返回x的正切值，x以弧度为单位
cotan
原型：function cotan(x:float):float
功能：返回x的余切值，x以弧度为单位
arcsinh
原型：function arcsinh(x:float):float
功能：返回双曲线的反正弦
arccosh
原型：function arccosh(x:float):float
功能：返回双曲线的反余弦
arctanh
原型：function arctanh(x:float):float
功能：返回双曲线的反正切
sinh
原型：function sinh(x:float):float
功能：返回双曲线的正弦
cosh
原型：function sinh(x:float):float
功能：返回双曲线的正弦
tanh
原型：function sinh(x:float):float
功能：返回双曲线的正切
cycletorad
原型：function cycletorad(cycle:float):float
功能：返回圆的份数转换成弧度之后的值
degtorad
原型：function degtorad(deg:float):float
功能：返回角度转换成弧度之后的值
radtocycle
原型：function radtocycle(rad:float):float
功能：返回弧度转换成圆的份数之后的值
radtodeg
原型：function radtodeg(rad:float):float
功能：返回弧度转换成角度之后的值
MaxValue
原型：function maxvalue(const data:Array[] of float):float
function maxvalue(const data:Array[] of Integer):Integer
function maxvalue(const data:PFloat;const N:Integer):float
function maxvalue(const data:PInteger;const N:Integer):Integer
功能：返回数组中的最大值
MinValue
原型：function minvalue(const data:Array[] of float):float
function minvalue(const data:Array[] of Integer):Integer
function minvalue(const data:PFloat;const N:Integer):float
function MinValue(const Data:PInteger;const N:Integer):Integer
功能：返回数组中的最小值
sum
原型：function sum(const data:Array[] of float):float
function sum(const data:PFloat;const N:LongInt):float
功能：求数组中所有数之和
sumsandsquares
原型：procedure sumsandsquares(const data:Array[] of float;var sum:float;
var sumofsquares:float)
procedure sumsandsquares(const data:PFloat;const N:Integer;
var sum:float;var sumofsquares:float)
功能：将数组中的数求和放入num中，求平方和放入sumofsquares中
**
原型：function operator **(float,float):float(bas:float;expo:float):float
function operator **(Int64,Int64):Int64(bas:Int64;expo:Int64):Int64
功能：同等于Power，这是乘方的操作符
具体例子可参看oi压缩包
(二) Pascal过程与函数调用
Abs
语法 Function Abs (r：Real)：Real;
Function Abs (r：Integer)：Integer;
Abs返回参数的绝对值。函数结果说明与参数类型（Real或Integer）相同。
ArcTan
语法 Funtion ArcTan（R：Real）：Real;
说明 ArcTan返回参数的正切值。
语法 Function Chr（I: Integer）;
说明 Chr返回出I序数值所对应的ASCII字符。
Concat
语法 Function Concat（S1,S2,…Sn）：String;
说明 Concat将任意多个字符串联在一起，返回所有字符串的联接，如果联接后的字符长度大于255，Turbo Pascal出现运行错误。
Copy
语法 Function Copy（S：string;
P,L：integer）：String；
说明 Copy 返回字符串中第P个字符开始的L个字符。
Cos
语法 Function Cos（R：Real）：Real;
说明 Cos返回R的余弦值。
Dec
语法 Procedure Dec（Var x：Scalar;
n：LongInt）；
说明 Dec是变量x减去n。若省略n，则x减去1。
Delete
语法 Procedure Delete(S：String;
P,L:Integer);
说明 Delete 删除字符串S中从第P个字符开始的L个字符。
Dispose
语法 Procedure Dispose（P：Pointer）；
说明 释放由指针变量设定的堆存贮区域，Dispose与命令New联合使用。
Eof
语法 Function Eof（F:File）：Boolean；
说明 当F文件指针到达文件尾时，Eof返回TRUE。
Eoln
语法 Function Eoln（F:File）：Boollean;
说明 当F文件指针到达一行的尾（由回车符和换行符表示）或文件尾时，Eoln返回TURE.
Exit
语法 Procedure Exit；
说明 Exit使程序从当前执行的块中退出。
Exp
语法 Function Exp（R：Real）：Real；
说明 Exp返回R的以e为底的幂。
Halt
语法 Procedure Halt；
说明 Halt中断程序的执行。
Hi
语法 Function Hi（I：Integer）：Byte；
说明 Hi返回整数I的高位字节。
Inc
语法 Procedure Inc（Var x; n：LongInt）；
说明 Inc为变量x加上n的值（x+n）。若参数表中缺省n，则x加1（x+1）。
Insert
语法 Procedure Insert（Source：string）
Var Target:string；
Index：Integer）；
说明 Insert将字符串Source插入到字串Target的Index处。
Int
语法 Function Int（R：Real）：Integer;
说明 Int返回实数R的整数部分。
Length
语法 Function Length（S：String）：Integer;
说明 Length返回字符串S的长度。
Ln
语法 Function Ln（Var R：Real）：Real；
说明 Ln返回实数R的自然对数。
Lo
语法 Lo（I:Integer）：Byte；
说明 Lo返回整数I的低位字节。
Odd
语法 Function Odd（I：Integer）：Boolean；
说明 当I为奇数时Odd返回TRUE，当I为偶数时返回为FALSE。
语法 Function Pi：Real；
说明 Pi返回数字常量。设数据的精度依赖于是否用了8087。
Pos
语法 Function Pos（Subs,S：String）：Integer;
说明 Pos返回字串SubS在字符串S中的位置。若S中未找到Subs，Pos返回值为0。
语法 Function Random（I:word）：word；
Function Random:Real;
说明 Random返回Turbo Pascal产生的一个随机数。若指定一个整数参数的话，Random返回一个大于或等于0，且小于该参数的整数，若不指定整数，Random返回一个大于或等于0，且小于1的实数。
Randomize
语法 Function Randomize;
说明 Randomize初始化随机数产生程序。其基数存放在长整型变量Randseed中。
Round
语法 Function Round（R：Real）：LongInt;
说明 Round将实数R四舍五入取整并返回。
Sin
语法 sin（R:Real）：Real；
说明 Sin返回R的正弦值。

Sizeof
语法 Function Sizeof(var Variable)：word;
说明 Sizeof返回一个变量或一个数据类型所需的字节数。
Sqr
语法 Function Sqr（R:Real）：Real；
说明 Sqr返回R的平方值。
Sqrt
语法 Function Sqrt（R:Real）：Real；
说明 Sqrt返回R的平方根
Str
语法 Str(I：Integer；[:Length,]Var S：String)；
Procedure Str（R: Real；[：length：Decimals,]）Var S: String)；
说明 Str将一个实数或一个整数转换为一个字符串。
Succ
语法 Function Succ（S:scalar）：Integer；
说明 Succ将任一标量值后移一个。
Swap
语法 Function Swap（I：Integer）：Integer；
说明 Swap将一个整数的高位字节和低位字节交换，例如：如果I等于00FFh，Swap返回FF00h。
Trunc
语法 Function Trunc（R: Real）：Integer；
说明 Trunc返回R的整数部分，结果必须在合法的整数范围内。
Upcase
语法 Function Upcase(C:char)：char
说明 如果C为小写字母Upcase返回C的大写值。
Val
语法 Procedure Val （S：String；Var R：Real；Var Code：Integer）；
Procedure Val （S：String；Var I：Integer Var Code：Integer）；
说明 Val将S转换为一个数字值（R或I）。如果转换为成功Turbo Pascal置Code为0，如果失败Code包含一个整数，它表示字符串中发生错误的字符。

取小数函数frac(x)
定义：function Frac(X: Real): Real; 注意：X 是实型表达式. 结果返回 X 的小数部分; 也就是说，Frac(X) = X - Int(_X). 例子：
var
R: Real;
begin
R := Frac(123.456); { 0.456 }
R := Frac(-123.456); { -0.456 }
end.
(三) 排序（快排、冒泡、堆排）：
快速排序 不稳定
[算法描述]
设有一无序数组a有n个元素.
1.以数组a的中点元素为参考值;
2.将中点左边大于(或小于)参考值的与中点右边小于(或大于)参考值的元素互换位置;
3.对中点左边的元素执行快排操作;
4.对中点右边的元素执行快排操作.

[源程序]
procedure qsort(var a:arraytype; lx,rx:longint);
var i,j,t,x:longint;
begin
i:=lx; j:=rx;
x:=a[random(j-i+1)+i];
repeat
while (a[i]<x) do inc(i); //降序:a[i]>x
while (a[j]>x) do dec(j); //降序:x>a[j]
if (i<=j) then
begin
t:=a[i]; a[i]:=a[j]; a[j]:=t; //如果是为记录数组排序的话,t必须是记录类型的
inc(i); dec(j);
end;
until (i>j);
if (lx<j) then qsort(a,lx,j);
if (i<rx) then qsort(a,i,rx);
end;
堆排序 不稳定
procedure heap(var r:arrtype;nn,ii:integer); {该过程为调整为大根堆的过程，大根堆排序后是 min to max }
var x,i,j:integer;
begin
i:=ii;
x:=r[ii];
j:=2*ii;
while j<=nn do
begin
if (j<nn) and (r[j]<r[j+1]) then j:=j+1; {小根堆:(j<nn) and (r[j]>r[j+1])}
if x<r[j] then begin r[i]:=r[j]; i:=j; j:=j*2; end {小根堆:x>r[j]}
else j:=nn+1;
end;
r[i]:=x;
end;

procedure heapsort(n:integer); {堆排序}
for i:=n div 2 downto 1 do {建立初始堆，且产生最大值a[1]}
heap(a,n,i);
for i:=n downto 2 do {将当前最值交换到最终位置上，再对前i-1个数调整}
begin
temp:=a[1]; a[1]:=a[i]; a[i]:=temp;
heap(a,i-1,1);
end;
(四) 常用数据类型
Byte 0 .. 255 1
Shortint -128 .. 127 1
Smallint -32768 .. 32767 2
Word 0 .. 65535 2
Integer either smallint, longint or int64 size 2,4 or 8
Longint -2147483648 .. 2147483647 4
Int64 -9223372036854775808 .. 9223372036854775807 8
QWord 0 .. 18446744073709551615 8
结论,FP中最佳类型当属longint可以有正负数,速度一流~若要节约,则可以试试word,不推荐Integer
(五) 高精度
高精度数的定义：
type
hp=array[1..maxlen] of integer;
1．高精度加法
procedure plus ( a,b:hp; var c:hp);
var i,len:integer;
begin
fillchar(c,sizeof(c),0);
if a[0]>b[0] then len:=a[0] else len:=b[0];
for i:=1 to len do begin
inc(c[i],a[i]+b[i]);
if c[i]>10 then begin dec(c[i],10); inc(c[i+1]); end; {进位}
end;
if c[len+1]>0 then inc(len);
c[0]:=len;
end;{plus}
2．高精度减法
procedure substract(a,b:hp;var c:hp);
var i,len:integer;
begin
fillchar(c,sizeof(c),0);
if a[0]>b[0] then len:=a[0] else len:=b[0];
for i:=1 to len do begin
inc(c[i],a[i]-b[i]);
if c[i]<0 then begin inc(c[i],10);dec(c[i+1]); end;
while (len>1) and (c[len]=0) do dec(len);
c[0]:=len;
end;

3．高精度乘以低精度
(1)
procedure multiply(a:hp;b:longint;var c:hp);
var i,len:integer;
begin
fillchar(c,sizeof(c),0);
len:=a[0];
for i:=1 to len do begin
inc(c[i],a[i]*b);
inc(c[i+1],(a[i]*b) div 10);
c[i]:=c[i] mod 10;
end;
inc(len);
while (c[len]>=10) do begin {处理最高位的进位}
c[len+1]:=c[len] div 10;
c[len]:=c[len] mod 10;
inc(len);
end;
while (len>1) and (c[len]=0) do dec(len); {若不需进位则调整len}
c[0]:=len;
end;{multiply}
(2)
program jk;
const maxn=1000;
type hp=array[0..maxn] of longint;
var i,j,n:longint; a:hp; b:longint;

procedure mul(var h:hp;k:longint);
//h:=h*k
var i:longint;
begin
for i:=0 to maxn do h[i]:=h[i]*k;
for i:=0 to maxn-1 do
begin
h[i+1]:=h[i+1]+h[i] div 10;
h[i]:=h[i] mod 10
end;
end;

begin
a[1]:=100; //两个乘数
b:=888;
mul(a,b); //求a:=a*b 即888*100
i:=maxn;
while (i>0) and (a[i]=0) do i:=i-1;
for j:=i downto 1 do write(a[j]); //输出计算后a的值
writeln;
end.

4．高精度乘以高精度
(1)
procedure high_multiply(a,b:hp; var c:hp);
var i,j,len:integer;
begin
fillchar(c,sizeof(c),0);
for i:=1 to a[0] do
for j:=1 to b[0] do begin
inc(c[i+j-1],a[i]*b[j]);
inc(c[i+j],c[i+j-1] div 10);
c[i+j-1]:=c[i+j-1] mod 10;
end;
len:=a[0]+b[0]+1;
while (len>1) and (c[len]=0) do dec(len);
c[0]:=len;
end;

(2)
var n1,n2,n3:string;
function mul(n1,n2:string):string;
var a,b,c:array[1..200] of 0..9;
lena,lenb,lenc,i,j,x:integer;
s:string; ch:string;
begin
lena:=length(n1); lenb:=length(n2);
for i:=1 to lena do a[lena-i+1]:=ord(n1[i])-ord('0');
for i:=1 to lenb do b[lenb-i+1]:=ord(n2[i])-ord('0');
for i:=1 to lena do
begin
x:=0;
for j:=1 to lenb do
begin
x := a[i]*b[j]+x div 10+c[i+j-1];
c[i+j-1]:=x mod 10;
end;
c[i+j]:= x div 10;
end;
lenc:=i+j;
while (c[lenc]=0) and (lenc>1) do dec(lenc);
for i:=lenc downto 1 do
begin
str(c[i],ch);
s:=s+ch;
end;
mul:=s;
end;

begin
assign(input,'input.dat');reset(input);
assign(output,'output.dat');rewrite(output);
readln(n1); readln(n2);
n3:=mul(n1,n2);
write(n3);
close(input);close(output);
end.

5．高精度除以低精度
(1)procedure devide(a:hp;b:longint; var c:hp; var d:longint);
{c:=a div b; d:= a mod b}
var i,len:integer;
begin
fillchar(c,sizeof(c),0);
len:=a[0]; d:=0;
for i:=len downto 1 do begin
d:=d*10+a[i];
c[i]:=d div b;
d:=d mod b;
end;
while (len>1) and (c[len]=0) then dec(len);
c[0]:=len;
end;

(2)
program jk;
const maxn=1000;
type hp=array[0..maxn] of longint;
var i,j,n:longint; c:hp; b:longint;

procedure devide(var h:hp;k:longint);
//h:=h div k
var d,i,r:longint;
begin
r:=0;
for i:=maxn downto 0 do
begin
d:=10*r+h[i];
h[i]:=d div k;
r:=d mod k
end;
end;

begin
c[1]:=13; //被除数
b:=5; //除数
devide(c,b); //求c:=c div b 即13 div 5
i:=maxn;
while (i>0) and (c[i]=0) do i:=i-1;
for j:=i downto 1 do write(c[j]); //输出计算后c的值
writeln;
end.

6．高精度除以高精度
procedure high_devide(a,b:hp; var c,d:hp);
var
i,len:integer;
begin
fillchar(c,sizeof(c),0);
fillchar(d,sizeof(d),0);
len:=a[0];d[0]:=1;
for i:=len downto 1 do begin
multiply(d,10,d);
d[1]:=a[i];
while(compare(d,b)>=0) do {即d>=b}
begin
Subtract(d,b,d);
inc(c[i]);
end;
end;
while(len>1)and(c.s[len]=0) do dec(len);
c.len:=len;
end;
7.精确计算n!
const max=10000; n=2000;
var a:array[1..max]of 0..9;
i,j,k,x:integer;
begin
k:=1; a[k]:=1;{a=1}
for i:=2 to n do{a←1*2*3….*n}
begin
x:=0;{进位初始化}
for j:=1 to k do{a=a*i}
begin
x:=x+a[j]*i; a[j]:=x mod 10;x:=x div 10
end;
while x>0 do {处理最高位的进位}
begin
k:=k+1;a[k]:=x mod 10;x:=x div 10
end
end;
for i:=k downto 1 do write(a[i]); {输出a}
end.
(六) 常用算法
（1）字符串匹配的KMP算法
[源程序]
procedure get_next(s:string; var next:inttype);
var
j,k:integer;
begin
j:=1;
k:=0;
next[1]:=0;
while j<=length(t) do
if (k=0) or (t[j]=t[k]) then
begin
j:=j+1;
k:=k+1;
next[j]:=k;
end
else k:=next[k];
end;

function index(s,t):integer; //求模式串t在主串s中的位置
var
next:inttype;
i,j:integer;
begin
get_next(t,next);
i:=1;
j:=1;
while (i<=length(s)) and (j<=length(t)) do
if (j=0) or (s[i]=t[j]) then
begin
i:=i+1;
j:=j+1;
end
else j:=next[j];
if j>length(t) then index:=i-length(t)
else index:=0;
end;
(七) 普通树的遍历
（1）深度优先遍历
procedure tral(t,m) {递归访问以t为根结点的含m棵子树的过程}
begin
if t <>nil then begin
write(t^.data,’ ’); {访问根结点}
for I:=1 to m do {前序遍历各子树}
tral(t^.child[I],m);
end;
end;
（2）广度优先遍历
Const n=100;
Var hend,tail,I:integer;
Q:array[1..n] of tree;
t:tree; {head,tail为队列的首尾指针,p为树的根结点}
Begin
Tail:=1; head:=1; t:=p; {初始化