noip复习资料.docx
- 文档编号:748443
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:35
- 大小:31.34KB
noip复习资料.docx
《noip复习资料.docx》由会员分享,可在线阅读,更多相关《noip复习资料.docx(35页珍藏版)》请在冰点文库上搜索。
noip复习资料
noip2007pascal语言及算法复习资料
第一章pascal的函数与技巧
一、常用函数与过程
*abs(x)取x的绝对值,结果可为整型或实型。
*frac(x)取x的小数部分,结果为实型。
*int(x)取x的整数部分,结果为实型。
*trunc(x)取x的整数部分,结果为整型。
*random(x)在[0,x)之间的整数中随机找一个整数,结果为整型。
*round(x)对x四舍五入取整数部分。
*exp(x)求ex的值。
*ln(x)求logex的值。
*copy(str,n1,n2)从字符串str中取从第n1个字符开始长度为n2个字符的子串,如果n1大于s的长度,则返回空字符串。
如果指定的n2大于第n1个字符后剩下的字符数,则返回剩下的字符串。
*val(str,int,code)将字串str转为数值型数据存入int,如果字符串无效,其中非法字符的下标放在code中;否则,code为零。
*pos(substr,str)查找substr是否为str的子串,若是则返回substr在str中的起始位置,若否则返回0。
*str(num,str)将num表达式转成字符串str。
*delete(str,n1,n2)从原字符串str删去一个从n1开始长度为n2的子串,如果n1比str长,不删除任何字符。
如果指定的n2大于从第n1个字符后剩下的字符数,则删除剩余部分。
*insert(source:
string;vars:
string;index:
integer)source是字符串表达式。
S是任意长度的字符串变量。
Index是整型表达式。
过程insert把字符串source插入字符串s中第index个字符开始的位置上。
二、小技巧
1.Ord(‘0’)=48;ord(‘A’)=65;ord(‘a’)=97;chr(32)=‘’;chr(33)=‘!
’;
2.求x^yexp(y*ln(x))
3.求x的n次方根exp(1/n*ln(x))
4.规定false=0,true=1;
5.复赛测试一般使用64MB内存空间
6.在FreePascal中,在程序结束之前一定要用close关闭input和output,否则输出文件可能不能被正确的写入。
尤其是程序非正常结束之前(如halt)也要关闭。
7.复赛使用的是fp1.0语言环境fp2.0的编译器测试,fp1.0环境下乘方x^y可以直接表示成x**y,fp2.0环境下乘方x^y要表示成x**y必须在程序开头包含usemath。
所以复赛时,注意要么不用**,要么不要忘掉包含usemath语句。
8.数据类型
整数
类型
值域
长度
(以字节为单位)
备注
byte
0…255
1
标准类型
shortint
-128…128
1
integer
-32768…32767
2
Word
0…65635
2
longint
-2147483648…2147483647
4
实数
Real
10-38…1038(精度11~12位)
6
Single
1.5*10-45…3.4*1038(精度7~8位)
4
数据处理方式{$n+}
Duble
5.0*10-324…1.7*10308(精度15~16位)
8
Comp
-9.2*1018…9.2*1018(精度19~20位)
8
extended
1.9*10-4951…1.1*104932(精度19~20位)
10
FP新增的数据类型
Int64整数类型-9223372036854775808~9223372036854775807占8个字节
QwordInt64的无符号整数类型0~18446744073709551615占8个字节
注意:
1.int64不是有序类型,所以不能作为for循环的循环变量。
2.直接给一个int64类型的变量赋值一个超过longint范围的整数是不合法的,例如:
定义a为int64类型,有如下语句:
a:
=8000000000;编译就通不过。
类似的,以下三条语句也通不过编译:
a:
=2*4000000000;
a:
=800000*10000;
a:
=a*8000000000;
这是因为fp在表达式的计算过程中用来存储整数的最大默认类型为longint,而不是int64。
当表达式的中间值超过longint时,fp会用实型来储存中间值,而实型是不能直接赋给整型的。
解决方法:
分成两步赋值,先执行a:
=1;然后执行a:
=a*800000*10000;需要强调的是,第二步赋值中一定要把8000000000拆成若干个不超过longint型的整数的和或乘积。
9.halt程序结束;break退出所在循环;exit退出所在过程(如在主程序中和halt的一样)
第二章重要定理和公式
一、常见递推关系
1.Fibonacci数列a
(1)=1;a
(2)=1;a(n)=a(n-1)+a(n-2);
2.catalan数(1,1,2,5,14,42,132......)
考虑具有n个结点不同形态的二叉树的个数H(n)
H(0)=1;
H(n)=H(0)H(n-1)+H
(1)H(n-2)+......+H(n-2)H
(1)+H(n-1)H(0) ;
或H(n)=(1/(n+1))*c(n,2n)
3.错位排列
n!
[1-1/1!
+1/2!
-...+(-1)n/n!
]
D(n)=(n-1)(D(n-1)+D(n-2))(n>2)D
(1)=0,D
(2)=1
二、图论与计算几何
1.度边定理:
sigemadi=2*E
2.海伦公式:
令p=(a+b+c)/2 ,则s=sqrt(p*(p-a)*(p-b)*(p-c));
三、排列组合公式
P(n,m)=n!
/m!
C(n,m)=n!
/(n-m)!
/m!
四、集合、数列公式
等差数列的通项公式:
an=a1+(n-1)d
求和公式:
sn=n*(a1+an)/2 ;
等比数列的通项公式:
an=a1*qn-1
求和公式:
Sn=[a1*(1-qn)]/(1-q)
集合容斥公式:
|A∪B∪C|=|A|+|B|+|C|-(|A∩B|+|A∩C|+|B∩C|)+|A∩B∩C|
五、其他公式
换底公式logex=log10x/log10e
费马小定理:
若n是素数,则对所有不被n整除的a即(a 推论若n是素数,则对任意小于n的整数a,有an≡a(modn). 第三章基本算法模块 一、数论算法 1.求两数的最大公约数 function gcd(a,b: integer): integer; begin if b=0 then gcd: =a else gcd: =gcd (b,a mod b); end ; 2.求两数的最小公倍数 function lcm(a,b: integer): integer; begin if a lcm: =a; while lcm mod b>0 do inc(lcm,a); end; 3.素数的求法 A.小范围内判断一个数是否为质数: function prime (n: integer): Boolean; var I: integer; begin for I: =2 to trunc(sqrt(n)) do if n mod I=0 then begin prime: =false; exit; end; prime: =true; end; B.判断longint范围内的数是否为素数(包含求50000以内的素数表): procedure getprime; var i,j: longint; p: array[1..50000] of boolean; begin fillchar(p,sizeof(p),true);p[1]: =false;i: =2; while i<50000 do begin if p[i] thenbegin j: =i*2; while j<50000 do begin p[j]: =false; inc(j,i); end; end; inc(i); end; l: =0; for i: =1 to 50000 do if p[i] then begin inc(l);pr[l]: =i; end; end;{getprime} function prime(x: longint): integer; var i: integer; begin prime: =false; for i: =1 to l do if pr[i]>=x then break else if x mod pr[i]=0 then exit; prime: =true; end;{prime} 二、图论算法 1.最小生成树 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: =lowcost[j]; k: =j; end; lowcost[k]: =0; {将顶点k加入生成树} {生成树中增加一条新的边k到closest[k]} {修正各点的lowcost和closest值} for j: =1 to n do if cost[k,j] lowcost[j]: =cost[k,j]; closest[j]: =k; end; end; end;{prim} B.Kruskal算法: (贪心) 按权值递增顺序删去图中的边,若不形成回路则将此边加入最小生成树。 function find(v: integer): integer; {返回顶点v所在的集合} var i: integer; begin i: =1; while (i<=n) and (not v in vset[i]) do inc(i); if i<=n then find: =i else find: =0; end; procedure kruskal; var tot,i,j: integer; begin for i: =1 to n do vset[i]: =[i];{初始化定义n个集合,第I个集合包含一个元素I} p: =n-1; q: =1; tot: =0; {p为尚待加入的边数,q为边集指针} sort; {对所有边按权值递增排序,存于e[I]中,e[I].v1与e[I].v2为边I所连接的两个顶点的序号,e[I].len为第I条边的长度} while p>0 do begin i: =find(e[q].v1);j: =find(e[q].v2); if i<>j then begin inc(tot,e[q].len); vset[i]: =vset[i]+vset[j];vset[j]: =[]; dec(p); end; inc(q); end; writeln(tot); end; 2.最短路径 A.标号法求解单源点最短路径: var a: array[1..maxn,1..maxn] of integer; b: array[1..maxn] of integer; {b[i]指顶点i到源点的最短路径} mark: array[1..maxn] of boolean; procedure bhf; var best,best_j: integer; begin fillchar(mark,sizeof(mark),false); mark[1]: =true; b[1]: =0;{1为源点} repeat best: =0; for i: =1 to n do If mark[i] then {对每一个已计算出最短路径的点} for j: =1 to n do if (not mark[j]) and (a[i,j]>0) then if (best=0) or (b[i]+a[i,j] best: =b[i]+a[i,j]; best_j: =j; end; if best>0 then begin b[best_j]: =best;mark[best_j]: =true; end; until best=0; end;{bhf} B.Floyed算法求解所有顶点对之间的最短路径: procedure floyed; begin for I: =1 to n do for j: =1 to n do if a[I,j]>0 then p[I,j]: =I else p[I,j]: =0; {p[I,j]表示I到j的最短路径上j的前驱结点} for k: =1 to n do {枚举中间结点} for i: =1 to n do for j: =1 to n do
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- noip 复习资料