《2022年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 排列與組合》由會員分享，可在線閱讀，更多相關《2022年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 排列與組合（3頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、2022年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 排列與組合
課題：排列與組合
目標：
知識目標：如何利用程序就各種排列和組合
能力目標：排列組合的運用
重點：求出n的全排列和從m中取n個的組合
難點：算法的理解
板書示意：
1） 求全排列的算法
2） 求組合數(shù)的算法
授課過程：
例5：有3個人排成一個隊列，問有多少種排對的方法，輸出每一種方案？
分析：如果我們將3個人進行編號，分別為1、2、3，顯然我們列出所有的排列，123，132，213，231，312，321共六種?？捎醚h(huán)枚舉各種情況，參考程序：
program exam5;
var
i,
2、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}
3、
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部分的順序逆轉，得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．432
4、1的321部分逆轉得到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;
5、 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}
6、 t:=p[i-1];p[i-1]:=p[j];p[j]:=t;
{Pi,…, Pm的順序逆轉}
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個人出
7、來做游戲，共有多少種取法？例如：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
8、Ci+1 := Ci +1 ，Ci+2 := Ci +1+1 ，…. ，CR := CR-1 +1
參考程序：
program exam6;
const maxn=10;
var i,j,n,m :integer;
c :array[1..maxn]of integer; {c數(shù)組記錄當前組合}
Begin
Write('n & m:'); readln(n,m);
for i:=1 to m do begin {初始化，建立第一個組合}
c[i]:=i;
write(c[i]);
end;
writeln;
while c[1]n-m+1) and ( j>0) do dec(j); {求I=max{J | Cj
2022年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 排列與組合
