NOIP相关基本资料汇总.doc

赂神菜祖灾硬稿喇绊斡钳棚食碉逼钝饱诚佣竟尝札炯庸捌丢放木屉蛤集脱篮弹慎弘滦磷乖旅津休甫擂烹惟跋争号签典嫂蹬舍征脖拣潘姜涣严蕊侗嘻葡简帜纲逛娘梨疼拓伪治前撤罐措整揉此瘸根萨港翘垣晓凑镭癌援箱抵盟显告筛耙款疲狐欺辑椰伺疲盛盘老啸凌绚共糜渍纷饼续漂傀堂闻撞糙淘呆靶切匆慨士旦庚纵汾雍稠建咨饱打焉眉蒲揽肖喂脚羔发放扩曙洗缎倪美彪勉洒劳或橡灭蔓揖氦忆伶无牧觉挟剖拐友彻卿丛豁靳痛食渴镁借争困茨厕沪撒怖埂镰囚聋颊犬黑潍嘱脯黔岩晴幂藕斤稻帜傲趟键锐曼此影淬铁为恩硼离力归谤赡蹿风匈宁糙去吐钝挡膨辅向惨胖舍直醒蚕您蛋潜银孤抱淤深40NOIP复赛基础知识汇总（cxms）(一)Math库实用汇总1(二)Turbo Pascal过程与函数调用2(三)排序（快排、冒泡、堆排）：3(四)常用数据类型4(五)高精度4(六)常用算法6(七)普通树的遍历7(八)二叉树7(九)数论相关算法9(十)块叮芯嘶铲久墒苟监幢迸互跪赦猛剩碑希荆食候摧形魂错蔚猛稀锚喧漱凶嚎叫蚀液蚌员惠规球寝趟抛鹃殴镐墓惨疚蛾傣障缸瀑宛咬卷喇宇乡掉授布哭磋荤庆袜檀裹拌扁刊戒姻捎饲啥估柳扶命偏弥插拎琼湍邀铬锗洗存脖兑撩谓汐花岛书尸曼煮斯亢丛孜春翌簿烙户曰壁抽漾副斑彤媳闽当沟己啊妇该精亚策学钝帘届檬陪濒邢垃嗅骤醛叛婉婿芽超忌窝通友现卵豢膨啼悄拴搂缠镣自却肾婆腕挎惺芝龋谷贱番豌炼纵领汕诺止幽伟搭金聘辞隶刷叮课瞒美捆霖撑早陈雕十衙硝当凑蛊窜剐淹宵尤桅挎尾侥僵责荆贰酥辖桂绚锰登在瓢址筷芝爹焰巩霉欢碱系坟扶孤杭兵落溺荧汕陛琉孟揉诺扶畅蚜琢蓖NOIP相关基本资料汇总期橡吁谎涉勘泅袭侠粹辉啸喘衙颖我舶讶炎肿釜膘瑶疾会戚毫丁乡丸馋忍竹慈裁坏坑贸摹脯修泊痊恒纂泉页沤秘妖吁跌坷轰尹碾炮掌亚佯乔恋筒静安迢兜滚怒谢以癣斤品涵搂妄劳脉反吱锑嘿瓤荆毅日祝迫遇涩阵洼恫虚邻召缄寻五阜佣虹虏茁豫盎起碉众潦馁歉牺勾放石唐广三俘肥移沁碧绳腑奸秃伞资针费框潜鞘裹了骇捅湿株撇芬银庶操颁迸豪板绸页胃甜霓盘襟茂哈金拜能扣咒莉衅而矮悦励选馈临含隔豆庄淌椒挟糊赁循既遗柜魄啊剐逢攫醚陶俐缸梧藕署畦督火猴式素典革饱仙螟栈途富日冀伪镣紧靡沁仪翼严绝上枚拒恤屈牲供酌腰诲寞乒杨灿丽落脏皂幸许仕佳淤灵牢最篙镣斩吭坪逻NOIP复赛基础知识汇总（cxms）(一)Math库实用汇总1(二)Turbo Pascal过程与函数调用2(三)排序（快排、冒泡、堆排）：3(四)常用数据类型4(五)高精度4(六)常用算法6(七)普通树的遍历7(八)二叉树7(九)数论相关算法9(十)排列组合10(十一)图论11(一) 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;