Bài gộp - gia sư tin học
Bộ bài bao gồm n quân, được gán mã số từ 1 đến n.
Lúc đầu bộ bài được chia cho n người, mỗi người nhận 1 quân. Mỗi lượt chơi,
trọng tài chọn ngẫu nhiên hai số x và y trong khoảng 1..n. Nếu có hai người
khác nhau, một người có trong tay quân bài x và người kia có quân bài y thì một
trong hai người đó phải trao toàn bộ số bài của mình cho người kia theo nguyên
tắc sau: mỗi người trong số hai người đó trình ra một quân bài tuỳ chọn của
mình, Ai có quân bài mang mã số nhỏ hơn sẽ được nhận bài của người kia. Trò
chơi kết thúc khi có một người cầm trong tay cả bộ bài. Biết số quân bài n và
các quân bài trọng tài chọn ngẫu nhiên sau m lượt chơi, hãy cho biết số lượng người còn có bài trên tay.
Dữ
liệu vào: Tệp văn bản BAIGOP.INP.
-
Dòng đầu tiên: hai số n và m, trong đó n là số lượng quân bài trong bộ bài, m
là số lần trọng tài chọn ngẫu nhiên hai số x và y. Các quân bài được gán mã số
từ 1 đến n. Mã số này được ghi trên quân bài.
-
Tiếp đến là m dòng, mỗi dòng ghi hai số tự nhiên x và y do trọng tài cung cấp. Các số trên cùng một dòng cách nhau qua dấu cách.
Dữ
liệu ra: Hiển thị trên màn hình số lượng người còn có bài trên tay.
Thí dụ:
|
Dữ liệu vào:
BAIGOP.INP
|
Kết quả hiển thị trên màn hình
|
ý
nghĩa: bộ bài có
10 quân mã số lần lượt 1, 2,…, 10 và có 10 người chơi. Sáu lần trọng tài chọn
ngẫu nhiên các cặp số (x, y) là (2, 5),
(3, 3), (4, 7), (1, 5), (2, 8) và (9, 3). Cuối ván chơi còn lại 5 người có bài trên tay: {1, 2, 5, 8}, {3, 9}, {4, 7}, {6}, {10}. |
|
10 6
2
5
3
3
4
7
1
5
2
8
9
3
|
5
|
Thuật toán
Đây là bài toán có nhiều ứng dụng hữu hiệu nên bạn đọc
cần tìm hiểu kĩ và cố gắng cài đặt cho nhuần nhuyễn. Như sau này sẽ thấy, nhiều
thuật toán xử lí đồ thị như tìm cây khung, xác định thành phần liên thông, xác
định chu trình… sẽ phải vận dụng cách tổ chức dữ liệu tương tự như thuật toán
sẽ trình bày dưới đây.
Bài này đòi hỏi tổ chức các tập quân bài sao cho thực
hiện nhanh nhất các thao tác sau đây:
Find(x): cho biết tên của tập chứa phần tử x.
Union(x, y): hợp tập chứa x với tập chứa y.
Mỗi tập là nhóm các quân bài có trong tay một người chơi. Như vậy mỗi
tập là một tập con của bộ bài {1, 2,…, n}. Ta gọi bộ bài là tập chủ hay tập nền. Do tính chất của trò chơi, ta có hai nhận xét quan trọng
sau đây:
1. Hợp của tất cả các tập con (mỗi tập con này do một
người đang chơi quản lí) đúng bằng tập chủ.
2. Hai tập con khác nhau không giao nhau: tại mỗi thời
điểm của cuộc chơi, mỗi quân bài nằm trong tay đúng một người.
Họ các tập con thỏa hai tính chất nói trên được gọi là một phân hoạch của tập chủ.
Các thao tác nói trên phục vụ trực tiếp cho việc tổ chức trò chơi theo
sơ đồ sau:
Khởi trị:
for i:= 1 to n do
begin
Trọng tài sinh
ngẫu nhiên hai số x và y
trong khoảng 1..n:
Hợp tập chứa x với tập chứa
y: Union(x,y);
end;
Để thực hiện thủ tục Union(x,y) trước hết ta cần biết quân bài x và quân bài y đang ở
trong tay ai? Sau đó ta cần biết người giữ quân bài x (hoặc y) có quân bài
nhỏ nhất là gì? Quân bài nhỏ nhất được xác định trong toàn bộ các quân bài mà
người đó có trong tay. Đây chính là điểm dễ nhầm lẫn. Thí dụ, người chơi A đang
giữ trong tay các quân bài 3, 4 và 7, A = {3, 4, 7}; người chơi B đang
giữ các quân bài 2, 5, 9 và 11, B = {2, 5, 9, 11}. Các số gạch chân là
số hiệu của quân bài nhỏ nhất trong tay mỗi người. Nếu x
= 9 và y = 7 thì A (đang giữ quân y = 7) và B (đang
giữ quân x = 9) sẽ phải đấu với nhau.
Vì trong tay A có quân nhỏ nhất là 3 và trong tay B có quân nhỏ nhất là 2 nên A
sẽ phải nộp bài cho B và ra khỏi cuộc chơi. Ta có, B = {2, 3, 4, 5, 7, 9, 11}.
Ta kết hợp việc xác định quân bài x
trong tay ai và người đó có quân bài nhỏ nhất là bao nhiêu làm một để xây dựng
hàm Find(x). Cụ thể là
hàm Find(x) sẽ
cho ta quân bài nhỏ nhất có trong tay người giữ quân bài x. Trong thí dụ
trên ta có:
Find(x) =
Find(9) = 2 và Find(y) = Find(7) = 3
Lưu ý rằng hàm Find(x) không chỉ rõ ai là người đang giữ quân bài x mà cho biết quân bài có số hiệu nhỏ nhất có trong tay người đang giữ
quân bài x, nghĩa là Find(9)=2 chứ không
phải Find(9) = B. Để giải
quyết sự khác biệt này ta hãy chọn phần tử có số hiệu nhỏ nhất trong tập các
quân bài có trong tay một người làm phần
tử đại diện của tập đó. Ta cũng đồng nhất phần tử đại diện với mã số của người giữ tập quân bài. Theo
quy định này thì biểu thức Find(9)=2 có thể được hiểu theo một trong hai nghĩa tương đương
như sau:
s
Người số 2 đang
giữ quân bài 9.
s
Tập số 2 chứa
phần tử 9.
Tổ chức hàm Find như trên có lợi là sau khi gọi i:=Find(x) và j:=Find(y) ta xác định ngay được ai phải
nộp bài cho ai. Nếu i < j thì j phải nộp bài cho i,
ngược lại, nếu i > j thì i phải nộp bài cho j. Trường hợp i = j cho biết hai quân bài x và y đang có trong tay một người, ta
không phải làm gì.
Tóm lại ta đặt ra các nguyên tắc
sau:
a) Lấy phần
tử nhỏ nhất trong mỗi tập làm tên riêng cho tập đó.
b) Phần tử có giá trị nhỏ quản lí các phần tử có giá trị lớn hơn nó theo
phương thức: mỗi phần tử trong một tập đều trỏ trực tiếp đến một phần tử nhỏ
hơn nó và có trong tập đó. Phần tử nhỏ nhất trong tập trỏ tới chính nó.
Trong thí dụ trên ta có A = {3,
4, 7}, B = {2, 5, 9, 11}, x = 9 và y = 7.
Như vậy, tập
A có phần tử đại diện là 3 và tập B có phần tử đại diện là 2.
Dữ liệu của tập A khi đó sẽ được
tổ chức như sau:
A = {3 ® 3, 4 ® 3, 7 ® 3}. Như vậy 3 là phần tử đại diện của tập này, do đó ta không cần dùng
biến A để biểu thị nó nữa mà có thể viết:
{3 ® 3, 4 ® 3, 7 ® 3} hoặc gọn hơn {3, 4, 7} ® 3.
Tương tự, dữ liệu của tập B sẽ có
dạng:
{2 ® 2, 5 ® 2, 9 ® 2, 11 ® 2} hoặc
gọn hơn {2, 5, 9, 11} ® 2.
Khi đó Find(9) = 2 và Find(7) = 3, và do
đó, tập 3 phải được gộp vào tập 2. Phép Union(9,7) sẽ tạo ra tập sau đây:
{3 ® 2, 4 ® 3, 7 ® 3, 2 ® 2, 5 ® 2, 9 ® 2, 11 ® 2},
tức là ta thực hiện đúng một thao tác sửa 3 ® 3 thành 3 ® 2: để hợp hai tập ta chỉ việc đối sánh hai phần tử đại diện i và j
của chúng:
s
Nếu i > j
thì cho tập i phụ thuộc vào tập j.
s
Nếu j > i
thì cho tập j phụ thuộc vào tập i.
s
Nếu i = j thì
không làm gì.
Kĩ thuật nói trên được gọi là hợp
các tập con rời nhau.
Ta dùng một mảng nguyên a thể hiện tất cả các tập. Khi đó hai
tập A và B nói trên được thể hiện trong a
như sau:
a[3] = 3; a[4] = 3; a[7]
= 3;
{tập A: phần tử đại diện là 3,
các phần tử 3, 4 và 7 đều trỏ đến 3}
a[2] = 2; a[5] = 2; a[9]
= 2; a[11] = 2;
{tập B: phần tử đại diện là 2,
các phần tử 2, 5, 9 và 11 đều trỏ đến 2}
|
(1)
|
(2)
|
(3)
|
(4)
|
(5)
|
(6)
|
(7)
|
(8)
|
(9)
|
(10)
|
(11)
|
(12)
|
(13)
|
(14)
|
(15)
|
|
|
2
(B)
|
3
(A)
|
3
(A)
|
2
(B)
|
|
3
(A)
|
|
2
(B)
|
|
2
(B)
|
|
|
|
|
Sau khi hợp nhất A với B ta được:
a[3] = 2; {chỗ sửa duy
nhất}
a[4]
= 3; a[7] = 3; a[2] = 2; a[5] = 2; a[9] = 2; a[11] = 2;
|
(1)
|
(2)
|
(3)
|
(4)
|
(5)
|
(6)
|
(7)
|
(8)
|
(9)
|
(10)
|
(11)
|
(12)
|
(13)
|
(14)
|
(15)
|
|
|
2
|
2
|
3
|
2
|
|
3
|
|
2
|
|
2
|
|
|
|
|
Theo các nguyên tắc trên ta suy ra phần tử x là phần tử đại diện của tập khi và chỉ khi a[x] = x. Dựa vào đây ta tổ chức hàm Find(x): xác định phần tử đại
diện của tập chứa x.
function Find(x: integer):
integer;
begin
while (x <> a[x]) do x
:= a[x];
Find := x;
end;
Khi đó thủ tục Union được triển khai đơn giản như sau:
procedure Union(x,
y: integer);
begin
x := Find(x);
y := Find(y);
if x = y then exit else
if x < y then a[y] := x
else {x > y} a[x] := y;
end;
Lúc bắt đầu chơi, mỗi người giữ một quân bài, ta
khởi trị a[i]:=i cho mọi i = 1..n với ý nghĩa: tập có
đúng một phần tử thì nó là đại diện của chính nó.
Để đếm số tập còn lại sau mỗi bước chơi ta có thể
thực hiện theo hai cách.
Ta thấy, nếu Find(x)=Find(y) thì không xảy ra việc gộp bài vì x và y cùng nằm trong một
tập. Ngược lại, nếu Find(x)<>Find(y) thì do gộp bài nên số người chơi sẽ giảm đi 1 tức là
số lượng tập giảm theo. Ta dùng một biến c đếm số lượng tập. Lúc đầu khởi trị c:=n (có n người
chơi). Mỗi khi xảy ra điều kiện Find(x) <> Find(y) ta giảm c 1 đơn vị: dec(c).
Theo cách thứ hai ta viết hàm Dem để đếm số lượng tập sau khi kết thúc một lượt chơi. Ta
có đặc tả sau đây:
số lượng tập = số lượng đại diện của tập.
Phần tử i là đại diện của một tập khi và chỉ khi a[i] = i.
Đặc tả trên cho ta:
function Dem: integer;
var d,i: integer;
begin
d := 0;
for i := 1 to n do
if a[i] = i then inc(d);
Dem := d;
end;
Dĩ nhiên trong bài này phương pháp thứ nhất sẽ hiệu quả hơn, tuy nhiên
ta thực hiện cả hai phương pháp vì hàm Dem là một tiện ích trong loại hình tổ chức dữ liệu theo
tiếp cận Find-Union.
Ta cũng sẽ cài đặt Union(x,y) dưới dạng hàm với giá trị ra là 1 nếu trước thời điểm
hợp nhất x và y thuộc về hai tập
phân biệt và là 0 nếu trước đó x và y đã thực sự có trong cùng một tập. Nói cách khác Union(x,y) cho biết
phép hợp nhất có thực sự xảy ra (1) hay không (0).
Trong chương trình dưới đây tệp BAIGOP.INP chứa dữ liệu vào có cấu trúc như sau:
-
Dòng đầu tiên
chứa hai số nguyên dương n và m, trong đó n là số lượng quân bài, m
là số lần trọng tài phát sinh ra hai số ngẫu nhiên.
-
Tiếp đến là m dòng, mỗi dòng chứa hai số do trọng
tài phát sinh. Các số được viết cách nhau bởi dấu cách.
Kĩ thuật trên có tên gọi là Find-Union
đóng vai trò quan trọng trong các thủ tục xử lí hợp các tập rời nhau. Trước khi
xem chương trình chúng ta hãy thử làm một bài tập nhỏ sau đây:
Với mảng a được tổ chức theo kĩ thuật Find-Union dưới đây hãy cho biết có mấy tập con và hãy liệt kê từng
tập một.
|
(1)
|
(2)
|
(3)
|
(4)
|
(5)
|
(6)
|
(7)
|
(8)
|
(9)
|
(10)
|
(11)
|
(12)
|
(13)
|
(14)
|
(15)
|
|
1
|
2
|
2
|
3
|
2
|
6
|
3
|
1
|
2
|
6
|
2
|
10
|
3
|
8
|
12
|
Đáp số: ba tập.
Tập với đại diện 1: {1, 8, 14}.
Tập với đại diện 2: {2, 3, 4, 5, 7, 9, 11, 13}.
Tập với đại diện 6: {6, 10, 12, 15}.
(* Pascal
*)
(*-----------------------------------
BAI GOP
------------------------------------*)
program
BaiGop;
uses crt;
const
MN = 5000;
fn = 'BAIGOP.INP';
var
a: array[1..MN] of
integer;
c,n,m: integer;
{c: dem so tap
n: so quan bai = so nguoi
choi
m: so lan trong tai sinh
2 so}
f: text;
{----------------------------------
Xac dinh tap chua phan tu x
-----------------------------------}
function
Find(x: integer): integer;
begin
while (x
<> a[x]) do x:= a[x];
Find := x;
end;
{-------------------------------------
Hop cua
tap chua x voi tap chua y.
Union =
1: co hop nhat
Union = 0: khong hop nhat vi x va y
thuoc cung 1 tap
--------------------------------------}
function Union(x,y: integer):
integer;
begin
Union := 0;
x := Find(x);
y := Find(y);
if x = y then
exit
else if x <
y then a[y] := x
else a[x] := y;
Union := 1;
end;
{-----------------------------------------------
Dem so luong tap con roi nhau (so nguoi choi)
-----------------------------------------------}
function Dem:
integer;
var d,i:
integer;
begin
d := 0;
for i := 1 to
n do
if a[i] = i then inc(d);
Dem:= d;
end;
procedure
BaiGop;
var i,j,k,x,y: integer;
begin
assign(f,fn); reset(f);
readln(f,n,m);
{n – so quan
bai; m – so lan chon x,y}
c := n; {c: so
nguoi choi}
if (n < 1)
or (n > MN) then exit;
for i := 1 to
n do a[i] := i;
for i := 1 to
m do
begin
readln(f,x,y);
c := c-Union(x,y);
end;
writeln(c);
close(f);
end;
BEGIN
BaiGop;
END.
Không có nhận xét nào:
Đăng nhận xét