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。