信息學(xué)奧賽入門必讀

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

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

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

4、C+ :大學(xué)生基本都有這個(gè)的，參加ACM必學(xué)語言。C/C+里面有一些概 念可能不太容易被初學(xué)編程的中學(xué)生接受，而且如果用的不熟練是很容易出錯(cuò)的。不過，學(xué)過PASCAL的人要學(xué)C/C+是很容易的，編程語言的學(xué)習(xí)是觸類旁通的。IDE:PASCAL建議初學(xué)者使用 Turbo Pascal 7.0 或者Borland Pascal 7.0 ，是DOS下的。要對(duì)調(diào)試的 基本操作熟悉。以后到了高層次的競(jìng)賽，例如N0I，是需要freepascal的，而且是Linux下的。不過雖然IDE變了，但是用幾天就會(huì)熟悉的了。至于DELPHI，有點(diǎn)大材小用的感覺。C/C+ : GCC是首選，Turbo C+ 3.0 也

5、不錯(cuò)。要看寫什么程序，對(duì)競(jìng)賽來說RHIDE +GCC是首選。學(xué)會(huì)選擇適合自己的題目來做!做題-總結(jié)-回頭看看，這是我做題的一個(gè)習(xí)慣。但是選什么題目來做呢？相信這是很多初學(xué)者關(guān)心的問題。在此，我談?wù)勎业囊恍┛捶?。首先，還是那句話：看看自己的位置。我認(rèn)為： 第一階段：編程語言的學(xué)習(xí)這個(gè)階段并不需要找什么“競(jìng)賽題”，而是踏踏實(shí)實(shí)的把教材上每一章后面的練習(xí)認(rèn)真地做幾 遍，最好沒天都回頭看看，不然會(huì)忘記的。不要認(rèn)為后面的練習(xí)很簡(jiǎn)單，一定要認(rèn)真做。基礎(chǔ)的語言熟練了以后，還需要學(xué)一些高級(jí)一點(diǎn)的，但是這部分內(nèi)容可以通過看別人的程序來學(xué)。比如說：有 些PASCAL書沒有說fillchar 的用法，但是我看到很多

6、高手的程序都把這個(gè)語句放在 begin end.的 開頭部分，于是猜想（不是盲目的猜，而是根據(jù)位置、單詞構(gòu)成等來猜）fillchar是用來初始化的，自己寫了一個(gè)這樣的程序來測(cè)試：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)是用來把數(shù)組a制0的。當(dāng)然fillchar 的真正用法不只是這樣的，這等到以后水平提高了就會(huì)明白的。第二階段：基礎(chǔ)算法。選題的方法有很多，可以選擇書籍或者OIBH列出來的題目(OIBH過幾天再放上一些基礎(chǔ)算法的程序)來做，也可以在以后解其他題的過程“提煉”岀屬于基礎(chǔ)算法的部分來做。我當(dāng)初“做”的 方法是：先自己想 一篇，然后看看標(biāo)準(zhǔn)程序，對(duì)比一下

8、優(yōu)劣，取長(zhǎng)補(bǔ)短，過兩天再做一次。最好養(yǎng) 成把一些不熟悉的算法隔幾天再做一次的習(xí)慣。有的時(shí)候，某個(gè)算法在你學(xué)習(xí)的那天以及以后幾天內(nèi)可能很熟悉，但是一段時(shí)間不用，很容易就忘或者不熟練。第三階段：簡(jiǎn)單的深度搜索和廣度搜索。(以后再寫，敬請(qǐng)留意基本算法講座之?dāng)?shù)學(xué)篇基本算法是解難題的基礎(chǔ)，必須熟練掌握。這一講將介紹跟數(shù)學(xué)密切相關(guān)的基本算法。(1) 素?cái)?shù)數(shù)學(xué)類的基本算法大多數(shù)屬于初等數(shù)論范疇，相當(dāng)大一部分與素?cái)?shù)有直接關(guān)系，因此素?cái)?shù)是一 個(gè)很基本又很重要的內(nèi)容。我們先來看看怎么判斷一個(gè)數(shù)是否素?cái)?shù)。素?cái)?shù)的定義為：如果一個(gè)數(shù)的正因子只有1和這個(gè)數(shù) 本身，那么這個(gè)數(shù)就是素?cái)?shù)。根據(jù)定義，我們立即能得到判斷一個(gè)數(shù)N

