ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)

1、第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.1 組合數(shù)學(xué)研究對(duì)象 組合數(shù)學(xué)研究的主要內(nèi)容是依據(jù)一定的規(guī)則來安排某些事務(wù)的有關(guān)數(shù)學(xué)問題。這些問題包括四個(gè)方面： 1. 這種安排是否存在，即存在性問題 2. 如果符合要求的安排是存在的，那么這樣的安排又有多少，即計(jì)數(shù)問題 3. 怎樣構(gòu)造這種安排，即算法構(gòu)造問題 4. 如果給出了最優(yōu)化標(biāo)準(zhǔn)，又怎樣得到得到最優(yōu)安排第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.1 組合數(shù)學(xué)1. 存在性問題實(shí)際生活中的各種問題，有些可以當(dāng)機(jī)立斷判定其有解還是無解。但也有不少問題一時(shí)難以判定。例如，宴會(huì)上，奇數(shù)位客人能否在晚會(huì)上與他人握手奇數(shù)次競(jìng)賽時(shí)不可能出現(xiàn)專門判定某個(gè)問題有解或無解的試題。

2、但往往會(huì)在測(cè)試數(shù)據(jù)中加入無解的數(shù)據(jù)。第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.1 組合數(shù)學(xué)2. 計(jì)數(shù)問題如果一個(gè)組合問題的解是存在的，自然會(huì)問有多少不同解例如，將8個(gè)“車”放在88的國(guó)際象棋棋盤上，如果他們兩兩不能互吃，那么稱8個(gè)“車”處于一個(gè)安全狀態(tài)。顯然這種安全狀態(tài)是存在的。問有多少種不同的安全狀態(tài)。 這就是一個(gè)計(jì)數(shù)問題。一般分為兩種類型：一種是計(jì)算某種特性的對(duì)象有多少；另一種是枚舉類型，把所有具有某種特性的對(duì)象都列舉出來。第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.1 組合數(shù)學(xué)3. 構(gòu)造性算法一個(gè)組合問題，已經(jīng)判定解是存在的，甚至已經(jīng)推知有多少解，但關(guān)鍵還在于把解構(gòu)造出來，有的哪怕出一個(gè)解也好。如魔方

3、問題，正交拉丁問題。第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.1 組合數(shù)學(xué)4. 優(yōu)化問題一個(gè)問題的構(gòu)造性算法可能不止一種，自然面臨如何擇優(yōu)，如何改進(jìn)，使得答案盡快地解出來。比如動(dòng)態(tài)規(guī)劃和線性規(guī)劃問題的解決方法。第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.1 組合數(shù)學(xué)組合問題的基本解題方法1. 從組合學(xué)基本概念基本原理出發(fā)的常規(guī)方法容斥原理Polya原理鴿巢原理遞歸方法生成函數(shù)方法第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.1 組合數(shù)學(xué)組合問題的基本解題方法2. 通常與問題所涉及的組合數(shù)學(xué)概念無關(guān)的非常規(guī)方法。主要用于解那些需要獨(dú)立思考見解獨(dú)到和有所創(chuàng)新的問題。 數(shù)學(xué)歸納法第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.1 組合

4、數(shù)學(xué)組合問題的基本解題方法3. 殊途同歸方法 從不同的角度討論計(jì)數(shù)問題，以建立組合等式 例如，對(duì)沒有三條對(duì)角線交于一點(diǎn)的凸多邊形，計(jì)算各邊及對(duì)角線所組成的互不重疊的區(qū)域個(gè)數(shù)。第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.1 組合數(shù)學(xué)組合問題的基本解題方法4. 數(shù)論方法運(yùn)用奇偶性，整除性等數(shù)論性質(zhì)進(jìn)行存在性問題的分析與推理。例子：設(shè)n位客人，在晚會(huì)上每人與他人握手d次，d是奇數(shù)，證明n是偶數(shù)。第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.3 數(shù)論常見的數(shù)論問題 1. 數(shù)的冪運(yùn)算 2. 歐拉定理的應(yīng)用 3. 素?cái)?shù)測(cè)試4. Pell方程5. 其它 第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.4 計(jì)算幾何基本概念點(diǎn)線（線段，直線

