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

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

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

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

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

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

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

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

8、 = false，C = false，D = true， 以下邏輯運(yùn)算表達(dá)式值為真的有（CDE）。A. (AB)(CD)B. (AB)C)DC. A(BC)D)D. (A(BC) DE. (AB)(CD)真真假假很容易判斷的，大家這么聰明應(yīng)該可以 自己搞定，我就不多講了總之復(fù)賽前要看一 下哦！需要結(jié)合C語(yǔ)言的邏輯判斷！邏輯6在 C語(yǔ)言中，判斷整數(shù)a 等于 0 或b等于 0或c等于0 的正確的條件表達(dá)式是（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蘊(yùn)含Q， 其中P、Q是兩個(gè)獨(dú)立的命題. 只有當(dāng)命題P成 立而命題Q不成立時(shí)， 命題PQ的值為 false， 其它情況均為true. 與命題PQ 等價(jià)的邏輯關(guān)系式是（AD）。A. PQB. PQC. (PQ)D. (QP )需要注意優(yōu)先級(jí)邏輯PQp=truep=false PQp=truep=falseq=truetruetrueq=truetruetrueq=falsefalsetrueq=falsefalsetruePQp=truep=false(QP )p=truep=falseq

10、=truetruefalseq=truetruetrueq=falsefalsefalseq=falsefalsetrue位運(yùn)算與邏輯強(qiáng)烈建議背下C語(yǔ)言常用運(yùn)算符的優(yōu)先級(jí)表。參見(jiàn)C語(yǔ)言程序設(shè)計(jì)附錄，序號(hào)越低優(yōu)先級(jí)越高。集合論集合我們剛剛學(xué)過(guò)，但是我們學(xué)的東西還是少了點(diǎn)。另外，注意信息學(xué)競(jìng)賽中的一 些符號(hào)和數(shù)學(xué)書(shū)上略有不同。需要學(xué)會(huì)的運(yùn)算：交集，并集，補(bǔ)集，差集集合論集合我們剛剛學(xué)過(guò)，但是我們學(xué)的東西還是少了點(diǎn)。另外，注意信息學(xué)競(jìng)賽中的一 些符號(hào)和數(shù)學(xué)書(shū)上略有不同。需要學(xué)會(huì)的運(yùn)算：交集，并集，補(bǔ)集，差集建議學(xué)會(huì) “鴿巢原理”差集符號(hào)： (就是減號(hào))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儲(chǔ)存單位的計(jì)算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儲(chǔ)存單位的計(jì)算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ū)別的，一個(gè)是bit，一個(gè)是Byte， 所以KB和Kb

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

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

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

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

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

18、樹(shù)二叉樹(shù)的遍歷：先根，中根，后根遍歷以及深度優(yōu)先遍歷和廣度優(yōu)先遍歷，具體方 法參看資料。根據(jù)前根中根或中根后根遍歷確定一顆二叉樹(shù)的形態(tài)以及另一種遍歷。二叉樹(shù)知識(shí)點(diǎn)補(bǔ)充n個(gè)結(jié)點(diǎn)所組成的不同形態(tài)的二叉樹(shù)數(shù)目為：C(2n,n)/(n+1)二叉樹(shù)二叉樹(shù)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二叉樹(shù)已知7個(gè)節(jié)點(diǎn)的二叉樹(shù)的先根遍歷是1 2 45 6 3 7(數(shù)字為結(jié)點(diǎn)的編

19、號(hào)，以下同)， 后 根遍歷是4 6 5 2 7 3 1， 則該二叉樹(shù)的可能的中根遍歷是（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只知道前根遍歷和后根遍歷是無(wú)法確定一棵二叉樹(shù)的，所以這題采用反推驗(yàn)證二叉樹(shù)4. 完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為4 * N + 3，則它的葉結(jié)點(diǎn)個(gè)數(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é)點(diǎn)數(shù)-1，這不是滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)數(shù) 么？二叉樹(shù)8高度為

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

