信息学奥赛入门必读

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

2、如果连编程语言都不了解，又怎么能够编程呢？我这里说的编程语言指的是标准的程序设计语言，例如PASCAL C/C+。而一些集成开发环境（IDE）并不属于这个范围，例如 DELPHI，VB，VC等。3. 一定要把一些基础打好，这个非常重要。所谓基础，就是一些基本的算法，例如：求最小公倍 数，高精度等。再次强调一点：一定要重视基础！ ！4. 101'2001金牌获得者毛子青前辈道岀学好信息学的金言：提高正确率！其实第3点说的"打好"基础的意思就是：对于基础的题目一定要百分百正确！我在GDSOI'2001中深刻的体会到"正确率"的内涵：满分300

3、分的试题，最高分只有159 ！而且能够有一题全对的人 也没几个！要知道，如果有一半题目全对的话，就已经有150 了！所以，我认为：简单的题目一定不能丢分，很难的题目不要花太多时间，能拿分就可以了。当然，这些建议是对于入门者来说的。5 要懂得利用网络资源。学会在网络上收集资料。但是有一点要注意： 不要沉溺在网络上！Q:用什么编程语言，什么 IDE好？A:我个人认为：编程语言：BASIC :如果你是编程初学者，那么 BASIC是最适合的，但是这种语言不适合搞信息学。PASCAL这个是最适合初学者学习的，因为这种语言和BASIC 一样简单易学，而且现在国内中学生的竞赛资料都是用PASCAL写的。C/

4、C+ :大学生基本都有这个的，参加ACM必学语言。C/C+里面有一些概 念可能不太容易被初学编程的中学生接受，而且如果用的不熟练是很容易出错的。不过，学过PASCAL的人要学C/C+是很容易的，编程语言的学习是触类旁通的。IDE:PASCAL建议初学者使用 Turbo Pascal 7.0 或者Borland Pascal 7.0 ，是DOS下的。要对调试的 基本操作熟悉。以后到了高层次的竞赛，例如N0I，是需要freepascal的，而且是Linux下的。不过虽然IDE变了，但是用几天就会熟悉的了。至于DELPHI，有点大材小用的感觉。C/C+ : GCC是首选，Turbo C+ 3.0 也

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

6、高手的程序都把这个语句放在 begin end.的 开头部分，于是猜想（不是盲目的猜，而是根据位置、单词构成等来猜）fillchar是用来初始化的，自己写了一个这样的程序来测试：program Test_Fillchar; const maxn=10; var a:array1.maxn of integer; i:integer; procedure PrintA; var j:Integer; begin for j:=1 to maxn do write(aj:5); writeln; end;begin for i:=1 to maxn do ai:= 123; PrintA;fill

7、char(a,sizeof(a),0); PrintA; end.得到这样的屏幕输出:123 123123 123123123 123 123 123 12300 0 00 0 000 0于是可以初步断定：fillchar(a,sizeof(a),0)是用来把数组a制0的。当然fillchar 的真正用法不只是这样的，这等到以后水平提高了就会明白的。第二阶段：基础算法。选题的方法有很多，可以选择书籍或者OIBH列出来的题目(OIBH过几天再放上一些基础算法的程序)来做，也可以在以后解其他题的过程“提炼”岀属于基础算法的部分来做。我当初“做”的 方法是：先自己想 一篇，然后看看标准程序，对比一下

