Tổ hợp trong Pascal 2020-08-08T20:47:21+07:002020-08-08T20:47:21+07:00https://sachgiai.com/Tin-hoc/to-hop-trong-pascal-13460.htmlhttps://sachgiai.com/uploads/news/2020_07/lap-trinh-pascal.jpgSách Giảihttps://sachgiai.com/uploads/sach-giai-com-logo.pngThứ bảy - 08/08/2020 20:28 Trong khi lập trình 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, hợp thành tập hợp lớn hơn... 1. KHÁI NIỆMa) Trong khi lập trình 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, hợp 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 các khái niệm của giải tích tổ hợp, đó là:+ Hoán vị+ Chỉnh hợp+ Tổ hợpb) Hoán vị- Một hoán vị của n phần tử là một bộ phận gồm n phần tử để được sắp xếp theo một trật tự nhất định, mỗi phần tử có mặt đúng một lần.- Số các hoán vị khác nhau của n phần tử là:Pn = n! = 1 x 2 x 3 x ... x nc) Chỉnh hợp- Một chỉnh hợp n chập r của n phần tử là một bộ sắp thứ tự gồm r phần tử lấy ra từ n phần tử đã cho.- Số chỉnh hợp n chập r là: = n(n - l)...(n - r + 1) = d) Tổ hợp- Cho một tập x có n phần tử. Một tổ hợp n chập r của n phần tử đó là một tập con của X gồm có r phần tử. - Số tổ hợp n chập r là: = = 2. CÁC THUẬT TOÁNa) Hoán vị* Bài toán:Viết chương trình in ra tất cả các hoán vị của N số tự nhiên đầu tiên.* Thuật toán:- Ta đặt mảng A[1..N] để chứa hoán vị tìm được.- Mảng B[1..N] of Bollean để làm cờ với B[I] cho 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 đệ qui với hai thủ tục là: PRINT và FIND (i: Byte).- Thủ tục PRINT sẽ in ra hoán vị vừa tìm được.- 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 đệ qui. Cơ chế hoạt động của nó như sau:procedure FIND (i: Byte);Var j: byte;Begin if i > N then Xuat Else Begin For j := 1 to N do if b[j] then Begin a[i] := j b[j] := 0 Find (i + 1) b[j] := 1; end; end;end;* Ví dụ: N = 3* Thể hiện bằng PASCAL:PROGRAM HOANVI;Const N = 3;Var A: Array [1..N] of byte; B: Array [1..N] of 0..1; i, dem: integer;Procedure xuat; var i: integer; Begin dem := dem + 1; write (’Hoan vi thu', dem, ’ '); For i:= 1 to N do write (A[i]); Writein ; readln ; end;Procedure Find (i: byte); var j: byte; Begin if i > N then Xuat else Begin For j := 1 to N do if (B[j] = 1) then Begin a[i] := j; b[j] := 0; find (i + 1); b[j] := 1; end; end; end;BEGIN dem := 0; For i: 1 to N do B[i]:= 1; Find(l);END.b) Chỉnh hợp* Bài toán:Viết chương trình in ra tất cả 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 thủ tục Find(i) lại như sau:Procedure Find (i: byte); var j: byte Begin if i > r then xuat else...* Ví dụ:N = 3, r = 2* Thể hiện bằng PASCAL: PROGRAM CHINHHOP; Var A: Array [1..N] of byte; B: Array [1..N] of 0..1; i, j, dem: byte;Procedure Xuat; Var i: byte; Begin dem := dem + 1; write (’Hoan vi thu dem, ':; For i: = 1 to r do write (A[i]); writein; Readln; end; Procedure Find (i: byte); Var j: byte; Begin if i > r -then Xuat else For j:= 1 to n do if (B[j] = 1) then Begin A[i] := j; B[j] := 0; Find (i + 1); B[j] := 1; end; end;BEGIN writeiln (‘Nhập r'); Readln(r); Dem:= 0; For i : 1 to b do B[i] := 1; Find(l);END.c) Tổ hợp* Bài toán:Viết chương trình in ra màn hình tất cả các tổ hợp n chập r của các số nguyên từ 1 đến n.* Thuật toán:• THUẬT TOÁN 1:- Tương tự như thuật toán tìm các chỉnh hợp n chập r nhưng ở đây ta chỉ cần chọn 1 chỉnh hợp có thứ tự tăng.- Thủ tục Find được cải tiến như sau:Procedure Find (k: byte);Var j: byte;Begin if k > r then xuat else Begin For j := 1 to n do if b[j] and (j > a[k – 1]) then begin a[k] := j; . b[j]:= False; Find [k + 1]; b[i] := True; end; end; End;• THUẬT TOÁN 2.- Do trong tổ hợp ta chỉ cần tìm từ nhỏ đến lớn và không cần quay lại nên ta có thể không cần tìm i đặt cờ B[1..N] of Boolean.- Thủ tục Find (i: byte) có thể viết như sau:Procedure Find (i: byte)Var i: byte;Begin If k > r then xuat Else For i:= (A[k - 1] + 1) to n do Begin B[K] := i Find (k + 1); end; end;• THUẬT TOÁN:- Chỉ cần đặt các cờ A[1..N] of 0..1- Lần lượt cho các A[i] bằng 1 hoặc 0 A[i]:= 1: số i được chọn vào tổ hợp. A[i]:= 0: số i không được chọn vào tổ hợp.■ Ví dụ: N = 3, r = 2Giải thuật của ta chạy hết cây chọn lựa sau đây để tìm ra tất cả các tổ hợp 3 chập 2 của tập X = (1, 2, 3);Thủ tục Find được viết lại như sau:procedure Find (i: byte);Var j: byte;Begin if d > r then print Else if ((n + 1 - i) > (r - d)) then Begin For j := 1 down to 0 do A[i] := j; d := d + j; Find (i + 1); d :=d - j; A[i] := A[i] - j; end;end;* Thể hiện bằng PASCAL:PROGRAM TOHOP1;Const n = 10Var A: array [0..N] of byte; B: array [1..N] of Boolean; r, dem, t: integer;procedure print;var i: byte;Begin Dem:= dem + 1; Write ('to hop thu', dem, 'la :'); For i := 1 to r do write (a[i]); writeln; readln;end;{……………………………….}Procedure Find (k: byte);Var j: byte;Begin if k > r then print else Begin For j:= 1 to n do if b[j] and (j > a[k - 1]) then Begin a[k] := j; b[j] := False.; Find [k + 1]; b[j] := True; end; end;end;BEGIN write ('Cho biet so phan tu:’); Readin (r); dem := 0; For t: = 1 to n do b[t]:= true a[0] := 0; Find(l);END.{………………………….}PROGRAM TOHOP2;const N = 10;Var A: array [0..N] of byte; dem, r: byte; {……………………..}procedure print; Var i: byte; Begin Dem := dem + 1; For i: = 1 to r do write (A[i]); Writein; Readin; end;{………………………….}Procedure Find (j = byte); Var i: byte; Begin if j > r then print else For i:= A[j - 1] to n do Begin B[j] := i ; Find(j + 1); end; End;BEGIN Dem := 0; a[0] := 0; Readln(r); Find(1);END.{………………………….}PROGRAM TOHOP3;Var A: array [0..n] of 0..1; r, d : byte;procedure Print;Var i: byte; Begin d := d + 1; write ('To hop thu', d, '{'); For i := 1 to n do if A[i] := 1 then write (i); Write(‘{'); Writeln; Readln;end;{………………………….}Procedure Find (i = byte);Var j: byte;Begin if d > r then print Else if (n + 1 - i) > (r - d) then For j := down to 0 do Begin A[i] := j; d := d + j Find(i + 1) d := d - j; end;End;BEGIN d := 0; writeln ('Nhap r'); Readln(r); Fill char (A, size of (A); 0); Find(l);END. Bản quyền bài viết thuộc về Sachgiai.com. Ghi nguồn Sách giải.com khi đăng lại bài viết này. Tags: Tổ hợp trong Pascal
Ý kiến bạn đọc
Sắp xếp theo bình luận mới Sắp xếp theo bình luận cũ Sắp xếp theo số lượt thích
Những tin mới hơn
Đồ thị trong Pascal
Cách thiết kế một chương trình trò chơi trong pascal
Những tin cũ hơn
Đệ qui trong Pascal
Sắp xếp trong Pascal (tiếp theo)
Lớp 1
Kết nối tri thức
Tiếng Việt 1
Toán 1
Giáo dục thể chất 1
Mỹ thuật 1
Chân trời sáng tạo
Tiếng Việt 1
Toán 1
Cánh diều
Âm nhạc 1
Giáo dục thể chất 1
Hoạt động trải nghiệm 1
Toán 1
Tự nhiên và xã hội 1
Lớp 2
Kết nối tri thức
Toán 2
Tiếng Việt 2
Chân trời sáng tạo
Tiếng Việt 2
Toán 2
Cánh diều
Toán 2
Tiếng Việt 2
Lớp 3
Kết nối tri thức
Tiếng Việt 3
Toán 3
Cánh diều
Tiếng Việt 3
Toán 3
Chân trời sáng tạo
Tiếng Việt 3
Toán 3
Lớp 4
Kết nối tri thức
Tiếng Việt 4
Toán 4
Chân trời sáng tạo
Tiếng Việt 4
Toán 4
Cánh diều
Tiếng Việt 4
Toán 4
Lớp 5
Kết nối tri thức
Tiếng Việt 5
Toán 5
Cánh diều
Tiếng Việt 5
Toán 5
Chân trời sáng tạo
Tiếng Việt 5
Toán 5
Lớp 6
Kết nối tri thức
Ngữ Văn 6
Toán 6
Tiếng Anh 6 Global Success
Lịch sử và Địa lí 6
Giáo dục công dân 6
Tin học 6
Cánh diều
Giáo dục công dân 6
Ngữ Văn 6
Toán 6
Chân trời sáng tạo
Ngữ Văn 6
Toán 6
Giáo dục công dân 6
Lớp 7
Kết nối tri thức
Ngữ Văn 7
Toán 7
Tiếng Anh 7 Global Success
Giáo dục công dân 7
Lịch sử và Địa lí 7
Khoa học tự nhiên 7
Tin học 7
Công nghệ 7
Cánh Diều
Ngữ Văn 7
Toán 7
Khoa học tự nhiên 7
Chân trời sáng tạo
Ngữ Văn 7
Toán 7
Mĩ thuật 7
Âm nhạc 7
Lớp 8
Kết nối tri thức
Ngữ Văn 8
Toán 8
Khoa học tự nhiên 8
Giáo dục công dân 8
Tin học 8
Lịch sử và Địa lí 8
Công nghệ 8
Tiếng Anh 8 Global Success
Cánh Diều
Ngữ Văn 8
Toán 8
Công Dân 8
Chân trời sáng tạo
Ngữ Văn 8
Toán 8
Lớp 9
Kết nối tri thức
Ngữ Văn 9
Toán 9
Khoa học tự nhiên 9
Giáo dục công dân 9
Tin học 9
Lịch sử và Địa lí 9
Tiếng Anh 9 Global Success
Công nghệ 9
Cánh Diều
Ngữ Văn 9
Toán 9
Chân trời sáng tạo
Ngữ Văn 9
Toán 9
Lớp 10
Kết nối tri thức
Ngữ Văn 10
Toán 10
Kinh tế và Pháp luật 10
Tiếng Anh 10 Global Success
Lịch Sử 10
Địa Lí 10
Vật Lí 10
Hoá học 10
Sinh học 10
Công nghệ trồng trọt 10
Công nghệ thiết kế 10
Quốc Phòng và An Ninh 10
Tin học 10
Cánh Diều
Ngữ Văn 10
Toán 10
Kinh tế và Pháp luật 10
Tin học 10
Hoá học 10
Lịch sử 10
Địa Lí 10
Sinh học 10
Vật lí 10
Tiếng Anh 10 Explore New Worlds
Công nghệ trồng trọt 10
Công nghệ thiết kế 10
Chân trời sáng tạo
Ngữ Văn 10
Toán 10
Lịch Sử 10
Địa Lí 10
Sinh học 10
Vật Lí 10
Hoá học 10
Quốc Phòng và An Ninh 10
Kinh tế và Pháp luật 10
Tiếng Anh 10 Friends plus
Lớp 11
Kết nối tri thức
Ngữ Văn 11
Toán 11
Hoá học 11
Sinh học 11
Địa Lí 11
Lịch Sử 11
Vật Lí 11
Kinh tế và Pháp luật 11
Công nghệ 11 Chăn nuôi
Công nghệ 11 Cơ khí
Tin học 11 Ứng dụng
Tin học 11 Khoa học máy tính
Tiếng Anh 11 Global Success
Cánh Diều
Ngữ Văn 11
Toán 11
Hoá học 11
Lịch Sử 11
Địa Lí 11
Sinh học 11
Vật Lí 11
Tin học 11 Ứng dụng
Tin học 11 Khoa học máy tính
Tiếng Anh 11 Explore New Worlds
Quốc phòng và An ninh 11
Kinh tế và Pháp luật 11
Công nghệ 11 Chăn nuôi
Công nghệ 11 Cơ khí
Chân trời sáng tạo
Ngữ Văn 11
Toán 11
Địa Lí 11
Hoá học 11
Sinh học 11
Lịch Sử 11
Kinh tế và Pháp luật 11
Tiếng Anh 11 Friends plus
Vật Lí 11
Lớp 12
Kết nối tri thức
Ngữ Văn 12
Toán 12
Địa Lí 12
Hoá học 12
Lịch Sử 12
Sinh học 12
Vật Lí 12
Tiếng Anh 12 Global Success
Tin học 12 Ứng dụng
Tin học 12 Khoa học máy tính
Kinh tế và Pháp luật 12
Công nghệ 12 Chăn nuôi
Công nghệ 12 Cơ khí
Cánh Diều
Ngữ Văn 12
Toán 12
Chân trời sáng tạo
Ngữ Văn 12
Toán 12
THÀNH VIÊN
Hãy đăng nhập thành viên để trải nghiệm đầy đủ các tiện ích trên site Nhập mã do ứng dụng xác thực cung cấp Thử cách khác Nhập một trong các mã dự phòng bạn đã nhận được. Thử cách khác Đăng nhập Đăng ký