Noi初賽問題求解專題

LET’SMAKETHINGSSIMPLEANDCOOL從離散數(shù)學

解析

問題求解——ByDirak嵊州市城關(guān)中學宋子健CONTEST一覽SIMPLEANDCOOLWWW.SBJSHWK.COM||+1813571145|OYSBSTREET12345,OYSBISMADEINCHINA2目標排列組合和基礎(chǔ)原理：排列，組合，鴿巢，容斥淺談常見模型：Catalan，全錯位數(shù)學建模：排序問題演練：習題CombinatorialSIMPLEANDCOOL離散數(shù)學3WWW.SBJSHWK.COM||+1813571145|OYSBSTREET12345,OYSBISMADEINCHINA名詞解釋：離散數(shù)學即組合數(shù)學，一般研究圖論、代數(shù)結(jié)構(gòu)、數(shù)理邏輯等離散對象，所謂離散即不連續(xù)。排列數(shù)P(n,m)：從n個數(shù)中取m個數(shù)進行排列，所可能取得的情況種數(shù)。計算公式：引申：m個數(shù)的全排列種數(shù)為m！組合數(shù)C(n,m)：從n個數(shù)中取m個數(shù)所可能的情況種數(shù)計算公式：引申：C(n,m)=c(n,n-m)4離散數(shù)學CombinatorialWWW.SBJSHWK.COM||+1813571145|OYSBSTREET12345,OYSBISMADEINCHINASIMPLEANDCOOL容斥原理

用韋恩圖表示為右圖。A、B、C為三個獨立的集合，得：即：將所有元素合并，再去掉重復計算的部分，即為總共的元素個數(shù)。Combinatorial鴿巢原理也稱抽屜原理。有n個鴿巢和(kn+1)只鴿子，將鴿子放進鴿巢，則至少有一個鴿巢有(k+1)只及以上的鴿子?？捎梅醋C法證明。實際問題中的鴿子和鴿巢往往要抽象得多，常需要根據(jù)題意自己構(gòu)造。SIMPLEANDCOOLWWW.SBJSHWK.COM||+1813571145|OYSBSTREET12345,OYSBISMADEINCHINA5離散數(shù)學WWW.SBJSHWK.COM||+1813571145|OYSBSTREET12345,OYSBISMADEINCHINACatalan數(shù)

設(shè)有一(n+2)邊形（只考慮凸多邊形），則可以畫出(n-1)條不相交的對角線將其分割成n個三角形，設(shè)所有可能的情況種數(shù)為，且定義。

先以一條邊為底邊，顯然該邊所在的三角形會把n邊形分成兩個部分（如圖是一種可能的情況），設(shè)左邊有(k+2)條邊，則右邊有(n+2)-(k+2)-1=(n-k-1)條邊。

根據(jù)乘法原理，這樣可能的情況數(shù)為

由于k的大小可以從0變化到n-1，∴得：

6常見模型MODELSIMPLEANDCOOLMODEL數(shù)列即著名的Catalan數(shù)列。用生成函數(shù)的知識可得它的通項公式：常見Catalan應(yīng)用：由1和-1各n個組成的數(shù)列滿足對于任一正整數(shù)k,該數(shù)列可能種數(shù)n個元素的出棧順序可能數(shù)有n個節(jié)點的二叉樹可能形態(tài)數(shù)……

SIMPLEANDCOOLWWW.SBJSHWK.COM||+1813571145|OYSBSTREET12345,OYSBISMADEINCHINA78常見模型MODELSIMPLEANDCOOLWWW.SBJSHWK.COM||+1813571145|OYSBSTREET12345,OYSBISMADEINCHINA全錯位排列

有1~n號信箱和1~n號郵件，每一封郵件都沒有放進所對應(yīng)的信箱，求放郵件的可能情況種數(shù)。利用容斥原理：