8、优劣，取长补短，过两天再做一次。最好养 成把一些不熟悉的算法隔几天再做一次的习惯。有的时候，某个算法在你学习的那天以及以后几天内可能很熟悉，但是一段时间不用，很容易就忘或者不熟练。第三阶段：简单的深度搜索和广度搜索。(以后再写，敬请留意基本算法讲座之数学篇基本算法是解难题的基础，必须熟练掌握。这一讲将介绍跟数学密切相关的基本算法。(1) 素数数学类的基本算法大多数属于初等数论范畴，相当大一部分与素数有直接关系，因此素数是一 个很基本又很重要的内容。我们先来看看怎么判断一个数是否素数。素数的定义为：如果一个数的正因子只有1和这个数 本身，那么这个数就是素数。根据定义，我们立即能得到判断一个数N

9、(大于1 )是否素数的简单的算法：枚举2到N1之间的整数，判断是否能整除N。该算法的Pascal代码。如果n很大，那么上面的程序就要运行比较长的一段时间，那么有没有更快一点的算法呢？回 答是肯定的！因为如果 n含有不为1和自身的因子，那么这些因子中必定有不大于sqrt(n)的(假设n有因子p， 1<p<n，如果pv=sqrt(n)，那么p就不大于 sqrt(n)，如果 p> sqrt(n)，那么n/p也 是n的因子，而且1<n/p<n，所以n/p不大于sqrt(n)。于是我们可以改进上面的程序，得到另外 一个Pascal程序。容易知道这个算法的时间复杂度为O(sq

10、rt(n)。(2) 因式分解因式分解的算法很简单，模拟手工分解的过程，我们得到分解n的算法：枚举所有不大于n的所有素数，判断这些素数能整除n多少次。判断2到n是否素数，总 共要计算sqrt(2)+sqrt (3)+sqrt+sqrt(n)<=n*sqrt(n) 次，因此算法的时间复杂度可以粗略地认为是O(n*sqrt(n)。事实上，我们有更好的算法。先看一个显而易见的结论：如果p是能整除n的所有大于1的数中最小的，那么p是n的一个素因子。基于这样一个结论，我们得到Pascal代码。(3) 公因子的数量问题描述：已知一个正整数N,问这个数有多少正公因子。算法分析：最容易想到的算法是：枚举1

11、.N，看看有多少个数能整除 N,这种算法的复杂度为 0( N)。 可以优化一下：如果 N有小于SQRT( N )的因子X，那么N必定有大于SQRT( N )的因子Y与X对应， 而且XY=N所以我们只需要枚举1.SQRT( N )的数即可，还要考虑 N为完全平方数的特殊情况。程序：Pascal。上面这个算法的复杂度为O(sqrt(N)。其实我们可以利用因式分解的方法来做。假设我们已经分解 N得到 N =(p1As1)*(p2As2).*(ppnumAspnum)，其中 pi为互不相同 的素数，那么N的正因子的数量为(具体怎么推导请参考组合数学教材中的母函数一章)：(s1+1)*(s2+1)*(s

12、pnum+1)。(4) 最大公因式问题描述：已知两个正整数a和b,求这两个数的最大公因数GCD( a , b )。(GCD是 Greatest Common Divisor 的缩写)算法分析：不妨设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 )

13、关于这个定理的具体证明，请参考初等数论书(或者初中数学竞赛中的数论相关章节)。下面给出利用这个定理来写的一个求最大公因式的程序，请读者仔细研究：Pascal。此算法的时间复杂度为O(log(Max(a,b)。(推导过程请参考算法与数据结构教材)(5) 最小公倍数问题描述：已知两个正整数a和b,求这两个数的最小公倍数LCM ( a , b )。(LCM是 Least Common Multiply 的缩写)算法分析：直接利用公式：LCM ( a , b ) * GCD( a , b ) = a * b即可。(6) 进制转换我们平常计算都是用十进制数的，但是有的时候我们需要用到2进制数、16进制数

14、等。一个k进制的数可以表示为：(As-1 As-2 AO)k = As-1 KA(s-1) + As-2 KA(s-2) + AO KA(0)，记为<1>式，其中0<=Ai<K (l=0,1,2.s-1)。对于一个已知的正整数n，如何得到n的K进制表示呢？换句话 说，我们就是要求出 As-1 As-2A0来。具体的求解顺序是：先求出A0,然后是A1 ，最后得到An-1。将<1>式等号两边同时取模 k得：n modK = a0。得到A0以后，(n-A0) div K = As-1 KA(s-2) + As-2 KA(s-3) + A1 0(0)，用与求A0同样

15、的方法可以得到 A1，然后是A2。Pascal程序。运行这个程序，输入： 15516就可以得到结果9B (16进制的9B = 9*16+1仁155 )怎么进行任意进制间的数的转换呢？已知一个数正整数n的P进制表示(As-1As-2A0)，求n的Q进制表示(BI-1BI-2B0)。一种简单的方法是：根据 P进制表示求出十进制的 n,然后再将 n转化为Q进制表示即可。前面考虑的都是整数的问题，我们现在来看看怎么处理实有理数。由于实数跟整数的区别仅仅在于小数部分，所以现在只考虑实数 r, r满足0 <= r <1的情况。定义r的K进制表示为：r = (0.A1 A2 A3 As ) K = A1 0(-1) + A2 KA(-2) + A3 0(-3).As O(-s)。求解顺序为： A1、A2As。