信息学奥赛入门必读.doc

1、信息学入门必读首先，你必须知道：第一：信息学学的是什么？第二：你为什么而学信息学？关于第一个问题，我可以回答你。至于第二个问题，那就要问你自己了。：信息学学什么？：我个人认为：初等组合。这是信息学解题的思维方式。图论。主要是基础概念方面的，用于理解算法。数学问题。这类题目有一些考的是数学思维，其中有一部分是考创造能力的。：学习过程中要注意什么问题？： 认清自己的位置。也就是根据自己的学习目的，判断自己是什么水平，经过努力能到达什么水平。熟练的掌握自己使用的编程语言。常常看到有人问一些很简单的语法问题什么的，其实这些东西实在太基础了，只需要翻翻书就可以弄懂的。如果连编程语言都不了解，又怎么能够编

2、程呢？我这里说的编程语言指的是标准的程序设计语言，例如PASCAL， C/C+ 。 而一些集成开发环境(IDE)并不属于这个范围，例如DELPHI ， VB， VC 等。 一定要把一些基础打好，这个非常重要。所谓基础，就是一些基本的算法，例如：求最小公倍数，高精度等。再次强调一点：一定要重视基础！IOI2001金牌获得者毛子青前辈道出学好信息学的金言：提高正确率!其实第点说的 打好 基础的意思就是：对于基础的题目，一定要百分百正确！我在GDSOI2001中深刻的体会到 正确率 的内涵：满分 300 分的试题， 最高分只有159 ！而且能够有一题全对的人也没几个！要知道，如果有一半题目全对的话，

3、就已经有150 了！所以，我认为：简单的题目一定不能丢分，很难的题目不要花太多时间，能拿分就可以了。当然，这些建议是对于入门者来说的。要懂得利用网络资源。学会在网络上收集资料。但是有一点要注意：不要沉溺在网络上！：用什么编程语言，什么IDE 好？：我个人认为：编程语言：BASIC ：如果你是编程初学者，那么BASIC 是最适合的，但是这种语言不适合搞信息学。PASCAL：这个是最适合初学者学习的， 因为这种语言和 BASIC 一样简单易学， 而且现在国内中学生的竞赛资料都是用 PASCAL写的。C/C+ ：大学生基本都有这个的，参加ACM必学语言。C/C+ 里面有一些概念可能不太容易被初学编程

4、的中学生接受，而且如果用的不熟练是很容易出错的。不过，学过PASCAL的人要学 C/C+ 是很容易的，编程语言的学习是触类旁通的。IDE：PASCAL：建议初学者使用Turbo Pascal 7.0或者 Borland Pascal 7.0，是 DOS下的。要对调试的基本操作熟悉。以后到了高层次的竞赛，例如NOI ，是需要 freepascal的，而且是 Linux下的。不过虽然 IDE 变了，但是用几天就会熟悉的了。至于DELPHI ，有点大材小用的感觉。C/C+ ： GCC是首选， Turbo C+ 3.0也不错。要看写什么程序，对竞赛来说RHIDE +GCC是首选。学会选择适合自己的题目

5、来做！做题总结回头看看，这是我做题的一个习惯。但是选什么题目来做呢？相信这是很多初学者关心的问题。在此，我谈谈我的一些看法。首先，还是那句话：看看自己的位置。我认为：第一阶段：编程语言的学习。这个阶段并不需要找什么“竞赛题”，而是踏踏实实的把教材上每一章后面的练习认真地做几遍，最好没天都回头看看，不然会忘记的。不要认为后面的练习很简单，一定要认真做。基础的语言熟练了以后，还需要学一些高级一点的，但是这部分内容可以通过看别人的程序来学。比如说：有些 PASCAL书没有说 fillchar的用法，但是我看到很多高手的程序都把这个语句放在begin end.的开头部分，于是猜想（不是盲目的猜，而是根

6、据位置、单词构成等来猜）fillchar是用来初始化的，自己写了一个这样的程序来测试：program Test_Fillchar; const maxn=10;var a:array1.maxn of integer;i:integer;procedure PrintA;varj:Integer;beginfor j:=1 to maxndo write(aj:5);writeln;end;beginfor i:=1 to maxn do ai:=123;PrintA;fillchar(a,sizeof(a),0);PrintA;end.得到这样的屏幕输出：123123123123123123

7、 123 123123 1230000000000于是可以初步断定：fillchar(a,sizeof(a),0)是用来把数组a 制 0 的。当然fillchar的真正用法不只是这样的，这等到以后水平提高了就会明白的。第二阶段：基础算法。选题的方法有很多，可以选择书籍或者OIBH列出来的题目（ OIBH 过几天再放上一些基础算法的程序）来做，也可以在以后解其他题的过程“提炼”出属于基础算法的部分来做。我当初“做”的方法是：先自己想一篇，然后看看标准程序，对比一下优劣，取长补短，过两天再做一次。最好养成把一些不熟悉的算法隔几天再做一次的习惯。有的时候，某个算法在你学习的那天以及以后几天内可能很熟