9、(大于1 )是否素?cái)?shù)的簡(jiǎn)單的算法：枚舉2到N1之間的整數(shù)，判斷是否能整除N。該算法的Pascal代碼。如果n很大，那么上面的程序就要運(yùn)行比較長(zhǎng)的一段時(shí)間，那么有沒有更快一點(diǎn)的算法呢？回 答是肯定的！因?yàn)槿绻?n含有不為1和自身的因子，那么這些因子中必定有不大于sqrt(n)的(假設(shè)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)。于是我們可以改進(jìn)上面的程序，得到另外 一個(gè)Pascal程序。容易知道這個(gè)算法的時(shí)間復(fù)雜度為O(sq

10、rt(n)。(2) 因式分解因式分解的算法很簡(jiǎn)單，模擬手工分解的過程，我們得到分解n的算法：枚舉所有不大于n的所有素?cái)?shù)，判斷這些素?cái)?shù)能整除n多少次。判斷2到n是否素?cái)?shù)，總 共要計(jì)算sqrt(2)+sqrt (3)+sqrt+sqrt(n)<=n*sqrt(n) 次，因此算法的時(shí)間復(fù)雜度可以粗略地認(rèn)為是O(n*sqrt(n)。事實(shí)上，我們有更好的算法。先看一個(gè)顯而易見的結(jié)論：如果p是能整除n的所有大于1的數(shù)中最小的，那么p是n的一個(gè)素因子?；谶@樣一個(gè)結(jié)論，我們得到Pascal代碼。(3) 公因子的數(shù)量問題描述：已知一個(gè)正整數(shù)N,問這個(gè)數(shù)有多少正公因子。算法分析：最容易想到的算法是：枚舉1

11、.N，看看有多少個(gè)數(shù)能整除 N,這種算法的復(fù)雜度為 0( N)。 可以優(yōu)化一下：如果 N有小于SQRT( N )的因子X，那么N必定有大于SQRT( N )的因子Y與X對(duì)應(yīng)， 而且XY=N所以我們只需要枚舉1.SQRT( N )的數(shù)即可，還要考慮 N為完全平方數(shù)的特殊情況。程序：Pascal。上面這個(gè)算法的復(fù)雜度為O(sqrt(N)。其實(shí)我們可以利用因式分解的方法來做。假設(shè)我們已經(jīng)分解 N得到 N =(p1As1)*(p2As2).*(ppnumAspnum)，其中 pi為互不相同 的素?cái)?shù)，那么N的正因子的數(shù)量為(具體怎么推導(dǎo)請(qǐng)參考組合數(shù)學(xué)教材中的母函數(shù)一章)：(s1+1)*(s2+1)*(s

12、pnum+1)。(4) 最大公因式問題描述：已知兩個(gè)正整數(shù)a和b,求這兩個(gè)數(shù)的最大公因數(shù)GCD( a , b )。(GCD是 Greatest Common Divisor 的縮寫)算法分析：不妨設(shè)a<=b, 一種十分容易想到的算法是：枚舉1到a的所有整數(shù)，在能同時(shí)整除 a和b的數(shù)中取最大的。這個(gè)算法的時(shí)間復(fù)雜度為O(min(a,b)，當(dāng)min(a,b)較大的時(shí)候程序要執(zhí)行比較長(zhǎng)的時(shí)間。我們可以利用初等數(shù)論中的一個(gè)定理：GCD( a , b ) = GCD( a , b-a ) = GCD( a , b-2*a ) = GCD( a , b-3*a )=GCD( a , b moda )

13、關(guān)于這個(gè)定理的具體證明，請(qǐng)參考初等數(shù)論書(或者初中數(shù)學(xué)競(jìng)賽中的數(shù)論相關(guān)章節(jié))。下面給出利用這個(gè)定理來寫的一個(gè)求最大公因式的程序，請(qǐng)讀者仔細(xì)研究：Pascal。此算法的時(shí)間復(fù)雜度為O(log(Max(a,b)。(推導(dǎo)過程請(qǐng)參考算法與數(shù)據(jù)結(jié)構(gòu)教材)(5) 最小公倍數(shù)問題描述：已知兩個(gè)正整數(shù)a和b,求這兩個(gè)數(shù)的最小公倍數(shù)LCM ( a , b )。(LCM是 Least Common Multiply 的縮寫)算法分析：直接利用公式：LCM ( a , b ) * GCD( a , b ) = a * b即可。(6) 進(jìn)制轉(zhuǎn)換我們平常計(jì)算都是用十進(jìn)制數(shù)的，但是有的時(shí)候我們需要用到2進(jìn)制數(shù)、16進(jìn)制數(shù)

14、等。一個(gè)k進(jìn)制的數(shù)可以表示為：(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)。對(duì)于一個(gè)已知的正整數(shù)n，如何得到n的K進(jìn)制表示呢？換句話 說，我們就是要求出 As-1 As-2A0來。具體的求解順序是：先求出A0,然后是A1 ，最后得到An-1。將<1>式等號(hào)兩邊同時(shí)取模 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程序。運(yùn)行這個(gè)程序，輸入： 15516就可以得到結(jié)果9B (16進(jìn)制的9B = 9*16+1仁155 )怎么進(jìn)行任意進(jìn)制間的數(shù)的轉(zhuǎn)換呢？已知一個(gè)數(shù)正整數(shù)n的P進(jìn)制表示(As-1As-2A0)，求n的Q進(jìn)制表示(BI-1BI-2B0)。一種簡(jiǎn)單的方法是：根據(jù) P進(jìn)制表示求出十進(jìn)制的 n,然后再將 n轉(zhuǎn)化為Q進(jìn)制表示即可。前面考慮的都是整數(shù)的問題，我們現(xiàn)在來看看怎么處理實(shí)有理數(shù)。由于實(shí)數(shù)跟整數(shù)的區(qū)別僅僅在于小數(shù)部分，所以現(xiàn)在只考慮實(shí)數(shù) r, r滿足0 <= r <1的情況。定義r的K進(jìn)制表示為：r = (0.A1 A2 A3 As ) K = A1 0(-1) + A2 KA(-2) + A3 0(-3).As O(-s)。求解順序?yàn)椋?A1、A2As。