信息学奥赛入门必读

信息学入门必读首先，你必须知道：第二：你为什么而学信息学？关于第一个问题，我可以回答你。至于第二个问题，那就要问你自己了。Ｑ：信息学学什么？Ａ：我个人认为：１． 初等组合。这是信息学解题的思维方式。２． 图论。主要是基础概念方面的，用于理解算法。３． 数学问题。这类题目有一些考的是数学思维，其中有一部分是考创造能力的。Ａ：平。２．熟练的掌握自己使用的编程语言。常常看到有人问一些很简单的语法问题什么的，其实这些东西实在太基础了，只需要翻翻书就可以弄懂的。如果连编程语言都不了解，又怎么能够编程呢？我这里说的编程语言指的是标准的程序设计语言，例如PASCAL，C/C++。而一些集成开发环境(IDE)并不属于这个范围，例如DELPHI，VB，VC等。３．一定要把一些基础打好，这个非常重要。所谓基础，就是一些基本的算法，例如：求最小公倍数，高精度等。再次强调一点：一定要重视基础４．IOI'2001提高正确率!GDSOI'2001300150能丢分，很难的题目不要花太多时间，能拿分就可以了。当然，这些建议是对于入门者来说的。５．要懂得利用网络资源。学会在网络上收集资料。但是有一点要注意：不要沉溺在网络上！Ｑ：用什么编程语言，什么IDE好？Ａ：我个人认为：编程语言：BASIC：如果你是编程初学者，那么BASIC是最适合的，但是这种语言不适合搞信息学。BASIC竞赛资料都是用PASCALC/C++ACMC/C+编程的中学生接受，而且如果用的不熟练是很容易出错的。不过，学过PASCALC/C+容易的，编程语言的学习是触类旁通的。IDE：PASCAL：建议初学者使用TurboPascal7.0BorlandPascal7.0DOSNOIfreepascalLinux过虽然IDEDELPHI，有点大材小用的感觉。C/C++：GCCTurboC++3.0RHIDE+GCC学会选择适合自己的题目来做！做题－总结－回头看看，这是我做题的一个习惯。但是选什么题目来做呢？相信这是很多初学者关心的问题。在此，我谈谈我的一些看法。首先，还是那句话：看看自己的位置。我认为：第一阶段：编程语言的学习。这个阶段并不需要找什么“竞赛题”，而是踏踏实实的把教材上每一章后面的练习认真地做几遍，最好没天都回头看看，不然会忘记的。不要认为后面的练习很简单，一定要认真做。基础的语言熟练了以后，还需要学一些高级一点的，但是这部分内容可以通过看别人的程序来学。比如说：有PASCALfillcharbeginend.的开头部分，于是猜想（不是盲目的猜，而是根据位置、单词构成等来猜）fillchar自己写了一个这样的程序来测试：ofvarj:=1doend; i:=1do123; end.得到这样的屏幕输出：123123123123123123123123123123 0 0 00 0 0 0 0 0 0于是可以初步断定：fillchar(a,sizeof(a),0)是用来把数组a0fillchar用法不只是这样的，这等到以后水平提高了就会明白的。第二阶段：基础算法。OIBH（OIBH方法是：先自己想一篇，然后看看标准程序，对比一下优劣，取长补短，过两天再做一次。最好养成把一些不熟悉的算法隔几天再做一次的习惯。有的时候，某个算法在你学习的那天以及以后几天内可能很熟悉，但是一段时间不用，很容易就忘或者不熟练。第三阶段：简单的深度搜索和广度搜索。……（以后再写，敬请留意基本算法讲座之数学篇基本算法是解难题的基础，必须熟练掌握。这一讲将介绍跟数学密切相关的基本算法。（１）素数数学类的基本算法大多数属于初等数论范畴，相当大一部分与素数有直接关系，因此素数是一个很基本又很重要的内容。我们先来看看怎么判断一个数是否素数。素数的定义为：如果一个数的正因子只有１和这个数本身，那么这个数就是素数。根据定义，我们立即能得到判断一个数Ｎ（大于１)是否素数的简单的算法：枚举２到Ｎ－１之间的整数，判断是否能整除Ｎ。该算法的Pascal代码。nn1sqrt(n)的（假np，1<p<n，如果p<=sqrt(n)，那么psqrt(n)，如果p>sqrt(n)，那么n/pn1<n/p<n，所以n/psqrt(n)）。于是我们可以改进上面的程序，得到另外一个Pascal程序。容易知道这个算法的时间复杂度为O(sqrt(n))。（２）因式分解因式分解的算法很简单，模拟手工分解的过程，我们得到分解nnn2npn1pnPascal代码。（３）公因子的数量问题描述：已知一个正整数N，问这个数有多少正公因子。O(NNSQRT(NX，那么NSQRT(NYXXY=N1..SQRT(N)的数即可，还要考虑N序：Pascal。上面这个算法的复杂度为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)。（４）最大公因式ab，求这两个数的最大公因数GCD(a,b(GCD是GreatestCommonDivisora<=b1到aabO(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,ba)关于这个定理的具体证明，请参考初等数论书（或者初中数学竞赛中的数论相关章节）。下面给出利用这个定理来写的一个求最大公因式的程序，请读者仔细研究：Pascal。此算法的时间复杂度为O(log(Max(a,b)))。（推导过程请参考算法与数据结构教材）（５）最小公倍数ab，求这两个数的最小公倍数LCM(a,b(LCM是LeastCommonMultiply算法分析：直接利用公式：LCM(a,b)*GCD(a,b)=a*b即可。（６）进制转换16k进制的数可以表示为：(As-1As-2A0)k=As-1K^(s-1)+As-2K^(s-2)+…+A0K^(0)，记为<10<=Ai<K（I=0,1,2..s-1）。对于一个已知的正整数n，如何得到n的KAs-1As-2A0A0A1An-1<1>式等号两边同时取模k：nmodKa0。得到A0(n-A0)divKAs-1K^(s-2)+As-2K^(s-3)+…+A1K^(0)，用与求A0A1，然后是A2……。Pascal程序。运行这个程序，输入：155169B（169B9*16+11=155）nP（As-1As-2…A0），nQ（Bl-1Bl-2…B0）。一种简单的方法是：根据Pn，然后再将nQ在于小数部分，所以现在只考虑实数0r<1rKA2A3As）K=A1K^(-1)+A2K^(-