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

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

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

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

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

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

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

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

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

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