it技術(shù)南開大學(xué)acm暑期集訓(xùn)之組合數(shù)學(xué)(已修改)
2025-06-10 16:19 本頁面
【正文】 南開大學(xué) ACM暑期集訓(xùn)之 組合數(shù)學(xué) 朱毅 20xx年 8月 主要參考文獻(xiàn) ? 《 組合數(shù)學(xué) 》 講義 ? 任課教師：黃連生 ? 清華大學(xué)計算機系 內(nèi)容提要 ? 排列組合 ? 鴿巢原理 ? 遞推關(guān)系與生成函數(shù) ? 二分圖的最大匹配 ? Polya計數(shù)原理的相關(guān)數(shù)學(xué)基礎(chǔ) 排列組合 圓排列 ? 6位女士和 6位先生圍著一張圓桌聚餐，要求安排女士和先生交替就座。問：有多少可能的安排方案。 ? 解 . 由于要求安排女士和先生交替就座，因此可以先安排六位女士坐下，兩位之間留出一個空位，然后再安排先生就座。安排六位女士坐下（圓排列）的方案數(shù)是 ? （種） 圓排列（續(xù)） ? 由于已經(jīng)有女士在位，安排先生在六個空位上就座時，就不再是圓排列了，因為原先被看成相同圓排列的六位先生的就座方式所產(chǎn)生的全體人員的圓排列是不同的。故安排先生在六個空位上就座的方案數(shù)是 ? 6！＝ 720 ? 于是我們得到滿足要求安排方案共計有 全排列生成算法 ? 如果將整數(shù) n從 『 1， 2。， n』 的一個排列中刪除，那么結(jié)果則是 『 1， 2。， n1』 的一個排列。 ? 給定一個 『 1， 2。， n1』 的排列，只要將 n插入到其中的 n個間隔（含頭尾） ? 算法描述： ? 從 『 1』 開始，將 2插入排列中得 『 1， 2』 的排列，以此類推，直至得到 『 1， 2。， n』 的排列 『 1， 2， 3』 全排列生成算法示例 1 2 2 1 ＝＝＝＝＝＝＝＝＝ 1 2 3 1 3 2 3 1 2 －－－－－－－－－－ 2 1 3 2 3 1 3 2 1 STL中生成排列數(shù)的函數(shù) ? include algorithm ? int A[] = {2, 3, 4, 5, 6, 1}。 ? prev_permutation(A, A+6)。 ? 結(jié)果： 2 3 4 5 1 6 ? int A[] = {2, 3, 4, 5, 6, 1}。 ? next_permutation(A, A+6)。 ? 結(jié)果： 2 3 4 6 1 5 相關(guān)練習(xí) ? NKOJ 1038 ? NKOJ 1108 鴿巢原理 鴿巢原理之一 鴿巢原理是組合數(shù)學(xué)中最簡單也是最基本 的原理，也叫抽屜原理。即 “若有 n個 鴿子巢， n+1個鴿子，則至少有 一個巢內(nèi)有至少有兩個鴿子。” 例１ 367人中至少有２人的生日相同。 例２ 10雙手套中任取 11只，其中至少有 兩只是完整配對的。 例３ 參加一會議的人中至少有２人認(rèn)識 的別的參加者的人數(shù)相等。 鴿巢原理之二 鴿巢原理二 m1 , m2 , … , m n都是正整數(shù)， 并有 m1 + m2 +… +m n－ n + 1個鴿子住進(jìn) n個 鴿巢，則至少對某個 i 有 第 i 個巢中至少有 mi個鴿子， i = 1 , 2 , … , n ． 上一小節(jié)的鴿巢原理一是這一原理的特殊 情況，即 m1 = m2 = … = m n= 2， m1 + m2 +… +m n－ n + 1 = n + 1 如若不然，則對任一 i， 都有第 i 個巢中的 鴿子數(shù) ≤mi－ 1 則 鴿巢原理之二 鴿子總數(shù) ≤ m1 + m2 +… +m n－ n ， 與假設(shè)相矛盾． 推論１ m只鴿子進(jìn) n個巢 ， 至少有一個巢 里有 「 － |只鴿子 ． n m 推論２ n(m－ 1) + 1只鴿子進(jìn) n個巢，至少 有一個巢內(nèi)至少有 m只鴿子． 推論３ 若 m1 , m2 , … , m n是正整數(shù)，且 r－ 1,則 m1,… , m n至少有一個 不小于 r m1 + … +m n n 遞歸關(guān)系和生成函數(shù) 定義： 對于序列 構(gòu)造一函數(shù)： 母函數(shù) , 210 ?aaa,)( 2210 ????? xaxaaxG?, 210 aaa稱函數(shù) G(x)是序列 的母函數(shù) 遞推關(guān)系 利用遞推關(guān)系進(jìn)行計數(shù)這個方法在算法分析中經(jīng)常用到，舉例說明如下： 例一 .Hanoi問題：這是個組合數(shù)學(xué)中的著名問題。 N個圓盤依其半徑大小，從下而上套在 A柱上，如下圖示。每次只允許取一個移到柱 B或 C上，而且不允許大盤放在小盤上方。若要求把柱 A上的 n個盤移到 C柱上請設(shè)計一種方法來，并估計要移動幾個盤次?，F(xiàn)在只有 A、 B、 C三根柱子可用。 遞推關(guān)系 Hanoi問題是個典型的問題，第一步要設(shè)計算法，進(jìn)而估計它的復(fù)雜性，集估計工作量。 算法： N=2時 第一步先把最上面的一個圓盤套在 B上 ? 第二步把下面的一個圓盤移到 C上 最后把 B上的圓盤移到 C上 到此轉(zhuǎn)移完畢 A B C 遞推關(guān)系 ? 對于一般 n個圓盤的問題， ? 假定 n1個盤子的轉(zhuǎn)移算法已經(jīng)確定。 ? 先把上面的 n1個圓盤經(jīng)過 C轉(zhuǎn)移到 B。 ? 第二步把 A下面一個圓盤移到 C上 ?? ? 最后再把 B上的 n1個圓盤經(jīng)過 A轉(zhuǎn)移到 C上
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1