Đăng ký Đăng nhập
Trang chủ Skkn tổ hợp, chỉnh hợp, hoán vị...

Tài liệu Skkn tổ hợp, chỉnh hợp, hoán vị

.DOC
26
364
90

Mô tả:

PHẦN I : MỞ ĐẦU A.LÝ DO CHỌN CHUYÊN ĐỀ Toán học tổ hợp (hay giải tích tổ hợp, đại số tổ hợp, lý thuyết tổ hợp) là một ngành toán học rời rạc, nghiên cứu về các cấu hình kết hợp các phần tử của một tập hữu hạn phần tử. Các cấu hình đó là các hoán vị, chỉnh hợp, tổ hợp,... các phần tử của một tập hợp. Môn toán này có liên quan đến nhiều lĩnh vực khác của toán học, như đại số, lý thuyết xác suất, lý thuyết ergod (ergodic theory) và hình học, cũng như đến các ngành ứng dụng như khoa học máy tính và vật lí thống kê....nên có nhều vấn đề rất sâu phải có trình độ cao. Tuy nhiên, với trình độ phổ thông cơ sở vẫn có thể tiếp cận và ứng dụng giải nhiều bài toán rất hay gặp trong thực tế cũng như các đề thi ( Thi HSG, thi tuyển sinh..). Đối với bộ môn tin học trong khi lập trình chúng ta thường xuyên phải làm các thao tác sắp xếp, phân hoạch, lấp tập con thành tập hợp lớn hơn … trên một tập hợp các phần tử hữu hạn và rời rạc nghĩa là thường xuyên đụng chạm đến khái niệm của giải tích và tổ hợp đó là : + Hoán vị + Chỉnh hợp +Tổ hợp B.PHẠM VI MỤC ĐÍCH CHUYÊN ĐỀ 1. Phạm vi chuyên đề: - Do đặc thù của học sinh THCS còn hạn chế về kiến thức toán học và kỹ thuật lập trình và khả năng bản thân còn có nhiều hạn chế, nên chuyên đề chỉ nêu được một số thuật giải mẫu và các ví dụ minh hoạ về “ tổ hợp, chỉnh hợp, hoán vị ”mà qua quá trình học tập giảng dạy tôi đã sưu tầm và tích lũy được . 2. Mục đích của chuyên đề: -Giúp học sinh hiểu được các khái niệm về tổ hoán vị, chỉnh hợp ,tổ hợp và các 1 thuật toán, cách cài đặt chương trình . -Giúp học sinh chủ động lĩnh hội kiến thức hơn, phát huy vai trò tích cực trong học tập của học sinh. Khắc sâu những kiến thức cơ bản, học sinh biết áp dụng , tìm tòi, khám phá không ngừng năng cao chất lượng bồi dưỡng HSG và học bộ môn tin học trong nhà trường . PHẦN II : NỘI DUNG CỤ THỂ A. CƠ SỞ LÝ LUẬN Thông qua chuyên đề này học sinh biết vận dụng và được cung cấp các kiến thức cần thiết về phương pháp sử dụng các thuật toán về tổ hợp và kỹ thuật lập trình cơ bản những kinh nghiệm cụ thể trong qua trình tìm tòi lời giải, giúp học sinh rèn luyện các thao tác tư duy, phương pháp suy luận và khả năng sáng tạo. B.CÁC KHÁI NIỆM I. Hoán vị: 1.Khái niệm: Ví dụ: Có 3 học sinh An (A), Bình (B)và Chính (C) ngồi cùng bàn học. Nếu mỗi tuần một lần thay đổi vị trí ngồi giữa 3 người thì sau bao nhiêu tuần họ lại vế vị \ trí ban đầu? . ABC ABCBACCBA ACBBCACAB 2 Giải : Gọi Vị trí ngồi ban đầu là Ao = (A,B,C) “ B ngồi giữa ;A bên phải; C bên trái ”. Các tuần tiếp theo các thay đổi có thể là: A1 = (A, C, B) ; A2 = (B, A, C) ; A3 = (B, C, A), A4 = (C, A, B), A5 = (C, B, A). Vậy sau 5 tuần họ lại vế vị trí ban đầu . *Nhận xét : cách giải trên là cách liệt kê; muốn khẳng định kết quả, ta phải chứng minh rằng không còn cách sắp xếp nào khác. Tuy nhiên nếu với số cho lớn thì các liệt kê không ổn, dễ bỏ sót. * Cách suy luận: Mỗi người nếu ngồi đầu bàn thì chỉ có 2 cách thay đổi vị tri, vậy có 3 người thì sẽ có 2 x 3 = 6 cách thay đổi vị trị. Đầu bài trên hỏi sau mấy tuần quay về vị trí ban đầu thi kết qurả phải là 6 – 1 = 5 (tuần) *Liên hệ với lý thuyết hoán vị Nếu mỗi lần “thay đổi vị trí” là một Hoán vị của tập hợp {A; B; C}. P = {A, B, C} thì tập hợp này có tất cả 6 Hoán vị . Cho tập hợp có phần tử ( ). Mỗi thay đổi vị trí sắp xếp một thứ tự nhất định, ta được một Hoán vị các phần tử của tập phần tử này theo . 2. Số các Hoán vị: Định lí : Số các Hoán vị của một tập hợp có phần tử là: Bài toán minh họa : Một đoàn khách du lịch dự định đến tham quan điểm du lịch và ở Hà Nội. Họ đi tham quan theo thứ tự nào đó, chẳng hạn : . Như vậy mỗi cách họ chọn thứ tự tham quan là một Hoán vị của tập . Do vậy đoàn khách có tất cả cách chọn. ( Như bài này rõ ràng cách liệt kê thô sơ khõ lòng giải quyết được) 3 Một hoán vị của n phần tử là một bộ gồm n phần tử để được sắp theo một trật tự nhất định, mỗi phần tử có mặt đúng một lần II. Chỉnh hợp: a. Khái niệm về chỉnh hợp Ví dụ : Trong trận chung kết bóng đá phải phân định thắng thua bằng đá luân lưu . Huấn luyện viên của mỗi đội cần trình với trọng tài một danh sách sắp thứ tự cầu thủ trong số cầu thủ của đội để tham gia đá. Hỏi mỗi đội bóng có bao nhiêu phương án chọn ? Giải: Ta có thể chọn trong Tiếp theo có cầu thủ để đá quả đầu tiên. cách chọn cầu thủ đá quả thứ hai, rồi cách chọn cầu thủ đá quả thứ ba, cách chọn cầu thủ đá quả thứ tư và cuối cùng có cách chọn cầu thủ đá quả thứ năm. Theo quy tắc nhân, mỗi đội sẽ có: cách chọn. Mỗi danh sách có xếp thứ tự cầu thủ được gọi là một chỉnh hợp chập của cầu thủ *Tổng quát: Cho tập tử của gồm phần tử và số nguyên , . Mỗi lần lấy ra và sắp xếp chúng theo một thứ tự ta được một Chỉnh hợp chập phần tử thuộc phần của . *Nhận xét: Hai Chỉnh hợp khác nhau khi và chỉ khi hoặc có ít nhất một phần tử của Chỉnh hợp này không là phần tử của Chỉnh hợp kia hoặc các phần tử của Chỉnh hợp giống nhau nhưng được sắp xếp theo thứ tự khác nhau. 4 b. Số các Chỉnh hợp: Trong ví dụ trên, tính số phương án huấn luyện viên lập danh sách cầu thủ là : 11.10.9.8.7=55440 (cách chọn.) Định lí: Số các Chỉnh hợp chập của một tập hợp có An k  n.( n  1).( n  2).....(n  k  1)  phần tử (1 �k �n) là: n! (1) ( n  k )! với quy ước Ta quy ước: An 0  1 , do đó công thức (1) đúng với mọi số nguyên thỏa mãn : 0 �k �n Chú ý: Một Hoán vị của một tập phần tử chính là một Chỉnh hợp chập của phần tử đó . Do đó : An n  pn  n ! III. Tổ hợp: * Khái niệm:Cho tập A có n phần tử và số nguyên với của phần tử của có hợp chập phần tử gọi là một Tổ hợp chập của của . Mỗi tập con ( gọi tắt là Tổ ) Như vậy, lập một Tổ hợp chập của chính là lấy ra phần tử của mà không quan tâm đến thứ tự. * Số các Tổ hợp: Định lí: Số các Tổ hợp chập của một tập hợp có phần tử ( ) là: A nk n! Cn   (2) k ! k !(n  k )! k Với quy ước: Cn  1 thì (2) cũng sẽ đúng với mọi số nguyên 0 thỏa mãn *Bài toán mẫu: 5 Trong lớp học có học sinh nam và học sinh nữ. Mỗi tuần Thầy giáo cần học sinh nam và học sinh nữ đi tham gia 1 sinh hoạt ngoại khóa của trường. Hỏi có bao nhiêu cách? Giải: Ta có: cách chọn học sinh nam trong số học sinh nam và có cách chọn HS nữ trong số HS nữ. Theo quy tắc nhân, số cách chọn cần tìm là: 4. Hai tính chất cơ bản của 4845.455=2204475 (cách chọn) Cn k : Tính chất 1: Cho các số nguyên n,k thỏa mãn ( .) Khi đó: C n k  Cn n  k Tính chất 2: Cho các số nguyên n, k thỏa mãn Khi đó: . Cn 1k  Cn k  Cn k 1 5. Bài toán thực hành: Bài 1: Có bao nhiêu cách xếp chỗ ngồi cho 10 bạn vào ngồi quanh 2 bàn tròn sao cho bàn thứ nhất có 6 bạn, bàn thứ hai có 4 bạn? Chú ý rằng 2 cách xếp n người cụ thể vào ngồi quanh một bàn tròn được coi là như nhau nếu người ngồi bên trái mỗi người trong 2 cách xếp là giống nhau. Hướng dẫn giải 6 Chia là ba bước. Bước 1: chọn nhóm 6 người (hoặc 4 người). Có Bước 2: Xếp người vào bàn tròn vị trí. Bước 3: Xếp người vào bàn tròn có vị trí. cách. cách. cách. Áp dụng quy tắc nhân, tính kết quả. Bài 2 : Một người dùng ổ khóa số gồm 3 vòng số, mỗi vòng có 10 chữ số từ 0 đên 9. Hỏi người đó có bao nhiêu cách đặt mật mã ( số để khóa chỉ người đó biết ) cho ổ khóa ? VD2: Hoán vị của 3 phần tử : 1 2 3 Hoán vị thứ nhất : 1 2 3 Hoán vị thứ 2 : 132 Hoán vị thứ 3: 213 Hoán vị thứ 4: 231 Hoán vị thứ 5: 312 Hoán vị thứ 6: 321 -Số các hoán vị khác nhau của n phần tử là: C. ÁP CÀI ĐẶT CÁC BÀI TOÁN CƠ BẢN TRONG TIN HỌC 1. Hoán vị: Bài toán:Tìm các hoán vị của n số tự nhiên đầu tiên .  Thuật toán : - Ta đặt một mảng A[1..n] để chứa các hoán vị tìmđược - Mảng B[1..n] of boolean để làm cờ với ý nghĩa b[i] cho ta biết số i đã được chọn vào hoán vị hay chưa . Thuật toán được lập theo kiểu đệ quy với hai thủ tục :PRINT và FINT (I: BYTE). Thủ tục print in hoán vị tìm được. procedure Print; 7 var i:longint; begin inc(dem); for i:=1 to n do write(g,A[i],' ');writeln(g); end; - Thủ tục FIND(i:Byte) giúp tìm phần tử thứ i trong hoán vị và được gọi một cách đệ quy. Cơ chế của nó hoạt độn như sau Procedure FIND(i:byte); Var j: byte; Begin If i>n then print Else Begin For J:=1 to n do If b[i] then Begin A[i]:=j; B[j]:=false; Find(i+1); B[j]:= true; End; End; End; ……………………………………………………. 8 Ví dụ: n =3 F(1) 1 2 F(2) 2 3 P(1 2 3) F(2) 3 F(3) 3 1 F(3) 2 P(1 3 2) F(2) 3 1 F(3) F(3) 3 1 P(2 1 3) P(2 3 1) 2 F(3) 2 P(312 ) F(3) 1 P(3 2 1) Program HoanVi; uses crt; const n=5; var A,S:array[1..100]of integer; B:array[1..100]of boolean; i,dem:integer; g:text; procedure Print; var i:longint; begin inc(dem); 9 for i:=1 to n do write(g,A[i],' ');writeln(g); end; procedure Find(i:longint); var j:longint; begin if i>n then print else begin for j:=1 to n do if B[j] then begin A[i]:=j; B[j]:=false; find(i+1); B[ j]:=true; end; end; end; BEGIN clrscr; assign(g,'ra.out'); REWRITE(G); for i:=1 to n do B[i]:=true; Find(1); close(g); END. *Bài tập áp dụng: Bài 4: Tên file chương trình đăt. là BL4PAS 10 Một số được gọi là “ số gần nguyên tố “nếu nó không phải là só nguyên tố nhưng tồn tại một cách sắp xếp lại các chữ số của nó (bỏ đi các chữ số 0 vô nghĩa ở đầu số sau khi sắp xếp các chữ số nếu có ) sao cho số sau khi sắp xếp trở thành một số nguyên tố . Yêu cầu: Nhập từ bàn phím mọt số nguyên dương N không quá 1000000, sau đó thông báo ra màn hình “số gần nguyên tố ”lớn nhất có giá trị không vượt quá N. Nếu không tìm được “số gần nguyên tố “nào không vượt quá N thì đưa ra dòng thông báo: KHONG CO . Dữ liệu nhập vào coi như là chuẩn, không cần kiểm tra. Ví dụ : +Nhập N=19 , thì đưa ra dòng thông báo :SO CAN TIM LA 16 +Nhập N=20 , thì đưa ra dòng thông báo :SO CAN TIM LA 20 *Thuật toán : + một vòng lặp từ lớn đến nhỏ, với mỗi số nếu không phải là nt thì đổi ra xâu + Đưa xâu st vào hoán vị , + Với mỗi hoán vị, ta chuyển lại thành số + KT tính NT của hoán vị đó + Nếu thỏa mãn thì kết thúc vòng lặp tìm kiếm. Cài đặt : program gan_nguyen_to; uses crt; var A:array[1..20]of char; B:array[1..20]of boolean; i,j,n,n1,k:longint; kq,st:string; kt:boolean; f,g:text; function nt(k:longint):boolean; var i:longint; 11 begin nt:=false; for i:=2 to trunc(sqrt(k)) do if k mod i=0 then exit; nt:=k>1; end; procedure Print; var i:longint; code:integer; begin kq:=''; for i:=1 to n do kq:=a[i]+kq;val(kq,k,code); if nt(k) then begin writeln(g,st);kt:=true; end; end; procedure Find(i:longint); var j,k:longint;code:integer; begin if i>n then print else begin for j:=1 to n do if B[j] then begin A[i]:=st[j]; B[j]:=false; find(i+1); B[ j]:=true; if kt then exit; 12 end; end; end; BEGIN assign(f,'gnt.inp');reset(f); assign(g,'gnt.out'); REWRITE(G); readln(f,n1); i:=n1; kt:=false; repeat if not(nt(i)) then begin str(i,st);n:=length(st) ; for j:=1 to n do B[j]:=true; Find(1); end; dec(i); until kt; close(f); close(g); END. *Hãy lập trình giải các bài toán sau đây: Bài 1: Xếp lại dãy số Cho dãy số nguyên dương đôi một khác nhau: a 1, a2, ..., an. Một hoán vị của dãy số là một cách sắp xếp khác các số hạng của dãy. Hãy liệt kê tất cả các hoán vị của dãy đã cho thoả mãn: giữa hai phần tử bất kỳ M và N trong hoán vị đó, không tồn tại phần tử P nào của hoán vị để:2P = M + N. 13 Ví dụ: Với dãy: 11, 22, 33, 44 thì Hoán vị 33 11 22 44 là thoả mãn điều kiện trên Hoán vị 11, 44, 22, 33 không thoả mãn vì có phần tử P = 22 nằm giữa hai phần tử M = 11 và N = 33 mà: 22 * 2 = 11 + 33. Dữ liệu vào: Đọc từ file văn bản SORT.INP. Các số trên 1 dòng cách nhau ít nhất 1 dấu trống  Dòng 1: Chứa số n (2  n  11)  Dòng 2: Chứa các số a1, a2, ..., an của dãy (1  ai  100). Dữ liệu ra: Ghi ra file văn bản SORT.OUT. Các số trên 1 dòng cách nhau ít nhất 1 dấu trống  K dòng đầu, mỗi dòng ghi 1 hoán vị tìm được.  Dòng cuối cùng ghi số lượng hoán vị tìm được (K) Ví dụ: SORT.INP 4 SORT.OUT 11 33 22 44 11 22 33 11 33 44 22 44 22 11 44 33 22 44 11 33 22 44 33 11 33 11 22 44 33 11 44 22 33 44 11 22 44 22 11 33 44 22 33 11 10 Bài 2: Vòng tròn nguyên tố Một vòng tròn chứa 2n vòng tròn nhỏ (Xem hình vẽ). Các vòng tròn nhỏ được đánh số từ 1 đến 2n theo chiều kim đồng hồ. Cần điền một số tự nhiên từ 1 14 đến 2n vào mỗi vòng tròn nhỏ (mỗi số chỉ được phép điền một lần) sao cho tổng của hai số trên hai vòng tròn nhỏ liên tiếp là số nguyên tố. Số điền ở vòng tròn nhỏ 1 luôn là số 1. 1 6 4 5 3 2 Dữ liệu vào: Đọc từ file văn bản CIRCLE.INP gồm chỉ một dòng chứa số nguyên dương n (1 < n < 10). Dữ liệu ra: Ghi ra file văn bản CIRCLE.OUT có cấu trúc như sau:  k dòng đầu, mỗi dòng ghi các số trong các vòng tròn nhỏ bắt đầu từ vòng tròn nhỏ 1 đọc theo thứ tự của các vòng tròn nhỏ, mỗi số cách nhau một dấu cách.  Dòng cuối cùng ghi số lượng các cách điền số tìm được (k). Ví dụ: CIRCLE.INP 3 CIRCLE.OUT 1 4 3 2 5 6 CIRCLE.INP 4 CIRCLE.OUT 1 2 3 8 5 6 7 4 1 6 5 2 3 4 1 2 5 8 3 4 7 6 2 1 4 7 6 5 8 3 2 1 6 7 4 3 8 5 2 4 15 Bài 1: Xếp lại dãy số Cho dãy số nguyên dương đôi một khác nhau: a1, a2, ..., an. Một hoán vị của dãy số là một cách sắp xếp khác các số hạng của dãy. Hãy liệt kê tất cả các hoán vị của dãy đã cho thoả mãn: giữa hai phần tử bất kỳ M và N trong hoán vị đó, không tồn tại phần tử P nào của hoán vị để:2P = M + N. *Thuật toán : + một vòng lặp từ lớn đến nhỏ, với mỗi số nếu không phải là nguyên tố thì đổi ra xâu. + Đưa dãy A vào hoán vị , + Kiểm tra hoán vị nào thỏa mãn điều kiện bài toán + Nếu thỏa mãn thì in ra hoán vị đó và kết thúc vòng lặp tìm kiếm. Cài đặt : uses crt; var A,c:array[1..20]of longint; B:array[1..20]of boolean; i,j,n,n1,k,d:longint; kt:boolean; f,g:text; procedure Print; var i,h,k:longint; begin i:=2; kt:=true; repeat for k:=1 to i-1 do 16 for h:=i+1 to n do if 2*a[i]=a[k]+a[h] then Kt :=false; inc(i); until not(kt)or(i=n); if kt then begin inc(d); for i:=1 to n do write(g,a[i],' '); writeln(g); end; end; procedure Find(i:longint); var j,k:longint; begin if i>n then print else begin for j:=1 to n do if B[j] then begin A[i]:=c[j]; B[j]:=false; find(i+1); B[ j]:=true; end; end; end; BEGIN 17 assign(f,'sort.inp');reset(f); assign(g,'sort.out'); REWRITE(G); readln(f,n); for i:=1 to n do read(f,c[i]); for i:=1 to n do B[i]:=true; Find(1); write(g,d); close(f); close(g); END. Bài 2: Vòng tròn nguyên tố. Một vòng tròn chứa 2n vòng tròn nhỏ (Xem hình vẽ). Các vòng tròn nhỏ được đánh số từ 1 đến 2n theo chiều kim đồng hồ. Cần điền một số tự nhiên từ 1 đến 2n vào mỗi vòng tròn nhỏ (mỗi số chỉ được phép điền một lần) sao cho tổng của hai số trên hai vòng tròn nhỏ liên tiếp là số nguyên tố. Số điền ở vòng tròn nhỏ 1 luôn là số *Thuật toán : - Xét mọi trường hợp của các hoán vị. Cài đặt : uses crt; var A:array[1..20]of longint; B:array[1..20]of boolean; i,j,n,n1,k,d:longint; f,g:text; function nt(n:longint):boolean; var i:longint; 18 begin nt:=false; for i:=2 to trunc(sqrt(n)) do if n mod i=0 then exit; nt:=n>1; end; procedure Print; var i,h,k:longint; kt:boolean; begin IF a[1]=1 then begin inc(n);a[n]:=a[1]; kt:=true; for i:=1 to n-1 do if not(nt(a[i]+a[i+1])) then Kt :=false; if kt then begin inc(d); for i:=1 to n-1 do write(g,a[i],' '); writeln(g); end; dec(n); end; end; procedure Find(i:longint); var j,k:longint; begin if i>n then print else begin 19 for j:=1 to n do if B[j] then begin A[i]:=j; B[j]:=false; find(i+1); B[j]:=true; end; end; end; BEGIN assign(f,'CIRCLE.inp');reset(f); assign(g,'CIRCLE.out'); REWRITE(G); readln(f,n); N:=N*2; for i:=1 to n do B[i]:=true; Find(1); write(g,d); close(f); close(g); END. 2. Chỉnh hợp: Bài toán:Tìm các chỉnh hợp n chập r của số tự nhiên đầu tiên (r<=n) . *Thuật toán : - Tương tự như phần hoán vị - chỉ cần sửa lại thủ tục FIND như sau 20
- Xem thêm -

Tài liệu liên quan