Nếu học mảng một chiều mà lại không biết đến các bài toán quan trọng sau đây thì e rằng sẽ có thiếu sót lớn về phía người dạy và cũng là thiệt thòi cho người học:
Đó là:
Lập một chương trình nhập số tự nhiên n (n>=2) và số k (1<=k<=n). Hãy
a/ In ra các tổ hợp chập k của n phần tử
b/ In ra các hoán vị của n
c/ In ra các chỉnh hợp chập k của n phần tử.
Ví dụ: Nhập n=5, k=3 thì
Câu a/ phải cho kết quả là: {1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,5},… , {3,4,5}
Câu b/ phải cho kết quả là: (1,2,3,4,5), (1,2,3,5,4), … , (5,4,3,2,1)
Câu c/ phải cho kết quả là: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1),…, (5,4,3).
Hôm nay, tôi mới chỉ giới thiệu cách giải của câu a/ thôi:
Phương pháp 1:
Dùng thủ tục đệ quy để tìm tiếp các phần tử của từng tổ hợp một.
Trường hợp cụ thể: Với n=5, k=3.
Mỗi tổ hợp là một mảng a[1], a[2], a[3].
Phần tử a[1] có thể nhận giá trị bằng j thay đổi từ 1 đến 3.
Phần tử a[2] có thể nhận j thay dổi từ a[1]+1 đến 4.
Phần tử a[3] có thể nhận j thay đổi từ a[2]+1 đến 5.
Khi có đủ 3 phần tử thì viết dãy a[1], a[2], a[3] ra, trái lại thì tìm tiếp.
Trường hợp Tổng quát:
Mỗi tổ hợp là một mảng a[1], a[2], …, a[k].
Phần tử a[1] có thể nhận j thay đổi từ 1 đến n-k+1.
Phần tử a[2] có thể nhận j thay dổi từ a[1]+1 đến n-k+2.
….
Phần tử a[i] có thể nhận j thay đổi từ a[k-1]+1 đến n-k+i. Với i=1,…,k
Khi có đủ k phần tử thì viết dãy a[1], a[2], …, a[k] ra, trái lại thì tìm tiếp.
Hình thái của Thủ tục đệ quy như sau:
Thủ tục ĐiTiếp(i:byte);
Biến phụ j:byte;
Bắt đầu:
Cho j thay đổi từ a[i-1]+1 đến n-k+1: Với mỗi j đó thì:
Bắt dầu:
Cho a[i]=j.
Nếu i=k thì xuất a[1], a[2],…, a[k] trên một dòng (để các dãy không dính nhau)
Trái lại thì điTiếp(i+1)
Hết
Hết
Trong chương trình chính:
Mới đầu cho a[0]=0, rồi gọi thử tục ĐiTiếp(1) là xong!
Phương pháp 2.
Cho một số nhị phân 000…0, gồm k chữ số 0. Thực ra có thể coi như một dãy gồm k số 0. Cho số nhị phân tăng dần, mỗi lần 1 đơn vị, cho đến lớn nhất là 111…1 gồm k số 1. Mỗi lần tăng, cho máy đếm xem có bao nhiêu chữ số 1. Nếu số chữ số 1 là k thì dãy a[i] sẽ nhận các giá trị là vị trí của chữ số 1 trong số nhị phân đó. Ví dụ: số nhị phân la 01011 thì a[1]=2, a[2]=4, a[3]=5.
Còn số nhị phân gồm k chữ số tăng thêm như thế nào thì hãy xem mẹo vặt sau đây:
Cho i=k
Chừng nào chữ số thứ i là 1 thì i cho ChuSo[i]=0 và cho i giảm 1 đơn vị (nhớ dùng while chứ không dùng if)
Khi i giảm mãi đến lúc ChuSo[i]=0.
Khi đó nếu i đó >0 thì cho ChuSo[i]=1.
Ví dụ: Xét số 10111. Mớ đầu cho i=5. Do ChuSo[5]=1 nên i giảm mãi i=2 vi ChuSo[2]=0. Lúc này ta cho ChuSo[2]=1 là xong, và dược 11000
Trên tinh thần bạn đã nắm bắt được các thuật toán trên và mày mò chán chê không được thì hãy xem mã nguồn sau đây viết bằng Pascal. Bạn có thể viết lại bằng C.
uses crt;
var i,n,k : byte;
a : array[0..10] of byte;
cach : word;
(*--------------------------------------------------------*)
procedure XuatKetQua;
var i:byte;
begin
cach:=cach+1;
write('Cach ',cach,': (');
for i:=1 to k do write(a[i],',')
gotoxy(wherex-1,wherey);
writeln(').');
if readkey=#27 then halt;
end;
(*--------------------------------------------------------*)
procedure DiTiep(i:byte);
var j:byte;
begin
for j:=a[i-1]+1 to N-k+i do
begin
a[i]:=j;
if i=k then XuatKetQua
else DiTiep(i+1);
end;
end;
(*--------------------------------------------------------*)
BEGIN
TextMode(c80);
writeLn('Viet ra cac to hop chap k cua n phan tu 1..n.');
write('n,k = '); readln(n,k);
a[0]:=0; cach:=0;
DiTiep(1);
writeLn('Go Esc de thoat...');
repeat until ReadKey=#27;
END.
Phương pháp 2:
uses crt;
type mangByte=array[1..10] of byte;
var i,n,k,SoBit1 : byte; {SoBit1 la soo luong cac chu so 1}
b : mangByte;
cach : word;
(*--------------------------------------------------------*)
procedure TangBin_DemBit1(var SoBIN:mangByte; var sb1:byte);
{tang nhi phan mang trong khuon kho n phan tu va cho so bit 1=?}
var i:byte;
begin
i:=n; {n la bien chinh chi so luong cac phan tu cua mang}
while (SoBIN[i]=1) and (i>0) do
begin
SoBIN[i]:=0;
i:=i-1;
end;
if i>0 then SoBIN[i]:=1;
sb1:=0;
for i:=1 to n do
if SoBIN[i]=1 then sb1:=sb1+1;
end;
(*--------------------------------------------------------*)
procedure XuatKetQua;
var i:byte;
begin
cach:=cach+1;
write('Cach ',cach,': (');
for i:=1 to n do
if b[i]=1 then write(i,',');
gotoxy(wherex-1,wherey);
writeln(').');
if readkey=#27 then halt;
end;
(*--------------------------------------------------------*)
BEGIN
TextMode(c80);
writeln('Viet ra cac to hop chap k cua n phan tu:');
write('n,k = ');
readln(n,k);
for i:=1 to n do b[i]:=0;
cach:=0;
repeat
TangBin_DemBit1(b,SoBit1);
if SoBit1=k then XuatKetQua;
until SoBit1=n;
writeln('Go Esc de thoat...');
repeat until readkey=#27;
END.
Chú ý:
Bạn phải chịu khó gõ vào thật chính xác, chứ copy vào có thể không chạy được đâu!
Mã nguồn trên đây có tính chất minh họa các thuật toán nói trên, còn khi cho n rất lớn, thì bạn có khi phải chỉnh sửa lại để kết quả mỹ mãn… Chẳng hạn khi cho n=1000 thì số cách có thể vượt quá kiểu word, rồi mảng Byte ở trên cũng có các chỉ số rất lớn!