NOIP复赛复习资料汇总.doc

NOIP复赛基础知识汇总（cxms）(一)Math库实用汇总1(二)Turbo Pascal过程与函数调用3(三)排序（快排、冒泡、堆排）：4(四)常用数据类型5(五)高精度5(六)常用算法7(七)普通树的遍历8(八)二叉树8(九)数论相关算法10(十)排列组合11(十一)图论12(一) Math库实用汇总使用方法：在程序头用Uses语句加载Math库例子：Program Ex_Math;Uses Math;BeginWriteln(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次方乘以xlog10 原型：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). 例子：varR: Real;beginR := 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:=arandom(j-i+1)+i; repeat while (aix while (ajx) do dec(j); /降序:xaj if (ij); if (lxj) then qsort(a,lx,j); if (irx) 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:=rii; j:=2*ii; while j=nn do begin if (jnn) and (rjrj+1) then j:=j+1; 小根堆:(jrj+1) if xrj else j:=nn+1; end; ri:=x; end;procedure heapsort(n:integer); 堆排序 for i:=n div 2 downto 1 do 建立初始堆，且产生最大值a1 heap(a,n,i); for i:=n downto 2 do 将当前最值交换到最终位置上，再对前i-1个数调整 begin temp:=a1; a1:=ai; ai:=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=array1.maxlen of integer;1高精度加法procedure plus ( a,b:hp; var c:hp); var i,len:integer;begin fillchar(c,sizeof(c),0); if a0b0 then len:=a0 else len:=b0; for i:=1 to len do begin inc(ci,ai+bi);if ci10 then begin dec(ci,10); inc(ci+1); end; 进位end; if clen+10 then inc(len); c0:=len;end;plus2高精度减法procedure substract(a,b:hp;var c:hp); var i,len:integer; begin fillchar(c,sizeof(c),0); if a0b0 then len:=a0 else len:=b0; for i:=1 to len do begin inc(ci,ai-bi); if ci1) and (clen=0) do dec(len); c0:=len; end;3高精度乘以低精度(1)procedure multiply(a:hp;b:longint;var c:hp); var i,len:integer; begin fillchar(c,sizeof(c),0); len:=a0; for i:=1 to len do begin inc(ci,ai*b); inc(ci+1,(ai*b) div 10); ci:=ci mod 10; end; inc(len); while (clen=10) do begin 处理最高位的进位 clen+1:=clen div 10; clen:=clen mod 10; inc(len); end; while (len1) and (clen=0) do dec(len); 若不需进位则调整len c0:=len; end;multiply(2)program jk;const maxn=1000;type hp=array0.maxn of longint;var i,j,n:longint; a:hp; b:longint;procedure mul(var h:hp;k:longint);/h:=h*kvar i:longint; begin for i:=0 to maxn do hi:=hi*k; for i:=0 to maxn-1 do begin hi+1:=hi+1+hi div 10; hi:=hi mod 10 end; end; begin a1:=100; /两个乘数 b:=888; mul(a,b); /求a:=a*b 即888*100 i:=maxn; while (i0) and (ai=0) do i:=i-1; for j:=i downto 1 do write(aj); /输出计算后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 a0 do for j:=1 to b0 do begin inc(ci+j-1,ai*bj); inc(ci+j,ci+j-1 div 10); ci+j-1:=ci+j-1 mod 10; end; len:=a0+b0+1; while (len1) and (clen=0) do dec(len); c0:=len; end;(2)var n1,n2,n3:string;function mul(n1,n2:string):string;var a,b,c:array1.200 of 0.9; lena,lenb,lenc,i,j,x:integer; s:string; ch:string;beginlena:=length(n1); lenb:=length(n2); for i:=1 to lena do alena-i+1:=ord(n1i)-ord(0); for i:=1 to lenb do blenb-i+1:=ord(n2i)-ord(0); for i:=1 to lena dobegin x:=0; for j:=1 to lenb do begin x := ai*bj+x div 10+ci+j-1; ci+j-1:=x mod 10; end; ci+j:= x div 10; end; lenc:=i+j; while (clenc=0) and (lenc1) do dec(lenc); for i:=lenc downto 1 do begin str(ci,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:=a0; d:=0; for i:=len downto 1 do begin d:=d*10+ai; ci:=d div b; d:=d mod b; end; while (len1) and (clen=0) then dec(len); c0:=len; end;(2)program jk;const maxn=1000;type hp=array0.maxn of longint;var i,j,n:longint; c:hp; b:longint; procedure devide(var h:hp;k:longint);/h:=h div kvar d,i,r:longint; begin r:=0; for i:=maxn downto 0 do begin d:=10*r+hi; hi:=d div k; r:=d mod k end; end; begin c1:=13; /被除数 b:=5; /除数 devide(c,b); /求c:=c div b 即13 div 5 i:=maxn; while (i0) and (ci=0) do i:=i-1; for j:=i downto 1 do write(cj); /输出计算后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:=a0;d0:=1; for i:=len downto 1 do begin multiply(d,10,d); d1:=ai; while(compare(d,b)=0) do 即d=b begin Subtract(d,b,d); inc(ci); end; end; while(len1)and(c.slen=0) do dec(len); c.len:=len; end;7.精确计算n!const max=10000; n=2000; var a:array1.maxof 0.9; i,j,k,x:integer;begin k:=1; ak:=1;a=1 for i:=2 to n doa1*2*3.*n begin x:=0;进位初始化 for j:=1 to k doa=a*i begin x:=x+aj*i; aj:=x mod 10;x:=x div 10 end; while x0 do 处理最高位的进位 begin k:=k+1;ak:=x mod 10;x:=x div 10 end end; for i:=k downto 1 do write(ai); 输出aend.(六) 常用算法（1）字符串匹配的KMP算法源程序procedure get_next(s:string; var next:inttype);var j,k:integer;begin j:=1; k:=0; next1:=0; while j=length(t) do if (k=0) or (tj=tk) then begin j:=j+1; k:=k+1; nextj:=k; end else k:=nextk;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 (jlength(t) then index:=i-length(t) else index:=0;end;(七) 普通树的遍历（1）深度优先遍历procedure tral(t,m) 递归访问以t为根结点的含m棵子树的过程beginif t nil then begin write(t.data, ); 访问根结点 for I:=1 to m do 前序遍历各子树tral(t.childI,m);end;end;（2）广度优先遍历Const n=100;Var hend,tail,I:integer; Q:array1.n of tree; t:tree; head,tail为队列的首尾指针,p为树的根结点Begin Tail:=1; head:=1; t:=p; 初始化 Qtail:=t; t进队 Tail:=tail+1; While (headtail) do 队列非空 Begin T:=qhead; 取出队首结点 Head:=head+1; Write(t.data, ); 访问某结点 For I:=1 to m do 该结点的所有子结点按顺序进队 If t.childInil then begin qtail:=t.childI; tail:=tail+1; end; End;End;(八) 二叉树二叉树的性质 性质1：在二叉树的第i层上至多有2(i-1)个结点（i=1）。 性质2：深度为k的二叉树至多有2k 1个结点（k=1）。 性质3：对任何一棵二叉树，如果其叶结点数为n0，度为2的结点数为n2，则一定满足：n0=n2+1。 性质4：具有n个结点的完全二叉树的深度为trunc(LOG2n)+1 2为底数，n为真数（2） 二叉树的存储结构 1.顺序存储结构：const m=树中结点数的上限;type node=record data:datatype; prt,lch,rch:0.m; end; treetype=array1.m of node;var tree:treetype; 2.链式存储结构，即单链表结构：type tree=node; node=record data:char; lchild,rchild:tree end;var bt:tree;或双链表结构：type tree=node; node=record data:char; lchild,rchild,father:tree end;var bt:tree;（3）二叉树的遍历(一) 先序遍历算法描述1.若二叉树为空则退出 否则: (1)访问处理根节点; (2)先序遍历左子树; (3)先序遍历右子树.源程序数组表示:procedure preorder(x:integer);begin if x0 then begin write(treex.data); preorder(treex.lch); preorder(treex.rch); end;end;链表表示:procedure preorder(tree:tree_point);begin if treenil then begin write(tree.data); preorder(tree.lch); preorder(tree.rch); end;end;(二) 中序遍历算法描述1.若二叉树为空则退出 否则: (1)中序遍历左子树; (2)访问处理根节点; (3)中序遍历右子树.源程序数组表示:procedure inorder(x:integer);begin if x0 then begin inorder(treex.lch); write(treex.data); inorder(treex.rch); end;end;链表表示:procedure inorder(tree:tree_point);begin if treenil then begin inorder(tree.lch); write(tree.data); inorder(tree.rch); end;end;(三) 后序遍历算法描述1.若二叉树为空则退出 否则: (1)后序遍历左子树; (2)后序遍历右子树; (3)访问处理根节点.源程序数组表示:procedure postorder(x:integer);begin if x0 then begin postorder(treex.lch); postorder(treex.rch); write(treex.data); end;end;链表表示:procedure postorder(tree:tree_point);begin if treenil then begin postorder(tree.lch); postorder(tree.rch); write(tree.data); end;end;（4）普通树转化为二叉树：输入格式： 顶点个数n (1=n=200) 以下n行其中第i行的元素以次为 结点i的数据值ai。以后各元素为结点i的儿子序列，以0结束。若ai后仅含一个0，则说明结点i为叶子结点。输入样例：18r 2 3 4 0a 5 6 0b 7 0c 8 9 10 0w 0x 11 12 0f 0s 13 14 0t 0u 0d 15 0e 0i 16 17 18 0j 0h 0m 0o 0n 0程序样例：fillchar(tree,sizeof(tree),0);readln(n);for k:=1 to n do begin read(treek.data); read(j); if j0 then begin treek.lch:=j; treej.prt:=k; repeat p:=j; read(j); if j0 then begin treep.rch:=j