Giáo sư sẽ cung cấp cho chúng ta 1 ma trận A kích thước NxN trong file PROBLEM.TXT với

+ A[i,j]=1 khi sinh viên i thích vấn đề j.

+ A[i,j]=0 khi sinh viên i không thích vấn đề j.

Yêu cầu:Bạn hãy viết 1 chương trình tính số ghép thoả mãn yêu cầu của giáo sư và gửi file kết quả SOLVE.TXT cho giáo sư.

Ví dụ:

PROBLEM.TXT

3
1 1 1
1 1 1
1 1 0

SOLVE.TXT

4

Giải thích : 4 cặp ghép là

((1,2),(2,3),(3,1))

((1,1),(2,3),(3,2))

((1,3),(2,1),(3,2))

((1,3),(2,2),(3,1))

Bài toán trên ta có thể giải theo cách tầm thường là tìm toàn bộ cách khả năng có thể ghép bằng cách vét cạn, độ phức tạp là N!. Trong trường hợp ma trận A gồm toàn số 1, số cách chọn sẽ là N!.

Dù N<=12 nhưng N! vẫn là 1 giá trị “khủng khiếp”.

Sau đây tôi xin đề xuất cách giải với thuật toán QHĐ trạng thái. Xin nói qua về QHĐ trạng thái.

QHĐ trạng thái là QHĐ trên các trạng thái, các trang thái thường được biều diễn bằng 1 dãy bít hoặc tính trước.

Ví dụ 1: Bài 1 thi QG năm 2006 bảng B ( tôi không nói lại đề ) : Ta dùng QHĐ trạng thái với 8 trạng thái cho mỗi dòng : (0,0),(0,1),(0,2),(0,3),(0,4),(1,3),(1,4),(2,4) với ý nghĩa (i,j) là chọn ô i và ô j, giá trị 0 là không chọn ô nào.

Ví dụ 2: Bài viết “chia sẻ 1 thuật toán hay” của bạn Nguyễn Hiển. Bạn đã dùng 1 dãy bít với ý nghĩa là bít thứ i bằng 1 nếu công việc đó được chọn, bằng 0 nếu công việc đó không được chọn.

Trở lại bài toán của chúng ta. Ta biết: 1 cách ghép cặp là cách ghép 1 sinh viên và 1 vấn đề. Giả sử ta có 1 cách ghép cặp (x1,y1),(x2,y2),…,(xn,yn). Bây giờ ta bỏ đi 1 cặp (x1,y1). Cặp ghép còn lại là (x2,y2),(x3,y3),…,(xn,yn) vẫn là 1 cặp ghép, ta có bài toán với kích thước nhỏ hơn. Như vậy các bạn đã thấy rõ bản chất QHĐ của bài toán này. Để tìm số cách ghép của N sinh viên, ta phải tìm số cách ghép của N-1 sinh viên.

Ta định nghĩa 1 dãy bít X thay cho các trạng thái của các vấn đề. X[i]=1 nếu vấn đề i được chọn. X[i]=0 nếu vấn đề i không được chọn. Độ dài dãy bít tối đa là 12 nên ta thay 1 dãy bít X bằng 1 giá trị TX.

Vì cặp ghép là đầy đủ nên số sinh viên ghép với 1 trạng thái X là số giá trị 1 trong X. Ta cố định các sinh viên này và duỵêt qua tất cả các trạng thái X. Gọi D[TX] là số cách ghép cặp 1 trạng thái X với sl sinh viên đầu tiên, sl là số bít 1 của trạng thái X. Ta có công thức QHĐ:

D[TX] := D[TX]+D[TX xor (1 shl i)] với i thoả mãn X[i]=1 và có sinh viên sl thích vấn đề i.

TX xor (1 shl i) có ý nghĩa là thay giá trị bít thứ i thành 0, ta đã giảm số vấn đề được chọn đi 1.

Sau đây là chương trình:

{ Sử dụng Free Pascal }

Constmax =1 shl 12;

fi='PROBLEM.TXT';

fo='SOLVE.TXT';

Varn :Integer;

f ,g: text;

A:array[0..20,0..20] of Boolean;

D:array[0..max] of longInt; {Mảng D có ý nghĩa như trên }

T:array[0..20]ofInteger; { T lưu lại vị trí các bít 1 để dễ dàng QHĐ hơn }

Procedure Tinh( TX : LongInt );

Vargt , j , i , sl : LongInt;

{sl là số lượng bít 1}

Begin

gt := TX;

i:= -1;

sl := -1;

While gt> 0 do {vong while de tim cac bit 1 trong phan tich nhi phan so TX}

Begin

Inc( i );

If gt and 1 = 1 then {neu bít i là 1 }

Begin

Inc(sl);

T[pt]:=i; {luu lai vi tri cac bit 1}

End;

gt:= gt shr 1;

End;

D[TX]:=0;

For j :=0 to sl do

If A[ sl , T[j] ] then {Sinh viên sl thích vấn đề T[j]}

Inc( D[TX] , D[ TX xor (1 shl T[j])] );

{TX xor (1 shl T[j] là tắt bit thứ T[j]}

End;

Procedure Xuli;

VarTX:LongInt;

Begin

D[0]:=1;

For TX:=1 to (1 shl n)-1 do

Tinh(TX); {QHD voi so TX

Writeln(g, D[1 shl n-1] );

End;

Procedure Nhap;

Vari ,j,t:Integer;

Begin

Read(f,n);

For i:=0 to n-1 do

For j:=0 to n-1 do

Begin

Read(f,t);

A[i,j]:= t =1;

End;

End;

Begin

assign(f,fi);reset(f);

assign(g,fo);rewrite(g);

fillchar(d,sizeof(d),0);

Nhap;

Xuli;

close(f);close(g);

End.

Thuật toán trên có độ phức tạp khoảng 2^N, hiệu quả hơn rất nhiều so với cách duyệt bình thường.

Bài toán trên đã giải quyết xong. Bây giờ, ta sẽ thay đổi bài toán trên 1 chút:

Vị giáo sư đáng kính muốn biết có bao nhiêu cách ghép cặp mà trong đó có chứa cặp sinh viên x và vấn đề y.

Khi ta đã giải quyết được bài toán trên thì bài toán mở rộng trở nên quá dễ.

Trên đây, tôi xin bàn thêm về bài toán cặp ghép. Để nói hết thì thật là khó. Hi vọng các bạn sẽ cùng tôi khám phá những điều mới mẻ và lý thú từ những thuật toán hay.

School@net (Theo THNT)