NOIP初賽知識點復(fù)習(xí)總結(jié)

1、NOIP2011初賽指導(dǎo)課程大綱NOIP初賽情況的簡單分析基礎(chǔ)知識二叉樹圖排列組合程序閱讀題程序填空題總結(jié)初賽試卷題型分析單項選擇 15分不定項選擇 15分（多選少選均不得分）問題求解 10分閱讀程序 32分完善程序 28分初賽試卷題型分析初賽考的知識點，大綱說：計算機基本常 識，基本操作和程序設(shè)計基本知識。選擇 題考查的是知識，而問題解決題、填空更 加重視能力的考查。一般說來，選擇題是不需要單獨準備的 ，也無從準備。只要多用心積累就可以 了。到是問題解決題目比較固定，大家應(yīng) 當(dāng)多作以前的題目。寫運行結(jié)果需要多做 題目，培養(yǎng)良好的程序閱讀和分析能力， 而完善程序最好總結(jié)一下以前題目常常要 你填

2、出來的語句類型。初賽試卷題型分析1.選擇題一般它們是比較容易得分的，一共30分，不可 錯過！ 近幾年來，初賽的考查范圍有了很大的變化，越來 越緊跟潮流，需要大家有比較廣泛的知識，包括計算機 硬件，軟件，網(wǎng)絡(luò)，數(shù)據(jù)結(jié)構(gòu)（例如棧，隊列，排序算 法），程序設(shè)計語言以及一些基本的數(shù)學(xué)知識和技巧（例如排列組合等）。2.填空、問題解決這部分題目對數(shù)學(xué)要求要高一點，往往考查的是代數(shù) 變形、集合論、數(shù)列（一般是考遞推），也考查 一些算 法和數(shù)據(jù)結(jié)構(gòu)知識。建議大家多花一點時間做，盡量做對。初賽試卷題型分析3. 閱讀程序?qū)懗鲞\行結(jié)果占的分數(shù)多，但得分率卻不高，較易失分，一 旦結(jié)果不正確，將丟失全分。這種題型主要考

3、察選手： 程序設(shè)計語言的掌握能力 數(shù)學(xué)運算能力 耐心、細心的心理品質(zhì)一般做這類題目的 關(guān)鍵在于能夠分析程序的結(jié)構(gòu)及程序段的功能， 找出程序目的，即這個程序想干什么。初賽試卷題型分析完成這類題目的一般方法和步驟是： 從頭到尾通讀程序，大致掌握程序的算法； 通過給程序分段，清理程序的結(jié)構(gòu)和層次，達到讀懂程序 的目的； 閱讀程序中特別注意跟蹤主要變量值的變化，也可以用列表的方法，了解變量變化和程序運行的結(jié)果，要注意發(fā)現(xiàn)規(guī)律。 迄今為止考過的題目還沒有“亂寫”的，總有一點“寫作目的” 的。抓住了它，得出答案就變得很容易了，而且對結(jié)果也會有信 心。寫程序運行結(jié)果大綱規(guī)定是必考的。試卷中給出的程序并不 復(fù)

4、雜，語句的含義容易明白，因此悟性好的選手總是很快就能體 會到程序的設(shè)計思路并得出正確的答案，而機械模仿計算機硬算 出結(jié)果的同學(xué)往往做的慢的多，而且容易失誤。初賽試卷題型分析4.完善程序這部分題目得分率似乎不高。沒關(guān) 系，盡量做吧。把一些簡單的填好就行了。建議大家把以前的初賽題目都做做。常常讓大家填的是：初始化一些明顯的動作：a.結(jié)果沒有儲存在需要的地方。b.累加器沒有做加法c.輸出關(guān)鍵動作。在算法描述中出現(xiàn)的比較關(guān)鍵的步驟。例如交換 排序程序的“交換”操作等很明顯需要完成的操作。分析方法和寫運行結(jié)果類似，注意分析變量和 程序結(jié)構(gòu)，理解變量和模塊的作用是解題的關(guān)鍵。進制轉(zhuǎn)換1二進制與十進制間的相

