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

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

2、束。上面的情況很簡單，因?yàn)橹挥腥齻€人，但是如果有n個人呢？顯然，流通不能解決問題。接下來，我們介紹一種完全置換的方法。假設(shè)當(dāng)前的排列是P1 P2，Pn，下一個排列可以根據(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互換時，pn4.(p)=p1p2，pi-1pi，pn，其順序相反，以及p1p2，pi-1pn-1，是下一個排列。例如：讓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的下一個排列。該程序設(shè)計如下：程序示例5；常數(shù)maxn=100var i，j，m，t :整數(shù)；p :陣列1.整數(shù)的maxn;計數(shù)：整數(shù)；排列編號的統(tǒng)計變量開始寫(m :)；read ln(m)；對于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的順序顛倒了對于j:=1至(m-i 1) div 2，請開始t :=pI j-1；pI j-1:=pm-j 1；pm-j 1:=t結(jié)束；打印當(dāng)前解決方案對于i:=1至m，寫(pI)；inc(計數(shù))；writeln直到錯誤；writeln(計數(shù))結(jié)束。例6:讓N個人選擇M個人玩游戲。有多少種方法？例如，當(dāng)N=4和M=2時，有六種：12，13，14，23，24和34。分析：因?yàn)榻M合的數(shù)量與順序的選擇無關(guān)。因此，對于同一組合的不同排列，只需要取最小的一個(即從小到大排序)。因此，可以設(shè)計以下算法：1.最后一個數(shù)字最多可以是N，第二個最后一個數(shù)字最多可以是N-1，等等，第K個最后一個數(shù)字