Noi初賽問(wèn)題求解專題

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

解析

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

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

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

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

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

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

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

SIMPLEANDCOOLWWW.SBJSHWK.COM||+1813571145|OYSBSTREET12345,OYSBISMADEINCHINA78常見(jiàn)模型MODELSIMPLEANDCOOLWWW.SBJSHWK.COM||+1813571145|OYSBSTREET12345,OYSBISMADEINCHINA全錯(cuò)位排列

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

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

7次【分析】

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

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