得通項公式：利用遞推法：MATHMODELING【例1】對于一個有5個元素的數(shù)組，最少需要幾次比較才能保證數(shù)組有序？【答案】

7次【分析】

由于原題的解析太(看)繁(不)瑣(懂)，我們引入決策樹的概念來解決題目。我們對元素進行比較時只有兩個結(jié)果：a>=b或a<b,由此根據(jù)兩個結(jié)果引發(fā)兩種不同的決策，因此該決策樹是二叉樹。因為有5個元素，最后排列結(jié)果有5！=120種，即該決策樹有120個葉子節(jié)點，因為葉子節(jié)點的深度就是所需的比較次數(shù)，而120>2^6，因此深度為6次或更少的決策樹葉子節(jié)點沒有120個，不能確定排列順序。故答案為7次。

對于n個元素的排列，需要比較次數(shù)學建模SIMPLEANDCOOLWWW.SBJSHWK.COM||+1813571145|OYSBSTREET12345,OYSBISMADEINCHINA9MATHMODELING【例2】

將數(shù)組{8,23,4,16,77,-5,53,100}中的元素從小到大排列，至少需要交換幾次？【答案】

5次【分析】

排列后的數(shù)組為{-5,4,8,16,23,53,77,100}。發(fā)現(xiàn)元素位置的變化如圖：SIMPLEANDCOOLWWW.SBJSHWK.COM||+1813571145|OYSBSTREET12345,OYSBISMADEINCHINA10數(shù)學建模11數(shù)學建模MATHMODELINGSIMPLEANDCOOLWWW.SBJSHWK.COM||+1813571145|OYSBSTREET12345,OYSBISMADEINCHINA我們畫一個有向圖，從初始狀態(tài)位置上的數(shù)向排列后位置上的數(shù)引一條有向邊。發(fā)現(xiàn)形成了幾個環(huán)（包括自指的節(jié)點）。如果要在最少次數(shù)內(nèi)排序，顯然兩個環(huán)中的元素交換位置是沒有意義的（因為肯定還要換回來），因此只需要將各個環(huán)交換好順序即可。顯然一個包含k個元素的環(huán)排序需要交換(k-1)次，所以總共要交換5次。對于N個元素的數(shù)組，設(shè)形成n個環(huán)，第i個環(huán)有k[i]個元素。則需要交換：(k[1]-1)+(k[2]-1)+…+(k[n]-1)=N-n次。EXPERIENCE撒經(jīng)驗WWW.SBJSHWK.COM||+1813571145|OYSBSTREET12345,OYSBISMADEINCHINASIMPLEANDCOOL12EXERSICESIMPLEANDCOOLWWW.SBJSHWK.COM||+1813571145|OYSBSTREET12345,OYSBISMADEINCHINA習題13在圓周上有7個點，在任兩個點之間連一條弦，假設(shè)任三條弦不交于一點。問把7邊形分成幾個三角形定義字符串的基本操作為：刪除一個字符、插入一個字符和將一個字符修改成另一個字符這三種操作。將字符串A變成字符串B的最少操作步數(shù)，稱為字符串A到字符串B的編輯距離。字符串"ABCDEFG"到字符串"BADECG"的編輯距離為________。III.在NOI期間，主辦單位為了歡迎來自全國各地的選手，舉行了盛大的晚宴。在第十八桌，有5名大陸選手和5名港澳選手共同進膳。為了增進交流，他們決定相隔就坐，即每個大陸選手左右相鄰的都是港澳選手、每個港澳選手左右相鄰的都是大陸選手。那么，這一桌共有_________種不同的就坐方案。注意：如果在兩個方案中，每個選手左邊相鄰的選手均相同，則視為同一個方案。IV.現(xiàn)有80枚硬幣，其中有一枚假幣，重量較輕，給你一個天平，最少需要稱量幾次才能找出假幣？14送學習資料哦，祝早日轉(zhuǎn)Vijos/C++↓↓↓↓↓↓SIMPL