奥林匹克信息学竞赛教程
过程和函数
　　　　　　
信息学入门必读
　　首先，你必须知道：
第一：信息学学的是什么？
第二：你为什么而学信息学？ 　　
　　关于第一个问题，我可以回答你。至于第二个问题，那就要问你自己了。
Ｑ：信息学学什么？
Ａ：我个人认为： 　　
１．　初等组合。这是信息学解题的思维方式。 　　
２．　图论。主要是基础概念方面的，用于理解算法。 　　
３．　数学问题。这类题目有一些考的是数学思维，其中有一部分是考创造能力的。
Ｑ：学习过程中要注意什么问题？
１．　认清自己的位置。也就是根据自己的学习目的，判断自己是什么水平，经过努力能到达什么水平。
２．　熟练的掌握自己使用的编程语言。常常看到有人问一些很简单的语法问题什么的，其实这些东西实在太基础了，只需要翻翻书就可以弄懂的。如果连编程语言都不了解，又怎么能够编程呢？我这里说的编程语言指的是标准的程序设计语言，例如 PASCAL， C/C++。 而一些集成开发环境 (IDE)并不属于这个范围，例如 DELPHI， VB， VC等。
３．　一定要把一些基础打好，这个非常重要。所谓基础，就是一些基本的算法，例如：求最小公倍数，高精度等。
　　 再次强调一点： 一定要重视基础！！！
４．　 IOI'2001金牌获得者毛子青前辈道出学好信息学的金言：
　　　　　提高正确率 !
其实第３点说的 &打好 &基础的意思就是：对于基础的题目，一定要百分百正确！我在 GDSOI'2001中深刻的体会到 &正确率 &的内涵：满分 300分的试题，最高分只有 159！而且能够有一题全对的人也没几个！要知道，如果有一半题目全对的话，就已经有 150了！所以，我认为：简单的题目一定不能丢分，很难的题目不要花太多时间，能拿分就可以了。当然，这些建议是对于入门者来说的。
５．要懂得利用网络资源。学会在网络上收集资料。但是有一点要注意：
不要沉溺在网络上！
Ｑ：用什么编程语言，什么 IDE好？
Ａ：我个人认为：
编程语言： 　　
BASIC ：如果你是编程初学者，那么 BASIC是最适合的，但是这种语言不适合搞信息学。
PASCAL：这个是最适合初学者学习的，因为这种语言和 BASIC一样简单易学，而且现在国内中学生的竞赛资料都是用 PASCAL写的。
C/C++ ：大学生基本都有这个的，参加 ACM必学语言。 C/C++里面有一些概 念可能不太容易被初学编程的中学生接受，而且如果用的不熟练是很容易出错的。不过，学过 PASCAL的人要学 C/C++是很容易的，编程语言的学习是触类旁通的。
PASCAL：建议初学者使用 Turbo Pascal 7.0或者 Borland Pascal 7.0，是 DOS下的。要对调试的基本操作熟悉。以后到了高层次的竞赛，例如 NOI，是需要 freepascal的，而且是 Linux下的。不过虽然 IDE变了，但是用几天就会熟悉的了。至于 DELPHI，有点大材小用的感觉。
C/C++ ： GCC是首选， Turbo C++ 3.0也不错。要看写什么程序，对竞赛来说 RHIDE +GCC是首选。
学会选 择适合自己的题目来做！
　　做题－总结－回头看看，这是我做题的一个习惯。但是选什么题目来 做呢？相信这是很多初学者关心的问题。在此，我谈谈我的一些看法。
　　首先，还是那句话：看看自己的位置。我认为：
第一阶段：编程语言的学习。
　　 这个阶段并不需要找什么“竞赛题”，而是踏踏实实的把教材上每一章后面的练习认真地做几遍，最好没天都回头看看，不然会忘记的。不要认为后面的练习很简单，一定要认真做。基础的语言熟练了以后，还需要学一些高级一点的，但是这部分内容可以通过看别人的程序来学。比如说：有些PASCAL书没有说fillchar的用法，但是我看到很多高手的程序都把这个语句放在begin end.的开头部分，于是猜想（不是盲目的猜，而是根据位置、单词构成等来猜）fillchar是用来初始化的，自己写了一个这样的程序来测试：
program Test_F
const maxn=10;
var a:array[1..maxn]
procedure PrintA;
for j:=1 to maxn do write(a[j]:5);
for i:=1 to maxn do a[i]:=123;
fillchar(a,sizeof(a),0);
　　 得到这样的屏幕输出：
　　 于是可以初步断定：fillchar(a,sizeof(a),0)是用来把数组a制0的。当然fillchar的真正用法不只是这样的，这等到以后水平提高了就会明白的。
第二阶段：基础算法。
　　 选题的方法有很多，可以选择书籍或者OIBH列出来 的题目（OIBH过几天再放上一些基础算法的程序）来做，也可以在以后解其他题的过程“提炼”出属于基础算法的部分来做。我当初“做”的方法是：先自己想一篇，然后看看标准程序，对比一下优劣，取长补短，过两天再做一次。最好养成把一些不熟悉的算法隔几天再做一次的习惯。有的时候，某个算法在你学习的那天以及以后几天内可能很熟悉，但是一段时间不用，很容易就忘或者不熟练。
第三阶段：简单的深度搜索和广度搜索。……（以后再写，敬请留意
基本算法讲座 之 数学篇
　　基本算法是解难题的基础，必须熟练掌握。这一讲将介绍跟数学密切相关的基本算法。
（１）素数
　　数学类的基本算法大多数属于初等数论范畴，相当大一部分与素数有直接关系，因此素数是一个很基本又很重要的内容。
　　 我们先来看看怎么判断一个数是否素数。素数的定义为：如果一个数的正因子只有１和这个数本身，那么这个数就是素数。根据定义，我们立即能得到判断一个数Ｎ（大于１)是否素数的简单的算法：枚举２到Ｎ－１之间的整数，判断是否能整除Ｎ。该算法的
　　 如果n很大，那么上面的程序就要运行比较长的一段时间，那么有没有更快一点的算法呢？回答是肯定的！因为如果n含有不为1和自身的因子，那么这些因子中必定有不大于sqrt(n)的（假设n有因子p，1&p&n，如果p&=sqrt(n)，那么p就不大于sqrt(n)，如果p&sqrt(n)，那么n/p也是n的因子，而且1&n/p&n，所以n/p不大于sqrt(n)）。于是我们可以改进上面的程序，得到另外一个
程序。容易知道这个算法的时间复杂度为O(sqrt(n))。
（２）因式分解
　　因式分解的算法很简单，模拟手工分解的过程，我们得到分解n的算法：枚举所有不大于n的所有素数，判断这些素数能整除n多少次。判断2到n是否素数，总共要计算sqrt(2)+sqrt(3)+sqrt(4)…+sqrt(n)&=n*sqrt(n)次，因此算法的时间复杂度可以粗略地认为是O(n*sqrt(n))。事实上，我们有更好的算法。先看一个显而易见的结论：如果p是能整除n的所有大于1的数中最小的，那么p是n的一个素因子。基于这样一个结论，我们得到
（３）公因子的数量
问题描述：已知一个正整数N，问这个数有多少正公因子。
算法分析：最容易想到的算法是：枚举1..N，看看有多少个数能整除N，这种算法的复杂度为O( N )。可以优化一下：如果N有小于SQRT( N )的因子X，那么N必定有大于SQRT( N )的因子Y与X对应，而且XY=N。所以我们只需要枚举1..SQRT( N )的数即可，还要考虑N为完全平方数的特殊情况。程序：。上面这个算法的复杂度为O(sqrt(N))。其实我们可以利用因式分解的方法来做。假设我们已经分解N得到 N =(p[1]^s[1])*(p[2]^s[2])...*(p[pnum]^s[pnum])，其中p[i]为互不相同的素数，那么N的正因子的数量为（具体怎么推导请参考组合数学教材中的母函数一章）：(s[1]+1)*(s[2]+1)*…*(s[pnum]+1)。
（４）最大公因式
问题描述：已知两个正整数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 mod a )
关于这个定理的具体证明，请参考初等数论书（或者初中数学竞赛中的数论相关章节）。
下面给出利用这个定理来写的一个求最大公因式的程序，请读者仔细研究：。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-2… A0)k = As-1 K^(s-1) + As-2 K^(s-2) + … + A0 K^(0) ，记为&1&式，其中0&=Ai&K（I=0,1,2..s-1）。对于一个已知的正整数n，如何得到n的K进制表示呢？换句话说，我们就是要求出As-1 As-2… A0来。具体的求解顺序是：先求出A0，然后是A1 ……，最后得到An-1。将&1&式等号两边同时取模k得：n mod K = a0。得到A0以后，(n-A0) div K = As-1 K^(s-2) + As-2 K^(s-3) + … + A1 K^(0)，用与求A0同样的方法可以得到A1，然后是A2……。 程序。
信息中心竞赛组编写(1)4星(0)3星(0)2星(0)1星(0)奥林匹克学 自学 入门 专转本 视频教程_土豆_高清视频在线观看}