預賽知識復習第1頁預賽試題形式

●預賽：預賽全部為筆試，滿分100分。試題由四部分組成：

1、選擇題：共20題，每小題1.5分，共計30分。每小題有5個備選答案，前10個題為單項選擇題(即每小題有且只有一個正確答案，選對得分)，后10題為不定項選擇題(即每小題有1至5個正確答案，只有全部選對才得分)。

2、問題求解題：共2題，每小題5分，共計10分。試題給出一個敘述較為簡單問題，要求學生對問題進行分析，找到一個適當算法，并推算出問題解?？忌o出答案與標準答案相同，則得分：不然不得分。

3、程序閱讀了解題：共4題，每小題8分，共計32分。題目給出一段程序(不一定相關于程序功效說明)，考生經(jīng)過閱讀了解該段程序給出程序輸出。輸出與標準答案一致，則得分；不然不得分。

4、程序完善題：共2題，每小題14分，共計28分。題目給出一段關于程序功效文字說明，然后給出一段程序代碼，在代碼中略去了若干個語句或語句一部分并在這些位置給出空格，要求考生依據(jù)程序功效說明和代碼上下文，填出被略去語句。填對則得分；不然不得分。

第2頁信息學競賽中數(shù)學知識◆集合運算◆排列與組合第3頁◆集合及其運算1、集合運算：并、交、補、差2、容斥原理第4頁1、集合運算：并、交、補、差并：∪交：∩補：^或～或差:-ABABAABA∪BA∩BA-B第5頁8.

（NOIP9）設全集E={1，2，3，4，5}，集合A={1，4}，B={1，2，5}，C={2，4}，則集合（A∩B）∪～C為（

e

）。

A）空集

B）{1}

C）{3，5}

D）{1，5}

E）{1，3，5}1、（NOIP10）設全集I={a,b,c,d,e,f,g}，集合A={a,b,c}，

B={b,d,e}，C={e,f,g}，那么集合為（a）。

A.{a,b,c,d}B.{a,b,d,e}C.{b,d,e}D.{b,c,d,e}E.{d,f,g}2.（NOIP11）設全集I={a,b,c,d,e,f,g,h}，集合B∪A={a,b,c,d,e,f}，

C∩A={c,d,e}，A∩~B={a,d}，那么集合C∩B∩A為（a）。

A.{c,e}B.{d,e}C.{e}D.{c,d,e}E.{d,f}

第6頁2、容斥原理在計數(shù)時，為了使重合部分不被重復計算，人們研究出一個新計數(shù)方法，這種方法基本思想是：先不考慮重合情況，把包含于某內容中全部對象數(shù)目先計算出來，然后再把計數(shù)時重復計算數(shù)目排斥出去，使得計算結果既無遺漏又無重復，這種計數(shù)方法稱為容斥原理。第7頁對有限集合S，用表示S元素個數(shù)容斥原理第一形式：設A，B是有限集合，則容斥原理第二形式：設A、B、C是有限集合，則第8頁1、（NOIP10）75名兒童到游樂場去玩。他們能夠騎旋轉木馬，坐滑行鐵道，乘宇宙飛船。已知其中20人這三種東西都玩過，55人最少玩過其中兩種。若每樣乘坐一次費用是5元，游樂場總共收入700，可知有

10名兒童沒有玩過其中任何一個。2、某學校足球隊有球衣30件，籃球隊有球衣15件，排球隊有球衣18件，三隊隊員總數(shù)為50人，其中有2人同時參加3個隊，那么同時只參加兩個隊隊員有多少？9３、分母是1001最簡分數(shù)一共有多少個？只是玩過其中兩種有55-20=35人只是玩過其中一個人所花費用700-20*（5*3）-35*（5*2）=50元只是其中一個人數(shù)50÷5=10人沒有玩過其中任何一個人數(shù)75-20-35-10=10人容斥原理A+B+C-（A與B重合-A與C重合-B與C重合）+A、B、C重合=總數(shù)30+15+18-（A與B重合-A與C重合-B與C重合）+2=50（A與B重合-A與C重合-B與C重合）=30+15+18+2-50=15人15-2*3=9人1001=7×11×13分子中不能含有質因數(shù)7、11、13即1至1001中，不能被7、11、13整除數(shù)有多少個？1001÷7=1431001÷11=911001÷13=771001÷[7,11]=13,[7,11]----7和11最小公倍數(shù)1001÷[7,13]=11,-------1001÷[11,13]=7,-----1001÷[7,11,13]=1143+91+77-(13+11+7)+1=281個不能被7，11，13整除數(shù)有1001-281=720個第9頁◆排列與組合第10頁1.排列定義:從n個不一樣元素中,任取m個元素,按照一定次序排成一列,叫做從n個不一樣元素中取出m個元素一個排列.排列數(shù)公式:全排列問題：