5、互轉(zhuǎn)換：（1）二進制轉(zhuǎn)十進制 方法：“按權(quán)展開求和” 例：（1011.01）2（123022121120021122）10（802100.25）10（11.25）10規(guī)律：個位上的數(shù)字的次數(shù)是0，十位上的數(shù)字的次數(shù)是1，.，依次遞增，而十分位的數(shù)字的次數(shù)是-1，百分位上數(shù)字的次數(shù)是-2，.，依次遞減。 注意：不是任何一個十進制小數(shù)都能轉(zhuǎn)換成有限位的二進 制數(shù)。進制轉(zhuǎn)換進制轉(zhuǎn)換1二進制與十進制間的相互轉(zhuǎn)換：（1）二進制轉(zhuǎn)十進制 方法：“按權(quán)展開求和” 例：（1011.01）2（123022121120021122）10（802100.25）10（11.25）10規(guī)律：個位上的數(shù)字的次數(shù)是0，十位

6、上的數(shù)字的次數(shù)是1，.，依獎遞增，而十分位的數(shù)字的次數(shù)是-1，百分 位上數(shù)字的次數(shù)是-2，.，依次遞減。 注意：不是任何一個十進制小數(shù)都能轉(zhuǎn)換成有限位的二進 制數(shù)。進制轉(zhuǎn)換以下二進制數(shù)與十進制數(shù)23.456最接近的是（）A 10111.0101B 11011.1111C 11011.0111D 10111.0111E.10111.1111D把下面的數(shù)轉(zhuǎn)換為10進制數(shù)再進行比較位運算位運算主要有：按位與( & )，按位或( | )，按位異或( )， 取反運算法則：1、先將兩邊的數(shù)轉(zhuǎn)化為二進制，右邊第 一位對齊，對于每一位進行按位運算。2、只有1&1為真，其余情況為假3、只有0|0為假，其余為真4

7、、只有10和01為真，其余為假5、優(yōu)先級& |6、(00001001)2=(11110110)2切記：25不是25而是2異或5位運算補充：負數(shù)在計算機內(nèi)的表示是取對應(yīng)正數(shù)的補碼。補碼 = 反碼 + 1如1表示為(0001)2，那么-1就表示為：(1111)2。10表示為(1010)2，那么-10就表示為(0110)2。位運算比如，計算212先轉(zhuǎn)換為二進制21 = (10101)22 = (10)2(10111)2=2310101 10= 10111位運算練習(xí)題：23|25的值是多少？2323|25 = 23|7 = 23這個內(nèi)容比較重要，至少會占1分，請大家務(wù)必學(xué)透！邏輯設(shè)A = true，B