21、邊相連，則稱(chēng)A和B是 關(guān)聯(lián)的 頂點(diǎn)的度：與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目，有奇點(diǎn)、 偶點(diǎn)之分 對(duì)于有向圖：有入度和出度之分圖大家記住定義，然后就見(jiàn)招拆招了。圖論的題目考得比較少，而且大家知道定義， 運(yùn)用各種方法應(yīng)該不難得到答案。下面就簡(jiǎn)單地講一下幾道出現(xiàn)過(guò)的題目。圖假設(shè)我們用d=(a1,a2,.,a5),表示無(wú)向圖G的5個(gè)頂點(diǎn)的度數(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è)閉回路的 圖，且圖G的每一條邊恰好在這個(gè)閉回路 上出現(xiàn)一次（即一筆畫(huà)成）。在以下各個(gè) 描述

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

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

24、：C(n+r-1,r)排列組合練習(xí)：1.有五個(gè)不同顏色的球，從中依次拿出三 個(gè)，可能的排列有多少種2.有五種不同顏色的球，從中依次拿出三 個(gè)，可能的排列有多少種3.有五個(gè)不同顏色的球，從中拿出三個(gè)， 可能的組合有多少種4.有五種不同顏色的球，從中拿出三個(gè)， 可能的組合有多少種排列組合由3個(gè)a，5個(gè)b和2個(gè)c構(gòu)成的所有字符串中，包含子串“abc”的共有（D）個(gè)。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個(gè)a，4個(gè)b和1個(gè)c和abc構(gòu)成字符串的數(shù)

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

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

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

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

29、形， 我們稱(chēng)為小 三角形。正三角形的一條通路 是一條連續(xù)的折線(xiàn)，起點(diǎn)是最 上面的一個(gè)小三角形，終點(diǎn)是 最 下面一行位于中間的小三 角形。在通路中，只允許由一 個(gè)小三角形走到另一個(gè)與其有 公共邊的且位于同 一行或下 一行的小三角形，并且每個(gè)小 三角形不能經(jīng)過(guò)兩次或兩次以 上（圖中是 n=5 時(shí)一條通路 的例 子）。設(shè) n=10，則該正 三角形的不同的通路的總數(shù)為_(kāi)。362880嚴(yán)格證明挺復(fù)雜，找規(guī)律 可以知道總數(shù)為(n-1)!1給定n個(gè)有標(biāo)號(hào)的球，標(biāo)號(hào)依次為1，2，n。將這n個(gè)球放入r個(gè)相同的盒子 里，不允許有空盒，其不同放置方法的總 數(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時(shí)，S(7,4)=_。289S(n,r)=S(n-1,r-1)+r*S(n-1,r)邊界條件自己找。 難題，遞推類(lèi)問(wèn)題，離散數(shù)學(xué)及其應(yīng)用有介紹下面介紹一個(gè)簡(jiǎn)單的遞推問(wèn)題，好讓大家初步認(rèn)識(shí)遞推。小明上樓，一步可以上一級(jí)，也可以上兩 級(jí)，請(qǐng)問(wèn)上n級(jí)有多少種上法？例如，上2 級(jí)可以有1+1，也可以一次上2級(jí)。上3級(jí) 可以是1+1+1，2+1,1+2三種。設(shè)f(n)表示上n級(jí)需要的步數(shù)，顯

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

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

33、列出變量變化表#include void fun(int *a,int *b)int *k;k=a; a=b; b=k;fun是耍人的意思，其實(shí)根本沒(méi)交換兩個(gè)變量的值。當(dāng) 時(shí)很多人被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)驗(yàn)和算法學(xué)習(xí)的程度有關(guān)，拿得一分是一分。不過(guò)對(duì)于編程經(jīng)驗(yàn) 不足和算法練習(xí)少的人來(lái)說(shuō)也不是沒(méi)分可 拿。比如說(shuō)for(i=n; )printf(%1d,gri);/

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

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