n個不一樣元素排成一排，排列方法有：=n*(n-1)*(n-2)*…*2*1=n!第11頁2.組合定義:從n個不一樣元素中,任取m個元素,并成一組,叫做從n個不一樣元素中取出m個元素一個組合.組合數(shù)公式:排列與組合區(qū)分與聯(lián)絡:與次序相關為排列問題,與次序無關為組合問題.第12頁加法原理和乘法原理從A到C共有多少中走法？ABC第13頁例1:學校師生合影，共8個學生，4個老師，要求老師在學生中間，且老師互不相鄰，共有多少種不一樣合影方式？第14頁解先排學生共有種排法,然后把老師插入學生之間空檔，共有7個空檔可插,選其中4個空檔,共有種選法.依據(jù)乘法原理,共有不一樣坐法為種.結論1

插入法:對于某兩個元素或者幾個元素要求不相鄰問題,能夠用插入法.即先排好沒有限制條件元素,然后將有限制條件元素按要求插入排好元素空檔之中即可.第15頁例2:5個男生3個女生排成一排,3個女生要排在一起,有多少種不一樣排法?

第16頁解

因為女生要排在一起,所以能夠將3個女生看成是一個人,與5個男生作全排列,有種排法,其中女生內部也有種排法,依據(jù)乘法原理,共有種不一樣排法.結論2

捆綁法:要求某幾個元素必須排在一起問題,能夠用捆綁法來處理問題.即將需要相鄰元素合并為一個元素,再與其它元素一起作排列,同時要注意合并元素內部也能夠作排列.第17頁例3:袋中有不一樣年份生產5分硬幣23個,不一樣年份生產1角硬幣10個,假如從袋中取出2元錢,有多少種取法?第18頁解

把全部硬幣全部取出來,將得到0.05×23+0.10×10=2.15元,所以比2元多0.15元,所以剩下0.15元即剩下3個5分或1個5分與1個1角,所以共有種取法.結論3

剩下法:在組合問題中,有多少取法,就有多少種剩法,他們是一一對應,所以,當求取法困難時,可轉化為求剩法.分析此題是一個組合問題,若是直接考慮取錢問題話,情況比較多,也顯得比較凌亂,難以理出頭緒來.不過假如依據(jù)組合數(shù)性質考慮剩下問題話,就會很輕易處理問題.第19頁例4

學校安排考試科目9門,語文要在數(shù)學之前考,有多少種不一樣安排次序?第20頁解不加任何限制條件,整個排法有種,“語文安排在數(shù)學之前考”,與“數(shù)學安排在語文之前考”排法是相等,所以語文安排在數(shù)學之前考排法共有種.結論4

對等法:在有些題目中,它限制條件必定是否定是對等,各占全體二分之一.在求解中只要求出全體,就能夠得到所求.分析對于任何一個排列問題,就其中兩個元素來講話,他們排列次序只有兩種情況,而且在整個排列中,他們出現(xiàn)機會是均等,所以要求其中某一個情況,能夠得到全體,那么問題就能夠處理了.而且也防止了問題復雜性.第21頁例5

某個班級共有43位同學,從中任抽5人,正、副班長、團支部書記最少有一人在內抽法有多少種?第22頁解

43人中任抽5人方法有種,正副班長,團支部書記都不在內抽法有種,所以正副班長,團支部書記最少有1人在內抽法有種.結論5

