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