高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 排列與組合

1、排列和組合主題：排列和組合目標(biāo)：知識(shí)目標(biāo)：如何在各種安排和組合中使用程序能力目標(biāo)：排列組合的應(yīng)用重點(diǎn)：找出N的整體排列，從m中找出N的組合難點(diǎn)：對(duì)算法的理解黑板上寫著：1)完全置換算法2)尋找組合數(shù)的算法教學(xué)過(guò)程：例5:有三個(gè)人排隊(duì)，問(wèn)有多少種方法，然后輸出每個(gè)方案。分析：如果我們數(shù)三個(gè)人，即1、2和3，顯然我們列出了所有的安排，包括123、132、213、231、312和321。通過(guò)循環(huán)列舉各種情況，參考程序：程序示例5；varI，j，k:integer開始對(duì)于I:=1比3 do對(duì)于j:=1至3 do對(duì)于k:=1至3 do如果(i j k=6)和(i*j*k=6 ),則寫入(I，j，k)；結(jié)

2、束。上面的情況很簡(jiǎn)單，因?yàn)橹挥腥齻€(gè)人，但是如果有n個(gè)人呢？顯然，流通不能解決問(wèn)題。接下來(lái)，我們介紹一種完全置換的方法。假設(shè)當(dāng)前的排列是P1 P2，Pn，下一個(gè)排列可以根據(jù)以下算法完成：1.找到滿足關(guān)系Pj-1 Pj的j的最大值，并將其設(shè)置為I，即I=最大j | Pj-1 Pj，j=2.n2.找到滿足關(guān)系Pi -1 Pk的k的最大值，并將其設(shè)置為j，即。j=最大K | Pi-1 Pk，k=1.n(p)=p1p2，當(dāng)pi-1與Pj互換時(shí)，pn4.(p)=p1p2，pi-1pi，pn，其順序相反，以及p1p2，pi-1pn-1，是下一個(gè)排列。例如：讓P1P2P3P4=34211.I=最大j | Pj

3、-1 Pj，j=2.n=22.j=最大K | Pi-1 Pk，k=1.n=23.P1和P2交換到43214.4321的321部分是相反的，4123是3421的下一個(gè)排列。該程序設(shè)計(jì)如下：程序示例5；常數(shù)maxn=100var i，j，m，t :整數(shù)；p :陣列1.整數(shù)的maxn;計(jì)數(shù)：整數(shù)；排列編號(hào)的統(tǒng)計(jì)變量開始寫(m :)；read ln(m)；對(duì)于i:=1至m，開始pI:=I；寫(I)結(jié)束；writelncount :=1；重復(fù)找到滿足關(guān)系Pj-1 Pj的j的最大值，并將其設(shè)置為II :=m；而(i1)和(pi-1=pi)做dec(I)；如果i=1，則斷開；找到滿足關(guān)系Pi -1 Pk的k

4、的最大值，并將其設(shè)置為jj:=m。而(j0)和(pi-1=pj)做dec(j)；如果j=0，則斷開；pi-1的(p)和Pj=p1p2，pmt :=pI-1；pI-1:=pj；pj:=t。 pi，pm的順序顛倒了對(duì)于j:=1至(m-i 1) div 2，請(qǐng)開始t :=pI j-1；pI j-1:=pm-j 1；pm-j 1:=t結(jié)束；打印當(dāng)前解決方案對(duì)于i:=1至m，寫(pI)；inc(計(jì)數(shù))；writeln直到錯(cuò)誤；writeln(計(jì)數(shù))結(jié)束。例6:讓N個(gè)人選擇M個(gè)人玩游戲。有多少種方法？例如，當(dāng)N=4和M=2時(shí)，有六種：12，13，14，23，24和34。分析：因?yàn)榻M合的數(shù)量與順序的選擇無(wú)關(guān)。因此，對(duì)于同一組合的不同排列，只需要取最小的一個(gè)(即從小到大排序)。因此，可以設(shè)計(jì)以下算法：1.最后一個(gè)數(shù)字最多可以是N，第二個(gè)最后一個(gè)數(shù)字最多可以是N-1，等等，第K個(gè)最后一個(gè)數(shù)字