8、 = false，C = false，D = true， 以下邏輯運算表達式值為真的有（CDE）。A. (AB)(CD)B. (AB)C)DC. A(BC)D)D. (A(BC) DE. (AB)(CD)真真假假很容易判斷的，大家這么聰明應(yīng)該可以 自己搞定，我就不多講了總之復(fù)賽前要看一 下哦！需要結(jié)合C語言的邏輯判斷！邏輯6在 C語言中，判斷整數(shù)a 等于 0 或b等于 0或c等于0 的正確的條件表達式是（B）A. ! (a!=0) | (b!=0) | (c!=0)B. ! (a!=0) & (b!=0) & (c!=0)C. ! (a=0) & (b=0) | (c=0)D.(a=0) &

9、(b=0) & (c=0)E. ! (a=0) | (b=0) | (c=0)邏輯12. 命題“PQ”可讀做P蘊含Q， 其中P、Q是兩個獨立的命題. 只有當(dāng)命題P成 立而命題Q不成立時， 命題PQ的值為 false， 其它情況均為true. 與命題PQ 等價的邏輯關(guān)系式是（AD）。A. PQB. PQC. (PQ)D. (QP )需要注意優(yōu)先級邏輯PQp=truep=false PQp=truep=falseq=truetruetrueq=truetruetrueq=falsefalsetrueq=falsefalsetruePQp=truep=false(QP )p=truep=falseq

10、=truetruefalseq=truetruetrueq=falsefalsefalseq=falsefalsetrue位運算與邏輯強烈建議背下C語言常用運算符的優(yōu)先級表。參見C語言程序設(shè)計附錄，序號越低優(yōu)先級越高。集合論集合我們剛剛學(xué)過，但是我們學(xué)的東西還是少了點。另外，注意信息學(xué)競賽中的一 些符號和數(shù)學(xué)書上略有不同。需要學(xué)會的運算：交集，并集，補集，差集集合論集合我們剛剛學(xué)過，但是我們學(xué)的東西還是少了點。另外，注意信息學(xué)競賽中的一 些符號和數(shù)學(xué)書上略有不同。需要學(xué)會的運算：交集，并集，補集，差集建議學(xué)會 “鴿巢原理”差集符號： (就是減號)A B 就相當(dāng)于去掉A中(AB)的元素。集合論設(shè)

11、全集I = a, b, c, d, e, f, g, h，集合BA = a, b, c, d, e, f， CA= c, d, e，B A= a, d，那么集合CBA為（A）。A. c, e B. d, e C. eD. c, d, e E. d, f集合論設(shè)全集I = a, b, c, d, e, f, g，集合A = a,b, c，B = b, d, e，C = e, f, g，那么集 合(A B)(CB)為（A）。A. a, b, c, dB. a, b, d, eC. b, d, eD. b, c, d, eE. d, f, g儲存單位的計算bit 位Byte 比特，字節(jié)KB 千字節(jié)M

12、B，兆字節(jié)其它單位：GBTB速率單位（聲音，視頻，網(wǎng)絡(luò)）：bps bit per second bit/sKbps Kbit per second Kbit/sMbps Mbit per second Mbit/s儲存單位的計算1 Byte = 8 bit1 KB = 1024 Byte1 MB = 1024 KB = 10242 Byte = 8*10243 bit1 GB = 1024 MB = 10242 KB = 10243 Byte=.自己去推了1Mbps = 1024 Kbps = 10242bpsAttention，大B小b有區(qū)別的，一個是bit，一個是Byte， 所以KB和Kb

13、是不一樣的，比如說“ADSL寬帶512Kb” 當(dāng)然，現(xiàn)在很多人都混著用了但是考試還是要嚴格點。儲存單位的計算聲音文件的大小等于：速率*長度（注意單位噢）下載時間與網(wǎng)絡(luò)速度的關(guān)系：下載時間 = 文件大小 / 下載速率注意下載速率的基本單位是bit/s，而文件大小的 單位是Byte，所以要乘以8。公式不用死記，用物理的量綱理論就可以了。由 單位確定公式。(bit/s) * (s) = bit下載速率*時間 = 文件大小儲存單位的計算例題：一個音樂愛好者收藏有100首MP3格式的音樂，這些音樂的編碼率都是192Kbps，平均每首音樂的時長為3min， 他要通過網(wǎng)絡(luò)將這些音樂傳送給另一個 人，假設(shè)網(wǎng)絡(luò)

14、速度恒定為512KB/s，則他 傳送這些音樂大概需要（）。A. 72sB. 843sC. 112.5minD.3h48min16sE. 超過24小時100 * 192Kb/s * 3min / (512KB/s) = 843.75s切記要換算單位！儲存單位的計算10. 一位藝術(shù)史學(xué)家有20000 幅1024 *768 的真彩色圖像，如果將這些圖像以位 圖形式保存在CD 光盤上（一張CD 光盤 的容量按600M計算），大約需要（C）張 CD光盤。A. 1 B. 10 C. 100 D. 1000 E. 10000Hint：真彩色通常指每像素32位的圖形1024*768*20000*32bit/6

15、00MB = 100儲存單位的計算10. 一位藝術(shù)史學(xué)家有20000 幅1024 *768 的 256色圖像，如果將這些圖像以位圖形式保存在CD 光盤上（一張CD 光盤 的容量按600M計算），大約需要（B）張CD光盤。A. 10 B. 25 C. 100 D. 250 E. 800真彩A. 1 B. 10 C. 100 D. 1000 E. 10000棧和隊列類比火車站。一個是這樣的另一個是這樣的棧和隊列某個車站呈狹長形，寬度只能容下一臺車，并且只有一個出入口。已知某時刻該車站狀態(tài)為空，從 這一時刻開始的出入記錄為：“進，出， 進，進，進，出，出，進，進，進，出,出”。 假設(shè)車輛入站的 順序

16、為 1，2，3，則車 輛出站的順序為（）。A. 1, 2, 3, 4, 5B. 1, 2, 4, 5, 7C. 1, 4, 3, 7, 6D. 1, 4, 3, 7, 2E. 1, 4, 3, 7, 5排序n個數(shù)排序，最少需要比較多少次？for(i=1; i=n; i+)for(j=1; j aj+1)/這就是比較.公式： 最少比較次數(shù) = log2n!10將 5 個數(shù)的序列排序，不論原先的順序如何，最少都可以通過（B）次比較， 完成從小到大的排序。A. 6B. 7C. 8D. 9E. 10排序思考:最壞情況下最少需要交換多少次?n-11. 將數(shù)組32, 74, 25, 53, 28, 43,

17、 86, 47中的元素按從小到大的順序排列，每 次可以交換任意兩個元素，最少需要 交換_5_次。排序穩(wěn)定排序包括：插入排序、冒泡排序不穩(wěn)定排序包括：選擇排序、希爾排序、快速排序、堆排序時間復(fù)雜度：冒泡排序O(n2)，選擇排序O(n2)，快速排 序O(nlog2n)，堆排序O(nlog2n)二叉樹定義：n個結(jié)點的有限集，每個結(jié)點至多 只有兩棵子樹，子樹也是二叉樹。每個結(jié) 點可以有左孩子和右孩子，順序不可顛倒。概念：度：某個結(jié)點孩子的個數(shù)葉子：度為0的結(jié)點深度：二叉樹的層數(shù)滿二叉樹：深度為n且結(jié)點數(shù)為2n-1的二叉樹完全二叉樹：深度為k，1k-1層為滿二叉 樹，第k層葉子節(jié)點集中在左邊的二叉樹二叉

18、樹二叉樹的遍歷：先根，中根，后根遍歷以及深度優(yōu)先遍歷和廣度優(yōu)先遍歷，具體方 法參看資料。根據(jù)前根中根或中根后根遍歷確定一顆二叉樹的形態(tài)以及另一種遍歷。二叉樹知識點補充n個結(jié)點所組成的不同形態(tài)的二叉樹數(shù)目為：C(2n,n)/(n+1)二叉樹二叉樹T，已知其前序遍歷序列為1 2 4 35 7 6，中序遍歷序列為4 2 1 5 7 3 6，則其后序遍歷序列為（B）。A. 4 2 5 7 6 3 1B. 4 2 7 5 6 3 1C. 4 2 7 5 3 6 1D. 4 7 2 3 5 6 1E. 4 5 2 6 3 7 1二叉樹已知7個節(jié)點的二叉樹的先根遍歷是1 2 45 6 3 7(數(shù)字為結(jié)點的編

19、號，以下同)， 后 根遍歷是4 6 5 2 7 3 1， 則該二叉樹的可能的中根遍歷是（ABD）A. 4 2 6 5 1 7 3B. 4 2 5 6 1 3 7C. 4 2 3 1 5 4 7D. 4 2 5 6 1 7 3只知道前根遍歷和后根遍歷是無法確定一棵二叉樹的，所以這題采用反推驗證二叉樹4. 完全二叉樹的結(jié)點個數(shù)為4 * N + 3，則它的葉結(jié)點個數(shù)為（E）。A. 2 * NB. 2 * N - 1C. 2 * N + 1D. 2 * N - 2E. 2 * N + 24n+3=2*2(n+1) - 1，多么熟悉的公式啊2*葉子結(jié)點數(shù)-1，這不是滿二叉樹的結(jié)點數(shù) 么？二叉樹8高度為

20、n 的均衡的二叉樹是指：如果去掉葉結(jié)點及相應(yīng)的樹枝，它應(yīng)該是高度為 n-1 的滿二叉樹。在這里，樹高等于葉 結(jié)點的最大深度，根結(jié)點的深度為 0，如 果某個均衡的二叉樹共有 2381 個結(jié)點， 則該樹的樹高為（B）。A. 10B. 11C. 12D. 13E. 210 12112381212二叉樹5.一個高度為h 的二叉樹最小元素數(shù)目是（B）。A） 2h+1B） hC） 2h-1D） 2hE） 2h-1此時二叉樹退化成一條鏈圖圖是由頂點和邊所組成的數(shù)據(jù)結(jié)構(gòu)。分為有向圖和無向圖。帶權(quán)圖：權(quán)的含義，不加權(quán)的圖也可以認為所有邊上的權(quán)都是1。 階和度：一個圖的階是指圖中頂點的個數(shù)如果頂點A和B之間有一條

21、邊相連，則稱A和B是 關(guān)聯(lián)的 頂點的度：與該頂點相關(guān)聯(lián)的邊的數(shù)目，有奇點、 偶點之分 對于有向圖：有入度和出度之分圖大家記住定義，然后就見招拆招了。圖論的題目考得比較少，而且大家知道定義， 運用各種方法應(yīng)該不難得到答案。下面就簡單地講一下幾道出現(xiàn)過的題目。圖假設(shè)我們用d=(a1,a2,.,a5),表示無向圖G的5個頂點的度數(shù)，下面給出的哪（些）組d 值合理（BE）。A）5，4，4，3，1B）4，2，2，1，1C）3，3，3，2，2D）5，4，3，2，1E）2，2，2，2，2圖9. 歐拉圖G是指可以構(gòu)成一個閉回路的 圖，且圖G的每一條邊恰好在這個閉回路 上出現(xiàn)一次（即一筆畫成）。在以下各個 描述

22、中, 不一定是歐拉圖的是：（）。A. 圖G中沒有度為奇數(shù)的頂點B. 包括歐拉環(huán)游的圖(歐拉環(huán)游是指通過 圖中每邊恰好一次的閉路徑)C. 包括歐拉閉跡的圖(歐拉跡是指通過途 中每邊恰好一次的路徑)D. 存在一條回路, 通過每個頂點恰好一次E. 本身為閉跡的圖解釋：閉跡，一條路徑，起點和終點是一個點圖5. 平面上有五個點A(5, 3), B(3, 5), C(2, 1),D(3, 3), E(5, 1)。以這五點作為完全圖G 的 頂點，每兩點之間的直線距離是圖G 中對應(yīng) 邊的權(quán)值。圖G 的最小生成樹中的所有邊的 權(quán)值和為（D）A.8B.7+5C.9D.6+5E.4+22+5講解：最小生成樹算法圖1

23、. 無向圖G有16條邊，有3個4度頂點、4個3度頂點，其余頂點的度均小于3，則G至少_1_1_個頂點。排列組合前置知識：乘法原理，加法原理，排列組 合公式C(n,r)，A(n,r)的計算方法以及基本 定理和推論。沒學(xué)到的同學(xué)可在課后自學(xué)（參見高二數(shù) 學(xué)課本，沒有的問數(shù)學(xué)老師要相關(guān)資料）另外強烈推薦一本書：離散數(shù)學(xué)及其應(yīng) 用，機械工業(yè)出版社，Kenneth H.Rosen著，袁崇義等譯，當(dāng)當(dāng)和卓越均有售排列組合公式：1、不可重復(fù)的n個元素取r個的排列數(shù)為：A(n,r)2、可重復(fù)的n個元素取r個的排列數(shù)為：nr3、不可重復(fù)的n個元素取r個的組合數(shù)為：C(n,r)4、可重復(fù)的n個元素取r個的組合數(shù)為

24、：C(n+r-1,r)排列組合練習(xí)：1.有五個不同顏色的球，從中依次拿出三 個，可能的排列有多少種2.有五種不同顏色的球，從中依次拿出三 個，可能的排列有多少種3.有五個不同顏色的球，從中拿出三個， 可能的組合有多少種4.有五種不同顏色的球，從中拿出三個， 可能的組合有多少種排列組合由3個a，5個b和2個c構(gòu)成的所有字符串中，包含子串“abc”的共有（D）個。A. 40320B. 39600C. 840D. 780E. 60C(8,1) * C(7,2) *C(5,4) * C(1,1) -C(6,2) * C(4,1)*C(3,3)取出abc，變成2個a，4個b和1個c和abc構(gòu)成字符串的數(shù)

25、目。一共有2+5+1+1=8個位置，任取1個給abc，方 法數(shù)是C(8,1)，剩下7個取2個給a，方法數(shù)C(7,2)，剩下5 個取4個放b，以此類推。但是要考慮abcabc出現(xiàn)兩次重 復(fù)計算的情況，所以要減去，怎么減大家自己思考一下。排列組合練習(xí)字符串success重新排列，包括其本身，共可以組成多少個不同的字符串？C(7,2)*C(5,2)*A(3,3) = 1260問題求解75名兒童到游樂場去玩。他們可以騎旋轉(zhuǎn)木馬，坐滑行鐵道，乘宇宙飛船。已知其 中20人這三種東西都玩過，55人至少玩過 其中的兩種。若每樣乘坐一次的費用是5 元，游樂場總共收入700，可知有_1_0_名兒童沒有玩過其中任何

26、一種。集合類問題，通?？梢赃\用數(shù)學(xué)方法解決已知a, b, c, d, e, f, g七個人中，a會講英語；b會講英語和漢語；c會講英語、意大利語和俄語；d會講漢語和日 語；e會講意大利語和德語；f會講俄語、日語和法語；g 會講德語和法語。能否將他們的座位安排在圓桌旁，使 得每個人都能與他身邊的人交談？如果可以，請以“a b” 開頭寫出你的安排方案：_a_bd_f_g_c_。小學(xué)數(shù)學(xué)推理題的啦英漢意俄日德法aObOOcOOOdOOeOOfOOOgOO2. 取火柴游戲的規(guī)則如下：一堆火柴有N根，A、B兩人輪流取出。每人每次可以取1 根或2 根，最先沒有火柴可取的人為敗 方，另一方為勝方。如果先取者

27、有必勝策 略則記為1，先取者沒有必勝策略記為0。當(dāng)N 分別為100，200，300，400，500時，先取者有無必勝策略的標(biāo)記順序為（回答應(yīng)為一個由0 或1 組成的字符串）。11011，簡單的博弈論，小學(xué)奧數(shù)題（取石子游戲） 現(xiàn)有 5 堆石子,石子數(shù)依次為 3，5，7，19，50，甲乙兩人輪流從 任一堆中任?。看沃荒苋∽砸欢眩荒?不?。? 取最后一顆石子的一方獲勝。甲 先取，問甲有沒有獲勝策略（即無論 乙怎 樣取，甲只要不失誤，都能獲勝）？第一次在第五堆里面取32枚石子。 T=3571950=32，取掉32后T=0，面對 T=0的狀態(tài)時，先取者必敗變態(tài)的博弈論，而且還是普及組的題目。碰到就

28、阿彌陀佛 了。1將 2006 個人分成若干不相交的子集， 每個子集至少有 3 個人，并且：（1）在每個子集中，沒有人認識該子集 的所有人。（2）同一子集的任何 3 個人中，至少有 2 個人互不認識。（3）對同一子集中任何 2 個不相識的 人，在該子集中恰好只有 1 個人認識這兩 個人。 則滿足上述條件的子集最多能有_個？401，這種題看造化了，解釋起來相當(dāng)復(fù)雜，主要方法是根 據(jù)(1)，(2)，(3)進行假設(shè)，發(fā)現(xiàn)至少需要5個人才能同時滿 足(1)，(2)，(3)，于是2006/5，一個6人，其余5人2將邊長為 n 的正三角形每 邊 n 等分，過每個分點分別 做另外兩邊的平行線，得到若干個正三角

29、形， 我們稱為小 三角形。正三角形的一條通路 是一條連續(xù)的折線，起點是最 上面的一個小三角形，終點是 最 下面一行位于中間的小三 角形。在通路中，只允許由一 個小三角形走到另一個與其有 公共邊的且位于同 一行或下 一行的小三角形，并且每個小 三角形不能經(jīng)過兩次或兩次以 上（圖中是 n=5 時一條通路 的例 子）。設(shè) n=10，則該正 三角形的不同的通路的總數(shù)為_。362880嚴格證明挺復(fù)雜，找規(guī)律 可以知道總數(shù)為(n-1)!1給定n個有標(biāo)號的球，標(biāo)號依次為1，2，n。將這n個球放入r個相同的盒子 里，不允許有空盒，其不同放置方法的總 數(shù)記為S(n,r)。例如，S(4,2)=7，這7種不 同的放

30、置方法依次為(1) , (234) , (2) ,(134) , (3) , (124) , (4) , (123) , (12) ,(34) , (13) , (24) , (14) , (23)。當(dāng)n=7，r=4時，S(7,4)=_。289S(n,r)=S(n-1,r-1)+r*S(n-1,r)邊界條件自己找。 難題，遞推類問題，離散數(shù)學(xué)及其應(yīng)用有介紹下面介紹一個簡單的遞推問題，好讓大家初步認識遞推。小明上樓，一步可以上一級，也可以上兩 級，請問上n級有多少種上法？例如，上2 級可以有1+1，也可以一次上2級。上3級 可以是1+1+1，2+1,1+2三種。設(shè)f(n)表示上n級需要的步數(shù)，顯

31、然只能夠從n-1級或n-2級上到第n級，所以方法總數(shù)適用加法原理，f(n)=f(n-1)+f(n-2)，啊，出現(xiàn)了，傳說中的斐波那契數(shù) 列！其中f(1)=1，f(2)=2，后面的都可以根據(jù)這兩個初 始條件推出來2N個人在操場里圍成一圈，將這N個人 按順時針方向從1到N編號，然后從第一個 人起，每隔一個人讓下一個人離開操場， 顯然，第一輪過后，具有偶數(shù)編號的人都 離開了操場。依次做下去，直到操場只剩 下一個人，記這個人的編號為J(N)，例 如，J(5)=3，J(10)=5，等等。則J(400)= _。（提示：對J(N)=2m+r進行分析，其中0r2m）。289，找規(guī)律，數(shù)學(xué)好的智商分數(shù)的比較占優(yōu)

32、勢N1234567891011121314151617J(n)113135713579111315132m2021212222222223232323232323232424r001012301234567012r+111313571357911131513非常容易看出：J(N)=J(2m+r)=2r+1J(400)=J(28+144)=2*144+1=289問題求解總結(jié)1、要耐心地尋找規(guī)律2、要冷靜的分析問題3、不到萬不得已決不輕言放棄（8分啊兄 弟們）4、不懂就蒙一個！閱讀程序1、認真計算2、耐心分析3、分析不下去就函數(shù)（語句作用）4、千萬記得第一個閱讀程序要檢查5、多多練習(xí)，熟能生巧6、

33、列出變量變化表#include void fun(int *a,int *b)int *k;k=a; a=b; b=k;fun是耍人的意思，其實根本沒交換兩個變量的值。當(dāng) 時很多人被fun了int main( )int a=3,b=6,*x=&a,*y=&b;fun(x,y);printf(No.1: %d,%d ,a,b);fun(&a,&b);printf(No.2: %d,%dn,a,b);return 0;程序填空這種題與編程經(jīng)驗和算法學(xué)習(xí)的程度有關(guān)，拿得一分是一分。不過對于編程經(jīng)驗 不足和算法練習(xí)少的人來說也不是沒分可 拿。比如說for(i=n; )printf(%1d,gri);/

34、* 在 %1d 中出現(xiàn)的是數(shù)字1，不是字母l */printf(n);雖然無頭無尾，也沒有題目描述，但是一眼就可以看出這個是個輸出結(jié)果的語句。于是 乎i0;i-凡此種種，不勝枚舉抓住機會！程序填空總結(jié)1、分析語句是干什么的，回到開頭講的內(nèi)容：初始化一些明顯的動作：a.結(jié)果沒有儲存在需要的地方。b.累加器沒有做加法c.輸出關(guān)鍵動作。2、不懂就根據(jù)上下文猜3、不寫白不寫，蒙一下總是好的。4、千萬注意開頭和結(jié)尾，常常有送分題目喔！幾個小問題20. 近20年來， 許多計算機專家都大力推崇 遞歸算法，認為它是解決較復(fù)雜問題的強有 力的工具. 在下列關(guān)于遞歸的說法中， 正確的是（AC）。A. 在1977年

35、前后形成標(biāo)準的計算機高級語言FORTRAN77禁止在程序使用遞歸， 原因 之一是該方法可能會占用更多的內(nèi)存空間.B. 和非遞歸算法相比， 解決同一個問題， 遞歸算法一般運行得更快一些C. 對于較復(fù)雜的問題， 用遞歸方式編程往往 比非遞歸方式更容易一些D. 對于已定義好的標(biāo)準數(shù)學(xué)函數(shù)sin(x)， 應(yīng) 用程序中的語句“y=sin(sin(x);”就是一種 遞歸調(diào)用16.在下列各軟件中，屬于 NOIP 競賽（復(fù) 賽）推薦使用的語言環(huán)境有（）。A. gccB. g+ABDC. Turbo CD. free pascal16.在下列各軟件中，屬于 NOIP 競賽（復(fù) 賽）推薦使用的語言環(huán)境有（）。A. gcc/g+B. Turbo PascalC. Turbo CD. free pascal18. 在下列關(guān)于計算機語言的說法中，正確的有（AB）。A. Pascal和C都是編譯執(zhí)行的高級語言B. 高級語言程序比匯編語言程序更容易從 一種計算機移植到另一種計算機上C. C+是歷史上的第一個支持面向?qū)ο蟮?計算機語言D. 高級語