排異法:有些問題,正面直接考慮比較復雜,而它反面往往比較簡捷,能夠先求出它反面,再從整體中排除.分析此題若是直接去考慮話,就要將問題分成好幾個情況,這么解題話,輕易造成各種情況遺漏或者重復情況.而假如從此問題相反方面去考慮話,不但輕易了解,而且在計算中也是非常簡便.這么就能夠簡化計算過程.第23頁圓周排列：從n個不一樣元素中取r個沿一圓周排列，排列方案：/rN個元素圓周排列：/n=（n-1）!第24頁有重復元素排列問題：如：n1個a，n2個b，n3個c，排成一排，有多少種排列方法。第25頁1.（NOIP7）平面上有三條平行直線，每條直線上分別有7，5，6個點，且不一樣直線上三個點都不在同一條直線上。問用這些點為頂點，能組成多少個不一樣四邊形？22502、（NOIP10）由3個a，5個b和2個c組成全部字符串中，包含子串“abc”共有（）個。

A.40320B.39600由3個a，5個b和2個c組成全部字符串中，包含子串“abc”共有C.840D.780E.60

當abc在第一位時,后面一共有105種排列(7!/(2!*4!)=105)當abc在第二位時,也是105種...當abc在第八位時,也是105.105*8=840種里面有重復減去有2個字字串abc.一共60種(6!/(2!*3!)=60)所以840-60=780種第26頁1．

(NOIP8)

在書架上放有編號為1，2，．．．，nn本書?，F(xiàn)將n本書全部取下然后再放回去，當放回去時要求每本書都不能放在原來位置上。比如：n=3時：原來位置為：123

放回去時只能為：312或231這兩種

問題：求當n=5時滿足以上條件放法共有多少種？（不用列出每種放法）44第27頁錯排問題：

n個不一樣元素錯排問題：如：1，2，3，。。。，n錯排問題，i不在第i個位置排列方法。分析：設f(n)為n個不一樣元素錯排方案。第一部分：n先不動，把另外n-1個數(shù)錯排，方案是：f（n-1），然后n和另外n-1個每一個交換，共有(n-1)*f(n-1)種方案。第二部分：n和其它n-1個之一交換，其余n-2個錯排，共有（n-1）*f（n-2）種方案。由加法原理：

f(n)=(n-1)*(f(n-1)+f(n-2))f(1)=0;f(2)=1;第28頁錯排計算公式：第29頁幾類主要遞推關系：第30頁一、第二類Stirling數(shù)問題一：放置小球n個有區(qū)分球放到m個相同盒子中，要求無一空盒，其不一樣方案數(shù)用S(n,m)表示，稱為第二類Stirling數(shù)

設有n個不一樣球，分別用b1,b2,……bn表示。從中取出一個球bn，bn放法有以下兩種：1)bn獨自占一個盒子；那么剩下球只能放在m-1個盒子中，方案數(shù)為S(n-1,m-1)2)bn與別球共占一個盒子；那么能夠事先將b1,b2,……bn-1這n-1個球放入m個盒子中，然后再將球bn能夠放入其中一個盒子中，方案數(shù)為m*S(n-1,m)S(n,m)=m*S(n-1,m)+S(n-1,m-1)(n>1,m>1)邊界條件：S(n,1)=1；S(n,n)=1；S(n,k)=0(k>n)第31頁問題二：集合劃分問題。設S是一個包含n個元素集合，S={b1,b2,b3,…,bn},現(xiàn)需要將S集合劃分為m個滿足以下條件集合S1,S2,…Sm。

Si≠∮;

Si∩Sj=∮;

