信息學奧賽入門必讀

1、信息學入門必讀首先，你必須知道：第一：信息學學的是什么？第二：你為什么而學信息學？關(guān)于第一個問題，我可以回答你。至于第二個問題，那就要問你自己了Q：信息學學什么？A:我個人認為：1 .初等組合。這是信息學解題的思維方式。2 .圖論。主要是基礎(chǔ)概念方面的，用于理解算法。3 .數(shù)學問題。這類題目有一些考的是數(shù)學思維，其中有一部分是考創(chuàng)造能力的。Q:學習過程中要注意什么問題？A:1 .認清自己的位置。也就是根據(jù)自己的學習目的，判斷自己是什么水平，經(jīng)過努力能到達什么水平。2 .熟練的掌握自己使用的編程語言。常常看到有人問一些很簡單的語法問題什么的，其實這些東西實在太基礎(chǔ)了，只需要翻翻書就可以弄懂的。如

2、果連編程語言都不了解，又怎么能夠編程呢？我這里說的編程語言指的是標準的程序設(shè)計語言，例如PASCALC/C+。而一些集成開發(fā)環(huán)境（IDE）并不屬于這個范圍，例如DELPHI,VB,VC等。3 .一定要把一些基礎(chǔ)打好，這個非常重要。所謂基礎(chǔ)，就是一些基本的算法，例如：求最小公倍數(shù)，高精度等。再次強調(diào)一點：一定要重視基礎(chǔ)！4 .IOI'2001金牌獲得者毛子青前輩道出學好信息學的金言：提高正確率！其實第3點說的"打好”基礎(chǔ)的意思就是：對于基礎(chǔ)的題目，一定要百分百正確！我在GDSOI'2001中深刻的體會到"正確率"的內(nèi)涵：滿分300分的試題，最高分只有

3、159!而且能夠有一題全對的人也沒幾個！要知道，如果有一半題目全對的話，就已經(jīng)有150了！所以，我認為：簡單的題目一定不能丟分，很難的題目不要花太多時間，能拿分就可以了。當然，這些建議是對于入門者來說的。5 .要懂得利用網(wǎng)絡(luò)資源。學會在網(wǎng)絡(luò)上收集資料。但是有一點要注意：不要沉溺在網(wǎng)絡(luò)上！Q:用什么編程語言，什么IDE好？A:我個人認為：編程語言：BASIC:如果你是編程初學者，那么BASIC是最適合的，但是這種語言不適合搞信息學。PASCAL這個是最適合初學者學習的，因為這種語言和BASIC一樣簡單易學，而且現(xiàn)在國內(nèi)中學生的競賽資料都是用PASCAL寫的。C/C+:大學生基本都有這個的，參加A

4、CM必學語言。C/C+里面有一些概念可能不太容易被初學編程的中學生接受，而且如果用的不熟練是很容易出錯的。不過，學過PASCAL的人要學C/C+是很容易的，編程語言的學習是觸類旁通的。IDE:PASCAL建議初學者使用TurboPascal7.0或者BorlandPascal7.0，是DOS下的。要對調(diào)試的基本操作熟悉。以后到了高層次的競賽，例如NOI,是需要freepascal的，而且是Linux下的。不過雖然IDE變了，但是用幾天就會熟悉的了。至于DELPHI,有點大材小用的感覺。C/C+:GCC是首選，TurboC+3.0也不錯。要看寫什么程序，對競賽來說RHIDE+GCC是首選學會選擇

5、適合自己的題目來做！做題-總結(jié)-回頭看看，這是我做題的一個習慣。但是選什么題目來做呢？相信這是很多初學者關(guān)心的問題。在此，我談?wù)勎业囊恍┛捶?。首先，還是那句話：看看自己的位置。我認為：第一階段：編程語言的學習。這個階段并不需要找什么“競賽題”，而是踏踏實實的把教材上每一章后面的練習認真地做幾遍，最好沒天都回頭看看，不然會忘記的。不要認為后面的練習很簡單，一定要認真做。基礎(chǔ)的語言熟練了以后，還需要學一些高級一點的，但是這部分內(nèi)容可以通過看別人的程序來學。比如說：有些PASCA用沒有說fillchar的用法，但是我看到很多高手的程序都把這個語句放在beginend.的開頭部分，于是猜想（不是盲目的

