信息學(xué)競(jìng)賽中數(shù)學(xué)知識(shí)

信息學(xué)競(jìng)賽中數(shù)學(xué)知識(shí)第一頁(yè)，共13頁(yè)。邏輯代數(shù)主要掌握?輯代數(shù)的邏輯運(yùn)算，邏輯運(yùn)算和Pascal中的邏輯運(yùn)算相似，只不過(guò)符號(hào)不同而已。邏輯代數(shù)的運(yùn)算符和Pascal的運(yùn)算符有如下對(duì)應(yīng)關(guān)系：┓：NOT〔非〕∨：OR〔或〕∧：AND〔與〕它們的運(yùn)算順序和Pascal中的規(guī)定是一致的，“非〞優(yōu)先級(jí)最高，“或〞最低。怎么來(lái)記憶符號(hào)和優(yōu)先級(jí)順序?第二頁(yè)，共13頁(yè)。邏輯代數(shù)運(yùn)算練習(xí)題1.設(shè)A=true，B=false，C=true，D=false，以下邏輯運(yùn)算表達(dá)式值為真的是〔〕。A.(A∧B)∨(C∧D∨A)B.((A∧B)∨C)∧DC.(B∨C∨D)∧D∧AD.A∧(D∨C)∧B2.設(shè)A=B=true，C=D=false，以下邏輯運(yùn)算表達(dá)式值為假的有〔〕。A.(?A∧B)∨(C∧D∨A)B.?(((A∧B)∨C)∧D)C.A∧(B∨C∨D)∨DD.(A∧(D∨C))∧B

第三頁(yè)，共13頁(yè)。排列組合問(wèn)題此處我們只討論最簡(jiǎn)單的排列組合問(wèn)題。乘法原理：完成一件事可以分為n個(gè)步驟，每個(gè)步驟又可分為a1,a2,a3，…，an個(gè)不同的方法，那么完成此事的總方法有a1×a2×a3×…×an種方法。加法原理：如果完成一件任務(wù)有n類(lèi)方法，在第一類(lèi)方法中有m1種不同方法，在第二類(lèi)方法中有m2種不同方法……在第n類(lèi)方法中有mn種不同方法，那么完成這件任務(wù)共有N=m1+m2+…+mn第四頁(yè)，共13頁(yè)。排列組合問(wèn)題加法原理典型例題：從甲地到乙地，可以乘火車(chē)，也可以乘汽車(chē)，還可以乘輪船。一天中火車(chē)有4班，汽車(chē)有3班，輪船有2班。問(wèn)：一天中乘坐這些交通工具從甲地到乙地，共有多少種不同走法？

乘法原理典型例題：從甲地到乙地有2條路，從乙地到丙地有3條路，從丙地到丁地也有2條路。問(wèn)：從甲地經(jīng)乙、丙兩地到丁地，共有多少種不同的走法？第五頁(yè)，共13頁(yè)。排列組合問(wèn)題排列及計(jì)算公式從n個(gè)不同元素中，任取m(m≤n)個(gè)元素按照一定的順序排成一列，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)排列；從n個(gè)不同元素中取出m(m≤n)個(gè)元素的所有排列的個(gè)數(shù)，叫做從n個(gè)不同元素中取出m個(gè)元素的排列數(shù)，用符號(hào)p(n,m)表示.p(n,m)=n(n-1)(n-2)……(n-m+1)=n!/(n-m)!(規(guī)定0!=1).2．組合及計(jì)算公式從n個(gè)不同元素中，任取m(m≤n)個(gè)元素并成一組，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)組合；從n個(gè)不同元素中取出m(m≤n)個(gè)元素的所有組合的個(gè)數(shù)，葉做從n個(gè)不同元素中取出m個(gè)元素的組合數(shù).用符號(hào)c(n,m)表示.c(n,m)=p(?,m)/m!=n!/((n-m)!*m!)；c(n,m)=c(n,n-m);第六頁(yè)，共13頁(yè)。排列組合練習(xí)題1.一個(gè)班級(jí)有45名同學(xué)，從中任意選取2名同學(xué)參加作文比賽，共有多少種不同的選法？2.5個(gè)同學(xué)到飯?zhí)门抨?duì)打飯，共有多少種不同的排隊(duì)方法？3.用0，1，2，3，4組合可以得到多少個(gè)無(wú)重復(fù)數(shù)字的四位數(shù)？4.兩條平行的直線L1和L2，L1上有3個(gè)點(diǎn)，L2上有5個(gè)點(diǎn)，問(wèn)由這些點(diǎn)總共可以組成多少個(gè)三角形？5.書(shū)架上有4本不同的書(shū)A、B、C、D。其中A和B是紅皮的，C和D是黑皮的。把這4本書(shū)擺在書(shū)架上，滿足所有黑皮的書(shū)都排在一起的擺法有_____種。滿足A必須比C靠左，址有紅皮的書(shū)要擺放在一起，所有黑皮的書(shū)要擺放在一起，共有______種擺法。

第七頁(yè)，共13頁(yè)。集合集合：由確定的、互相區(qū)別的一些對(duì)象組成的總體。集合的每個(gè)對(duì)象稱(chēng)為元素。如初一〔11〕班同學(xué)組成一個(gè)集合，里面的每個(gè)同學(xué)稱(chēng)為元素。常用的集合表示法：列舉法、描述法集合的運(yùn)算：并〔∪〕、交〔∩〕、差〔-〕、補(bǔ)〔~或ˉ〕

第八頁(yè)，共13頁(yè)。集合運(yùn)算例題設(shè)全集I={0,1,2,3,4,5,6,7,8,9}，A={2,4}，B={4,5,6,7}，C={0,8,9}，D={1,2,3}，那么A∪B=A∪B∪C∪D=A∩B=A-B=B-A=C-A=~A=B=第九頁(yè)，共13頁(yè)。集合問(wèn)題的圖示法文氏圖：由矩形、圓形及內(nèi)部的點(diǎn)組成。

矩形：其內(nèi)部的點(diǎn)表示全集的所有元素；

矩形內(nèi)的圓〔或其它閉曲線〕：表示不同的集合；

圓〔或閉曲線〕內(nèi)部的點(diǎn)：表示相應(yīng)集合的元素。第十頁(yè)，共13頁(yè)。文氏圖例題某單位的100名員工進(jìn)展調(diào)查，結(jié)果發(fā)現(xiàn)他們喜歡看球賽和電影、戲劇。其中58人喜歡看球賽，38人喜歡看戲劇，52人喜歡看電影，既喜歡看球賽又喜歡看戲劇的有18人，既喜歡看電影又喜歡看戲劇的有16人，三種都喜歡看的有12人，那么只喜歡看電影的有：

A、22人B、28人C、30人D、36人第十一頁(yè)，共13頁(yè)。文氏圖練習(xí)有47本書(shū)，有27本是小說(shuō)，32本是紅皮的，6不既不是紅皮的，也不是小說(shuō)。問(wèn)有多少本紅皮小說(shuō)？某班50人，語(yǔ)文、數(shù)學(xué)考試中，語(yǔ)文及格45人，數(shù)學(xué)及格42人，兩門(mén)都不及格2人，那么兩門(mén)都不及格有多少人？外語(yǔ)學(xué)校有英語(yǔ)、法語(yǔ)、日語(yǔ)教師總共27人，其中只能教英語(yǔ)的有8人，只能教日語(yǔ)的有6人，能教英