5、）面（三角形，圓，多邊形（凸，凹）體（空間幾何）第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.4 計(jì)算幾何點(diǎn) Pointtypedef struct TPoint double x; double y; /double z;TPoint;第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.4 計(jì)算幾何線段 Segmenttypedef struct TSegment TPoint t2; Tsegment;第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.4 計(jì)算幾何直線 Linetypedef struct TLine /直線方程的系數(shù) double a, b, c;TLine; ax + by + c = 0第10講:ACM競(jìng)賽

6、之?dāng)?shù)學(xué)基礎(chǔ)10.4 計(jì)算幾何射線 radialtypedef struct TRadial TPoint p; TPoint INF;(無窮遠(yuǎn)出一點(diǎn))TRadial;第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.4 計(jì)算幾何三角形 Triangletypedef struct TTriangle TPoint t3;TTriangle;第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.4 計(jì)算幾何圓 Circletypedef struct TCircle double r; TPoint centre;TCircle;第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.4 計(jì)算幾何多邊形 Polygontypedef struct

7、 TPolygon TPoint pMaxNode; int n;TPolygon; 第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.4 計(jì)算幾何點(diǎn)線面之間的關(guān)系點(diǎn)與點(diǎn)點(diǎn)與線點(diǎn)與面點(diǎn)與圓點(diǎn)與多邊形線與線線與面面與面第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.4 計(jì)算幾何點(diǎn)與點(diǎn)（距離）double distance(TPoint p1, TPoint p2) /計(jì)算平面上兩個(gè)點(diǎn)之間的距離TPoint p; p.x = p1.x p2.x; p.y = p1.y p2.y; return sqrt(p.x * p.x + p.y * p.y); 多維矢量（空間）點(diǎn)的距離與此類似第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.4

8、計(jì)算幾何點(diǎn)與線點(diǎn)是否在直線上點(diǎn)是否在線段上點(diǎn)到直線的距離點(diǎn)關(guān)于直線的對(duì)稱點(diǎn)第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.4 計(jì)算幾何點(diǎn)與面點(diǎn)是否在平面點(diǎn)到平面的距離第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.4 計(jì)算幾何點(diǎn)與多邊形點(diǎn)是否在圓內(nèi)（到圓心的距離）點(diǎn)是否在多邊形內(nèi)第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.4 計(jì)算幾何線與線判斷兩條線段是否相交判斷線段與直線是否相交判斷直線與直線是否相交若相交求交點(diǎn)第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.4 計(jì)算幾何線與面線與圓（線與圓的關(guān)系）直線劃分多邊形第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.5 概率論隨機(jī)數(shù)在現(xiàn)實(shí)計(jì)算機(jī)上無法產(chǎn)生真正的隨機(jī)數(shù)，在概率算法中使用的隨機(jī)數(shù)都是一定程度

9、上隨機(jī)的，即偽隨機(jī)數(shù)。線性同余法是產(chǎn)生偽隨機(jī)數(shù)的最常用的方法。由線性同余法產(chǎn)生的隨機(jī)序列a0,a1,an滿足其中b0，c0，dm。d稱為該隨機(jī)序列的種子。從直觀上看，m應(yīng)取得充分大，因此可取m為機(jī)器大數(shù)，另外應(yīng)取gcd(m,b)=1，因此可取b為一素?cái)?shù)。第10講:ACM競(jìng)賽之?dāng)?shù)學(xué)基礎(chǔ)10.5 概率論數(shù)值概率算法：用隨機(jī)投點(diǎn)法計(jì)算值 設(shè)有一半徑為r的圓及其外切四邊形。向該正方形隨機(jī)地投擲n個(gè)點(diǎn)。設(shè)落入圓內(nèi)的點(diǎn)數(shù)為k。由于所投入的點(diǎn)在正方形上均勻分布，因而所投入的點(diǎn)落入圓內(nèi)的概率為 。所以當(dāng)n足夠大時(shí)，k與n之比就逼近這一概率。從而 public static double darts(int n) / 用隨機(jī)投點(diǎn)法計(jì)算值 int k=0; for (int i=1;i =n;i+) double x=dart.fRandom(); double y=dart.fRandom(); if (x*x+