S1∪S2∪…∪Sm=S;(1<=I,j<=m)則稱S1,S2,…,Sm是S一個劃分。編程：輸入n和m值，輸出不一樣劃分方案數(shù)。要求：輸入數(shù)據(jù)有一行，第一個數(shù)是n,第二個數(shù)m。樣例：輸入：43輸出：6第32頁noip131．給定n個有標號球，標號依次為1，2，…，n。將這n個球放入r個相同盒子里，不允許有空盒，其不一樣放置方法總數(shù)記為S(n,r)。比如，S(4,2)=7，這7種不一樣放置方法依次為{(1),(234)},{(2),(134)},{(3),(124)},{(4),(123)},{(12),(34)},{(13),(24)},{(14),(23)}。當n=7,r=4時，S(7,4)=____350_________遞推公式S(n,r)=S(n-1,r)*r+S(n-1,r-1).因為把n個球放入r個箱子,相當于先把n-1個球放好再放最終一個.最終一個有兩種放法：放入前面已經(jīng)有球箱子或者獨占一個箱子.前者對應S(n-1,r)*r(放入每一個不一樣箱子都是一個不一樣放法,因為箱子內原來球不一樣),后者對應S(n-1,r-1).第33頁二、Catalan數(shù)問題一：凸n邊形三角形剖分在一個凸n邊形中，經(jīng)過不相交于n邊形內部對角線，把n邊形拆分成若干三角形，不一樣拆分數(shù)目用f(n)表之，f(n)即為Catalan數(shù)。比如五邊形有以下五種拆分方案，故f(5)=5。求對于一個任意凸n邊形對應f(n)。第34頁區(qū)域①是一個凸k邊形，區(qū)域②是一個凸n-k+1邊形，區(qū)域①拆分方案總數(shù)是f(k)；區(qū)域②拆分方案數(shù)為f(n-k+1)；故包含△P1PkPnn邊形拆分方案數(shù)為f(k)*f(n-k+1)種F(n)=第35頁問題二：二叉樹數(shù)目問題描述：求n個結點能組成不一樣二叉數(shù)數(shù)目?！締栴}分析】：設F(n)為n個結點組成二叉樹數(shù)目。輕易知道：f(1)=1;f(2)=2,f(3)=5選定其中1個結點為根，左子樹結點個數(shù)為i，二叉樹數(shù)目f（i）種；右子樹結點數(shù)目為n-i-1，二叉樹數(shù)目f（n-i-1）種，I可取范圍[0，n-1]。所以有：F(n)=

為了計算方便：約定f（0）=1第36頁問題三：出棧序列問題描述：N個不一樣元素按一定次序入棧，求不一樣出棧序列數(shù)目?！締栴}分析】：設f（n）為n個元素不一樣出棧序列數(shù)目。輕易得出：f（1）=1；f（2）=2。第n個元素能夠第i（1<=i<=n）個出棧，前面已出棧有i-1個元素，出棧方法：f（i-1）；后面出棧n-i個元素，出棧方法為：f（n-i）。所以有：F(n)=第37頁三、集合取數(shù)問題

1、設f(n,k)是從集合{1，2，。。。，n}中能夠選擇沒有兩個連續(xù)整數(shù)k個元素子集數(shù)目，求遞歸式f(n,k)?！締栴}分析】：N有兩種情況：①當n在子集時，則n-1一定不在子集中，即在{1，2，。。。，n-2}中選k-1個元素，數(shù)目為f(n-2,k-1)。②當n不在子集中時，則在{1，2，。。。，n-1}中選k個元素，數(shù)目為f(n-1,k)。所以：f(n,k)=f(n-2,k-1)+f(n-1,k)邊界條件：F(n,1)=n,f(n,k)=0(n<=k)第38頁四、整數(shù)劃分問題

1、將整數(shù)n分成k份，且每份不能為空，任意兩種分法不能相同(不考慮次序)。

比如：n=7，k=3，下面三種分法被認為是相同。

1，1，5;1，5，1;5，1，1;

問有多少種不一樣分法。

輸入：n，k(6<n<=200，2<=k<=6)

輸出：一個整數(shù)，即不一樣分法。樣例

輸入：73

輸出：4{四種分法為：1，1，5;1，2，4;1，3，3;2，2，3;}【問題分析】：用f(i,j)表示將整數(shù)i分成j分分法，能夠劃分為兩類：

1)：j分中不包含1分法，為確保每份都>=2，能夠先那出j個1分到每一份，然后再把剩下i-j分成j份即可，分法有：f(i-j,j).2):j份中最少有一份為1分法，能夠先那出一個1作為單獨1份，剩下i-1再分成j-1份即可，分法有：f(i-1,j-1).所以：f(i,j)=f(i-j,j)