【正文】 。 ? 將整數(shù) n分成 k份，且每份不能為空，且最大值不超過 m的分法 。 ? 多個多項式采用逐次相乘的方法。 ? n=5,拆分數(shù) 6 ? n=6,拆分數(shù) 10 ? n=7,拆分數(shù) 14 ? 1:5=1+4 ? 2:5=1+1+3 ? 3:5=1+1+1+2 ? 4:5=1+1+1+1+1 ? 5:5=1+2+2 ? 6:5=2+3 nj = 2[ f ( n j , j ) + f ( n 1 , j 1 )]?? 用母函數(shù)法： ? 當 n=5時： ? 構(gòu)造母函數(shù)如下： ? F(x)=(x0+x1+x2+x3+x4+x5)([x2]0+[x2]1+[x2]2)([x3]0+[x3]1) ? ([x4]0+[x4]1)([x5]0+[x5]1) ? =(1+x+x2+x3+x4+x5)(1+x2+x4)(1+x3)(1+x4)(1+x5) ? =1+x+2x2+3x3+5x4+7x5+…… ? 項 a[i]Xi的系數(shù) a[i]， a[i]1即自然數(shù) i的拆分數(shù) . ? 減 1是因為包含了 i=i的一種拆分方案。2， 2， 3。1， 2， 4。 輸入： n， k (6n=200， 2=k=6) 輸出：一個整數(shù)，即不同的分法。 5， 1， 1。 1， 1， 5。 418 3060C ?插 空 問 題 ：四、整數(shù)劃分問題 將整數(shù) n分成 k份，且每份不能為空，任意兩種分法不能相同 (不考慮順序 )。 n1}中選 k個元素，數(shù)目為 f(n1,k)。 n2}中選 k1個元素，數(shù)目為 f(n2,k1)。 n}中能夠選擇的沒有 兩個連續(xù) 整數(shù)的 k個元素子集的數(shù)目，求遞歸式 f(n,k)。 第 n個元素可以第 i（ 1=i=n）個出棧，前面已出棧有 i1個元素，出棧方法： f（ i1）；后面出棧 ni 個元素，出棧方法為： f（ ni）。 【 問題分析 】 ： 設(shè) f（ n）為 n個元素的不同出棧序列數(shù)目。 f(2)=2, f(3)=5 選定其中 1個結(jié)點為根，左子樹結(jié)點的個數(shù)為 i，二叉樹數(shù)目 f（ i）種；右子樹結(jié)點數(shù)目為 ni1，二叉樹數(shù)目 f（ ni1）種， I的可取范圍 [0， n1]。 【 問題分析 】 ： 設(shè) F(n)為 n個結(jié)點組成二叉樹的數(shù)目。求對于一個任意的凸 n邊形相應(yīng)的 f(n)。當 n=7,r=4 時， S(7,4)= _____________ 二、 Catalan數(shù) 問題一：凸 n邊形的三角形剖分 在一個凸 n邊形中，通過不相交于 n邊形內(nèi)部的對角線，把 n邊形拆分成若干三角形，不同的拆分數(shù)目用 f(n)表之， f(n)即為 Catalan數(shù)。將這 n 個球放入 r 個相同的盒子里，不允許 ? 有空盒，其不同放置方法的總數(shù)記為 S(n,r)。 要求：輸入數(shù)據(jù)有一行，第一個數(shù)是 n,第二個數(shù) m。 (1=I ,j=m) 則稱 S1,S2, …,Sm 是 S的一個劃分。 Si∩Sj=∮ 。 設(shè) S是一個包含 n個元素的集合， S={b1,b2,b3,…,bn}, 現(xiàn)需要將 S集合劃分為 m個滿足如下條件的集合 S1,S2, …Sm 。 44 1 1 1 1 1( ) ! ( ......( 1 ) )2 ! 3! 4 ! 5 !nf n nn? ? ? ? ?錯排的計算公式： 幾類重要的遞推關(guān)系： 一、第二類 Stirling數(shù) 問題一：放置小球 n個有區(qū)別的球放到 m個相同的盒子中，要求無一空盒，其不同的方案數(shù)用S(n,m)表示，稱為第二類 Stirling數(shù) 設(shè)有 n個不同的球，分別用 b1,b2,……bn 表示。 由加法原理： f(n)=(n1)*(f(n1)+f(n2)) f(1)=0。 第一部分： n先不動，把另外的 n1個數(shù)錯排，方案是： f（ n1），然后 n和另外的 n1個每一個交換，共有 (n1)*f(n1)種方案。 n 的錯排問題， i不在第 i個位置的排列方法?，F(xiàn)將 n本書全部取下然后再放回去，當放回去時要求每本書都不能放在原來的位置上。問用這些點為頂點，能組成多少個不同四邊形？ （ NOIP10）由 3個 a， 5個 b和 2個 c構(gòu)成的所有字符串中，包含子串“ abc” 的共有（ ）個。 1 2 31 2 3( ) !! * ! * !n n nn n n??重復元素的組合問題： 從 n種不同的元素中取 r個的元素的組合，允許有重復元素的組合： 1rnrC ??典型模型： r個相同的小球，放到 n個不同的盒子里，所有的放置方法。若每樣乘坐一次的費用是 5元，游樂場總共收入 700，可知有 名兒童沒有玩過其中任何一種。他們可以騎旋轉(zhuǎn)木馬，坐滑行鐵道，乘宇宙飛船。 A. {c, e} B. {d, e} C. {e} D. {c, d, e} E. {d, f} 容斥原理 在計數(shù)時，為了使重疊部分不被重復計算，人們研究出一種新的計數(shù)方法，這種方法的基本思想是： 先不考慮重疊的情況，把包含于某內(nèi)容中的所有對象的數(shù)目先計算出來，然后再把計數(shù)時重復計算的數(shù)目排斥出去，使得計算的結(jié)果既無遺漏又無重復，這種計數(shù)的方法稱為 容斥原理 。 A） 空集 B） {1} C） {3， 5} D） {1， 5} E） {1， 3， 5} （ NOIP10）設(shè)全集 I = {a, b, c, d, e, f, g}，集合 A = {a, b, c}， B = {b, d, e}， C = {e, f, g}，那么集合為（ ）。noip13 A. gcc B. g++ C. Turbo C D. free pascal 19. NOIP競賽推薦使用的語言環(huán)境有（ ）。(((A∧ B)∨ C)∧ D∧ E) C. A∧ (B∨ C∨ D∨ E) D. (A∧ (B∨ C)) ∧ D∧ E 競賽環(huán)境的考察： ，屬于 NOIP競賽（復賽）推薦使用的語言環(huán)境有（ ）。 A∧ B)∨ (C∧ D)∨ 172。 （ A + C） E) A+1=A 5．在 Pascal語言中，表達式 (21 xor 2)的值是（ ） noip12 A. 441 B. 42 6．在 Pascal語言中，判斷 a不等于 0且 b不等于 0的正確的條件表達式是（ ） noip12 A. not a=0 or not b=0 B. not((a=0)and(b=0)) C. not(a=0 and b=0) D. (a0)or(b0) E. (a0)and (b0) 11. 設(shè) A=B=D=true， C=E=false，以下邏輯運算表達式值為真的有（ ）。C D) A +（ B （ B + C ） = A （ A + B ） = A B) A +（ A (A)11001110 (B)01110110 (C)11101110 (D)01001100 13．下列邏輯運算正確的是（ ）。 A） 30H B） 05H C） 35H D） 53H 11. （ NIOP11）設(shè) A = true， B = false， C = false， D = true，以下邏輯運算表達式值為真的有（ ）。A “ 非”運算的運算法則為 =1 =0 A0 1① (NOIP9)假設(shè) A=true,B=false,C=ture,D=ture,邏輯運算表達式 A/\B \/C/\D的值是（ ）。”表示?！胺恰边\算也叫求 反運算 或者 邏輯否定 。 在邏輯問題中，如果某一事件的發(fā)生取決于條件的否定，即事件與事件發(fā)生的條件之間構(gòu)成矛盾，則這種因果關(guān)系稱為“非”邏輯。 “或”運算又稱 邏輯加 ，其運算符號為“ +” ，有時也用“ ∨ ”表示。0=0 A1 = 0 10 = 0 1 F = A “與”運算又稱為 邏輯乘 ， 其運算符號為“ 異或 : xor ◆ 運算的優(yōu)先級：非＞與＞或 “與” 運算 （ “ A. 調(diào)制解調(diào)器 B. 路由器 C. 網(wǎng)卡 D. 網(wǎng)關(guān) E. 網(wǎng)橋 十、邏輯運算： ◆ 運算： 與 : and ∧ （ NOIP10） A、 WWW（ World Wide Web） B、 URL（ Uniform Resource Locator） C、 HTTP（ Hypertext Transfer Protocol） D、 FTP（ Fast Transfer Protocol） E、 TCP（ Transfer Control Protocol）。（ NOIp11） A. HTTP B. SMTP C. TCP D. FTP E. POP3 9. 不能在 Linux 上使用的網(wǎng)頁瀏覽器是（ ）。這三類網(wǎng)絡(luò)的地址特征為 ⑴ A類網(wǎng)絡(luò)以 0開頭，網(wǎng)絡(luò)號碼是 7位，主機號碼是 24位 ⑵ B類網(wǎng)絡(luò)以 10開頭，網(wǎng)絡(luò)號碼是 14位，主機號碼是 16位 ⑶ C類網(wǎng)絡(luò)以 110開頭， C類網(wǎng)絡(luò)的網(wǎng)絡(luò)號碼是 21位，主機號碼是 8位 D類地址以 1110開頭， E類地址以 11110開頭。Noip14 A. 鏈路層 B．網(wǎng)絡(luò)層 C. 傳輸層 D. 應(yīng)用層 TCP/IP（ Transmission Control Protocol/Inter Protocol)的簡寫，中文譯名為 傳輸控制協(xié)議 /因特網(wǎng)互聯(lián)協(xié)議 ，又叫網(wǎng)絡(luò)通訊協(xié)議 。 7432 TCP/IP是一組構(gòu)成互聯(lián)網(wǎng)基礎(chǔ)的網(wǎng)絡(luò)協(xié)議，字面上包括兩組協(xié)議：傳輸控制協(xié)議（ TCP）和網(wǎng)際協(xié)議（ IP）。 主機 A與主機 B進行通信時，通信協(xié)議是在對等層之間進行的。 常用的固定字長有 8位 、 16位 、 32位等 。常用的單位有： KB 1K=1024 MB 1M=1024K GB 1G=1024M TB 1t=1024G 機器字 （ word） ： 字是位的組合 ， 并作為一個獨立的信息單位處理 。字節(jié)是信息存儲中最常用的基本單位。 (NOIP8) A） B） 11110110 C） D） ② [x]補碼 =10011000，其原碼為 ( )(NOIP7) A)011001111 B)11101000 C)11100110 D)01100101 C B 八、 信息存儲單位 ⑴位（ bit，縮寫為 b） ：度量數(shù)據(jù)的最小單位，表示一位二進制信息。 如：39的 BCD碼為 00111001。 BCD碼 （ 8421碼 ） BCD碼就是用二進制代碼表示的十進制數(shù) ， 也稱 BCD數(shù) 。 [01100100]補 ＝ 01000100 對于負數(shù) :兩頭的