2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 排列與組合.doc
《2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 排列與組合.doc》由會員分享，可在線閱讀，更多相關《2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 排列與組合.doc（3頁珍藏版）》請在裝配圖網(wǎng)上搜索。
2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 排列與組合 課題：排列與組合 目標： 知識目標：如何利用程序就各種排列和組合 能力目標：排列組合的運用 重點：求出n的全排列和從m中取n個的組合 難點：算法的理解 板書示意： 1） 求全排列的算法 2） 求組合數(shù)的算法 授課過程： 例5：有3個人排成一個隊列，問有多少種排對的方法，輸出每一種方案？ 分析：如果我們將3個人進行編號，分別為1、2、3，顯然我們列出所有的排列，123，132，213，231，312，321共六種。可用循環(huán)枚舉各種情況，參考程序： program exam5; var i,j,k:integer; begin for I:=1 to 3 do for j:=1 to 3 do for k:=1 to 3 do if (i+j+k=6) and (i*j*k=6) then writeln(i,j,k); end. 上述情況非常簡單，因為只有3個人，但當有N個人時怎么辦？顯然用循環(huán)不能解決問題。下面我們介紹一種求全排列的方法。 設當前排列為P1 P2 ,…,Pn，則下一個排列可按如下算法完成： 1．求滿足關系式Pj-1 < Pj的J的最大值，設為I，即 I=max{j | Pj-1 < Pj , j = 2..n} 2．求滿足關系式Pi -1 < Pk的k的最大值，設為j，即 J=max{K | Pi-1 < Pk , k = 1..n} 3．Pi -1與Pj互換得 (P) = P1 P2 ,…,Pn 4．(P) = P1 P2 ,…, Pi-1 Pi,…, Pn部分的順序逆轉(zhuǎn)，得P1 P2 ,…, Pi-1 Pn Pn-1,…, Pi便是下一個排列。 例：設P1 P2 P3 P4 =3421 1．I= max{j | Pj-1 < Pj , j = 2..n} = 2 2．J=max{K | Pi-1 < Pk , k =1..n} = 2 3．P1與P2交換得到4321 4．4321的321部分逆轉(zhuǎn)得到4123即是3421的下一個排列。 程序設計如下： program exam5; const maxn = 100; var i,j,m,t : integer; p : array[1..maxn] of integer; count :integer; {排列數(shù)目統(tǒng)計變量} begin write(m:);readln(m); for i:=1 to m do begin p[i]:=i; write(i) end; writeln; count:=1; repeat {求滿足關系式Pj-1 < Pj的J的最大值，設為I} i:=m; while (i>1) and (p[i-1]>=p[i]) do dec(i); if i=1 then break; {求滿足關系式Pi -1 < Pk的k的最大值，設為j} j:=m; while (j>0) and (p[i-1]>=p[j]) do dec(j); if j=0 then break; {Pi -1與Pj互換得 (P) = P1 P2 ,…,Pm} t:=p[i-1];p[i-1]:=p[j];p[j]:=t; {Pi,…, Pm的順序逆轉(zhuǎn)} for j:=1 to (m-i+1) div 2 do begin t:=p[i+j-1];p[i+j-1]:=p[m-j+1];p[m-j+1]:=t end; {打印當前解} for i:=1 to m do write(p[i]); inc(count); writeln; until false; writeln(count) End. 例6：求N個人選取M個人出來做游戲，共有多少種取法？例如：N=4，M=2時，有12，13，14，23，24，34共六種。 分析：因為組合數(shù)跟順序的選擇無關。因此對同一個組合的不同排列，只需取其最小的一個（即按從小到大排序）。因此，可以設計如下算法： 1．最后一位數(shù)最大可達N，倒數(shù)第二位數(shù)最大可達N-1，…，依此類推，倒數(shù)第K位數(shù)最大可達N-K+1。 若R個元素組合用C1C2 …CR表示，且假定C1
- 配套講稿：
如PPT文件的首頁顯示word圖標，表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關 鍵 詞：
- 2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 排列與組合 2019 2020 年高 信息技術 全國青少年 奧林匹克 聯(lián)賽 教案 排列 組合
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學習交流，未經(jīng)上傳用戶書面授權(quán)，請勿作他用。
鏈接地址：http://www.hcyjhs8.com/p-2613277.html