it技術《南開大學acm暑期集訓之組合數(shù)學》-全文預覽
【正文】 為二。 119 ?? ?? nnn abb119 ?? ?? nnn baa19 ?na121 ?nppp ? np1?nb121 ?nppp ?5?np nppp ?21 (222)是關于序列 和 的連立關系。 na n ?nb n ? 故有： 119 ?? ?? nnn baa119 ?? ?? nnn abb{? 1 ,8 11 ?? ba)222( ?? 也有類似解釋。即： 遞推關系 令 )21)(1(2 )21(1()1()21(211)(xxB ) xAB ) ((AxxxBxAxBxAxH???????????????xxBABA ????? )2()( 如何從母函數(shù)得到序列 ？下面介紹一種化為部分分數(shù)的算法。當然，利用遞推關系 (221)式也可以依次求得 ，這樣的連鎖反應關系，叫做遞推關系。以此類推。 N=4， 5， … 以此類推。 算法： N=2時 第一步先把最上面的一個圓盤套在 B上 ? 第二步把下面的一個圓盤移到 C上 最后把 B上的圓盤移到 C上 到此轉移完畢 A B C 遞推關系 ? 對于一般 n個圓盤的問題， ? 假定 n1個盤子的轉移算法已經(jīng)確定。每次只允許取一個移到柱 B或 C上，而且不允許大盤放在小盤上方。 例２ 10雙手套中任取 11只，其中至少有 兩只是完整配對的。 ? next_permutation(A, A+6)。 n1』 的排列，只要將 n插入到其中的 n個間隔（含頭尾） ? 算法描述： ? 從 『 1』 開始，將 2插入排列中得 『 1， 2』 的排列，以此類推，直至得到 『 1， 2。故安排先生在六個空位上就座的方案數(shù)是 ? 6！＝ 720 ? 于是我們得到滿足要求安排方案共計有 全排列生成算法 ? 如果將整數(shù) n從 『 1， 2。南開大學 ACM暑期集訓之 組合數(shù)學 朱毅 20xx年 8月 主要參考文獻 ? 《 組合數(shù)學 》 講義 ? 任課教師：黃連生 ? 清華大學計算機系 內容提要 ? 排列組合 ? 鴿巢原理 ? 遞推關系與生成函數(shù) ? 二分圖的最大匹配 ? Polya計數(shù)原理的相關數(shù)學基礎 排列組合 圓排列 ? 6位女士和 6位先生圍著一張圓桌聚餐，要求安排女士和先生交替就座。安排六位女士坐下（圓排列）的方案數(shù)是 ? （種） 圓排列（續(xù)） ? 由于已經(jīng)有女士在位，安排先生在六個空位上就座時，就不再是圓排列了，因為原先被看成相同圓排列的六位先生的就座方式所產(chǎn)生的全體人員的圓排列是不同的。 ? 給定一個 『 1， 2。 ? 結果： 2 3 4 5 1 6 ? int A[] = {2, 3, 4, 5, 6, 1}?！? 例１ 367人中至少有２人的生日相同。 N個圓盤依其半徑大小，從下而上套在 A柱上，如下圖示。 遞推關系 Hanoi問題是個典型的問題，第一步要設計算法，進而估計它的復雜性，集估計工作量。 n=2時已給出算法； n=3時，第一步便利用算法把上面兩個盤移到 B上，第二步再把第三個圓盤轉移到柱 C上；最后把柱 B上兩個圓盤轉移到柱 C上。 n=2時，算法是對的，因此， n=3是算法是對的。反過來也一樣，求得了母函數(shù)，對應的序列也就可得而知了。 ,)3()2()1()( 32 ????? xhxhxhxH,)2(2)1(2 )(2 ) ?????? xhxhxxH_ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _????????32)]2(2)3([ )]1(2)2([)1()()21(xhhxhhxhxHx遞推關系 根據(jù) (221)， ?? ,1)2(2)3(,1)1(2)2(,1)1( ????? hhhhh)1/()()21( 32 xxxxxxHx ???????? ? 或利用遞推關系 (221)有 1)1(2)2(:2 ?? hhx1)2(2)3(:3 ?? hhx???? )? _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _)1/()(2)( 2 xxxxHxxH ?????1)2(2 1)1( ,1)1(2)( ???? hnhnh遞推關系 上式左端為： xxHxhxHxhxh ?????? )()1()()3()2( 32 ? 右端第一項為： )(2x ])2()1([2)2(2)1(2 232xHxhxhxxhxh?????? ?? 右端第二項為： )1/(232 xxxx ???? ?遞推關系 整理得 xxxxxxHx??????11
教學課件相關推薦
鄂ICP備17016276號-1