6、猜，而是根據(jù)位置、單詞構(gòu)成等來猜）fillchar是用來初始化的，自己寫了一個這樣的程序來測試：programTest_Fillchar;constmaxn=10;vara:array1.maxnofinteger;integer;procedurePrintA;varj:Integer;beginforj:=1tomaxndowrite(aj:5);writeln;end;beginfori:=1tomaxndoai:=123;PrintA;fillchar(a,sizeof(a),0);PrintA;end.得到這樣的屏幕輸出:于是可以初步斷定：fillchar(a,sizeof(a),0

7、)是用來把數(shù)組a制0的。當然fillchar的真正用法不只是這樣的，這等到以后水平提高了就會明白的。第二階段：基礎(chǔ)算法。選題的方法有很多，可以選擇書籍或者OIBH列出來的題目(OIBH過幾天再放上一些基礎(chǔ)算法的程序)來做，也可以在以后解其他題的過程“提煉”出屬于基礎(chǔ)算法的部分來做。我當初“做”的方法是：先自己想一篇，然后看看標準程序，對比一下優(yōu)劣，取長補短，過兩天再做一次。最好養(yǎng)成把一些不熟悉的算法隔幾天再做一次的習慣。有的時候，某個算法在你學習的那天以及以后幾天內(nèi)可能很熟悉，但是一段時間不用，很容易就忘或者不熟練。第三階段：簡單的深度搜索和廣度搜索。(以后再寫，敬請留意基本算法講座之數(shù)學篇基

8、本算法是解難題的基礎(chǔ)，必須熟練掌握。這一講將介紹跟數(shù)學密切相關(guān)的基本算法。(1)素數(shù)數(shù)學類的基本算法大多數(shù)屬于初等數(shù)論范疇，相當大一部分與素數(shù)有直接關(guān)系，因此素數(shù)是一個很基本又很重要的內(nèi)容。我們先來看看怎么判斷一個數(shù)是否素數(shù)。素數(shù)的定義為：如果一個數(shù)的正因子只有1和這個數(shù)本身，那么這個數(shù)就是素數(shù)。根據(jù)定義，我們立即能得到判斷一個數(shù)N(大于1)是否素數(shù)的簡單的算法：枚舉2到N1之間的整數(shù)，判斷是否能整除N。該算法的Pascal代碼。如果n很大，那么上面的程序就要運行比較長的一段時間，那么有沒有更快一點的算法呢？回答是肯定的！因為如果n含有不為1和自身的因子，那么這些因子中必定有不大于sqrt(n

9、)的(假設(shè)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)。于是我們可以改進上面的程序，得到另外一個Pascal程序。容易知道這個算法的時間復雜度為O(sqrt(n)。(2)因式分解因式分解的算法很簡單，模擬手工分解的過程，我們得到分解n的算法：枚舉所有不大于n的所有素數(shù)，判斷這些素數(shù)能整除n多少次。判斷2到n是否素數(shù)，總共要計算sqrt(2)+sqrt(3)+sqrt(4)+sqrt(n)<=n*sqrt(n)次，因此算法

10、的時間復雜度可以粗略地認為是O(n*sqrt(n)。事實上，我們有更好的算法。先看一個顯而易見的結(jié)論：如果p是能整除n的所有大于1的數(shù)中最小的，那么p是n的一個素因子。基于這樣一個結(jié)論，我們得到Pascal代碼。(3)公因子的數(shù)量問題描述：已知一個正整數(shù)N,問這個數(shù)有多少正公因子。算法分析：最容易想到的算法是：枚舉1.N,看看有多少個數(shù)能整除N,這種算法的復雜度為O(N)o可以優(yōu)化一下：如果N有小于SQRT(N)的因子X,那么N必定有大于SQRT(N)的因子丫與X對應(yīng)，而且XY=N所以我們只需要枚舉1.SQRT(N)的數(shù)即可，還要考慮N為完全平方數(shù)的特殊情況。程序：Pascal。上面這個算法的

11、復雜度為O(sqrt(N)。其實我們可以利用因式分解的方法來做。假設(shè)我們已經(jīng)分解N得到N=(p1As1)*(p2As2).*(ppnumAspnum),其中pi為互不相同的素數(shù)，那么N的正因子的數(shù)量為(具體怎么推導請參考組合數(shù)學教材中的母函數(shù)一章)：(s1+1)*(s2+1)*(spnum+1)。(4)最大公因式問題描述：已知兩個正整數(shù)a和b,求這兩個數(shù)的最大公因數(shù)GCD(a,b)。(GCD是GreatestCommonDivisor的縮寫)算法分析：不妨設(shè)a<=b,一種十分容易想到的算法是：枚舉1到a的所有整數(shù)，在能同時整除a和b的數(shù)中取最大的。這個算法的時間復雜度為O(min(a,b

12、),當min(a,b)較大的時候程序要執(zhí)行比較長的時間。我們可以利用初等數(shù)論中的一個定理：GCD(a,b)=GCD(a,b-a)=GCD(a,b-2*a)=GCD(a,b-3*a)=GCD(a,bmoda)關(guān)于這個定理的具體證明，請參考初等數(shù)論書(或者初中數(shù)學競賽中的數(shù)論相關(guān)章節(jié))。下面給出利用這個定理來寫的一個求最大公因式的程序，請讀者仔細研究：Pascalo此算法的時間復雜度為O(log(Max(a,b)。(推導過程請參考算法與數(shù)據(jù)結(jié)構(gòu)教材)(5)最小公倍數(shù)問題描述：已知兩個正整數(shù)a和b,求這兩個數(shù)的最小公倍數(shù)LCM(a,b)。(LCM是LeastCommonMultiply的縮寫)算法分

13、析：直接利用公式：LCM(a,b)*GCD(a,b)=a*b即可。(6)進制轉(zhuǎn)換我們平常計算都是用十進制數(shù)的，但是有的時候我們需要用到2進制數(shù)、16進制數(shù)等。一個k進制的數(shù)可以表示為：(As-1As-2A0)k=As-1KA(s-1)+As-2KA(s-2)+A0KA(0),記為<1>式，其中0<=Ai<K(I=0,1,2.s-1)o對于一個已知的正整數(shù)n,如何得到n的K進制表示呢？換句話說，我們就是要求出As-1As-2A0來。具體的求解順序是：先求出A0,然后是A1,最后得到An-10將<1>式等號兩邊同時取模k得：nmodK=a0。得到A0以后，(n-

14、A0)divK=As-1KA(s-2)+As-2KA(s-3)+A1KA(0),用與求A0同樣的方法可以得到A1,然后是A2。Pascal程序。運行這個程序，輸入：15516就可以得到結(jié)果9B(16進制的9B=9*16+11=155)怎么進行任意進制間的數(shù)的轉(zhuǎn)換呢？已知一個數(shù)正整數(shù)n的P進制表示(As-1As-2A0),求n的Q進制表示(Bl-1Bl-2B0)。一種簡單的方法是：根據(jù)P進制表示求出十進制的n,然后再將n轉(zhuǎn)化為Q進制表示即可。前面考慮的都是整數(shù)的問題，我們現(xiàn)在來看看怎么處理實有理數(shù)。由于實數(shù)跟整數(shù)的區(qū)別僅僅在于小數(shù)部分，所以現(xiàn)在只考慮實數(shù)r,r滿足0<=r<1的情況。定義r的K進制表示為：r=(0.A1A2A3As)K=A1KA(-1)+A2KA(-2)+A3KA(-3).A