8、悉，但是一段时间不用，很容易就忘或者不熟练。第三阶段：简单的深度搜索和广度搜索。 （以后再写，敬请留意基本算法讲座之 数学篇基本算法是解难题的基础，必须熟练掌握。这一讲将介绍跟数学密切相关的基本算法。（）素数数学类的基本算法大多数属于初等数论范畴，相当大一部分与素数有直接关系，因此素数是一个很基本又很重要的内容。我们先来看看怎么判断一个数是否素数。素数的定义为：如果一个数的正因子只有和这个数本身，那么这个数就是素数。根据定义，我们立即能得到判断一个数（大于 ) 是否素数的简单的算法：枚举到之间的整数，判断是否能整除。该算法的Pascal代码。如果 n 很大，那么上面的程序就要运行比较长的一段时

9、间，那么有没有更快一点的算法呢？回答是肯定的！因为如果 n 含有不为 1 和自身的因子，那么这些因子中必定有不大于 sqrt(n)的（假设 n 有因子 p， 1pn，如果 p sqrt(n) ，那么 n/p 也是 n 的因子，而且 1n/pn ，所以 n/p不大于 sqrt(n)）。于是我们可以改进上面的程序，得到另外一 个 Pascal 程序。容易知道这个算法的时间复杂度为O(sqrt(n)。（）因式分解因式分解的算法很简单，模拟手工分解的过程，我们得到分解n 的算法：枚举所有不大于n 的所有素数，判断这些素数能整除n 多少次。判断2 到 n 是否素数，总共要计算sqrt(2)+sqrt(3

10、)+sqrt(4)+sqrt(n)=n*sqrt(n)次，因此算法的时间复杂度可以粗略地认为是O(n*sqrt(n) 。事实上，我们有更好的算法。先看一个显而易见的结论：如果p 是能整除 n 的所有大于 1 的数中最小的，那么p 是 n 的一个素因子。基于这样一个结论，我们得到Pascal代码。（）公因子的数量问题描述：已知一个正整数N，问这个数有多少正公因子。算法分析： 最容易想到的算法是： 枚举 1.N ，看看有多少个数能整除N，这种算法的复杂度为O(N)。可以优化一下：如果 N有小于 SQRT( N ) 的因子 X，那么 N 必定有大于 SQRT( N ) 的因子 Y 与 X 对应，而且

11、 XY=N。所以我们只需要枚举1.SQRT( N )的数即可，还要考虑N 为完全平方数的特殊情况。程序： Pascal 。 上面这个算法的复杂度为O(sqrt(N) 。其实我们可以利用因式分解的方法来做。假设我们已经分解 N得到 N =(p1s1)*(p2s2).*(ppnumspnum)，其中 pi 为互不相同的素数，那么N的正因子的数量为(s1+1)*(s2+1)*(spnum+1)（具体怎么推导请参考组合数学教材中的母函数一章）：。（）最大公因式问题描述：已知两个正整数a 和(GCD是 Greatest Common Divisorb，求这两个数的最大公因数的缩写 )GCD( a , b

12、 )。算法分析：不妨设a=b，一种十分容易想到的算法是：枚举1 到a 的所有整数，在能同时整除a 和b 的数中取最大的。这个算法的时间复杂度为O(min(a,b)，当min(a,b)较大的时候程序要执行比较长的时间。我们可以利用初等数论中的一个定理：GCD( a , b ) = GCD( a , b-a ) = GCD( a , b-2*a ) = GCD( a , b-3*a ) = GCD( a , b moda )关于这个定理的具体证明，请参考初等数论书（或者初中数学竞赛中的数论相关章节）。下面给出利用这个定理来写的一个求最大公因式的程序，请读者仔细研究：Pascal 。此算法的时间复杂

13、度为 O(log(Max(a,b)。（推导过程请参考算法与数据结构教材）（）最小公倍数问题描述：已知两个正整数a 和 b，求这两个数的最小公倍数LCM ( a , b )。(LCM是 Least Common Multiply的缩写 )算法分析：直接利用公式：LCM ( a , b ) * GCD( a , b ) = a * b即可。（）进制转换我们平常计算都是用十进制数的，但是有的时候我们需要用到进制数、16 进制数等。一个 k进制的数可以表示为： (As-1 As-2A0)k = As-1 K(s-1) + As-2 K(s-2) + A0 K(0) ，记为 式，其中 0=AiK （I=

14、0,1,2.s-1）。对于一个已知的正整数n，如何得到 n 的 K 进制表示呢？换句话 说，我们就是要求出As-1 As-2 A0 来。具体的求解顺序是： 先求出 A0，然后是 A1 ，最后得到 An-1 。将 式等号两边同时取模k 得： n mod K = a0。得到 A0 以后， (n-A0) div K = As-1K(s-2) + As-2 K(s-3) + A1 K(0)，用与求 A0 同样的方法可以得到A1，然后是 A2 。Pascal 程序。运行这个程序，输入： 15516 就可以得到结果 9B（16 进制的 9B = 9*16+11=155 ）怎么进行任意进制间的数的转换呢？已知一个数正整数n 的 P 进制表示（ As-1As-2 A0），求n 的 Q进制表示（ Bl-1Bl-2B0）。一种简单的方法是：根据P 进制表示求出十进制的 n，然后再将n 转化为 Q进制表示即可。前面考虑的都是整数的问题，我们现在来看看怎么处理实有理数。由于实数跟整数的区别仅仅在于小数部分，所以现在只考虑实数r ，r满足 0 = r 1 的情况。定义r 的 K 进制表示为： r =（0.A1A2 A3As ）K = A1 K(-1) + A2 K(-2) + A3 K(-3). As K(-s)。求解顺序为： A1