SKKN Vận dụng phương pháp sinh để giải một số bài toán liệt kê tổ hợp theo thứ tự từ điển

* Tên báo cáo giải pháp: “Vận dụng phương pháp sinh để giải một số bài toán liệt kê tổ hợp theo thứ tự từ điển”.
* Lĩnh vực: Chuyên môn.
III. Mục đích yêu cầu của giải pháp:
1. Thực trạng ban đầu trước khi áp dụng giải pháp
Trong thời đại ngày nay, thế giới đang diễn ra quá trình tin học hóa trong nhiều lĩnh vực hoạt động của xã hội. Tin học phát triển nhanh như vũ bão và đã trở thành một ngành khoa học đóng vai trò quan trọng không thể thiếu đối với sự phát triển của xã hội.
Trong những năm gần đây, các em học sinh từ cấp tiểu học cho đến phổ thông đã được trang bị những hiểu biết ban đầu về máy tính, biết được lợi ích của máy tính trong đời sống và học tập.Việc học sinh tiếp cận với tin học đã tạo nền tảng cơ sở ban đầu để định hướng cho các em có sở thích và năng khiếu nghiên cứu khoa học theo ngành khoa học công nghệ cao.
Môn tin học giúp học sinh bước đầu làm quen với phương pháp giải quyết vấn đề theo quy trình công nghệ và kỹ năng sử dụng máy tính phục vụ học tập và cuộc sống. Tin học có ý nghĩa to lớn đối với sự phát triển trí tuệ, tư duy thuật toán, góp phần hình thành học vấn phổ thông cho học sinh.
Qua thực tế giảng dạy môn Tin học tại trường THPT An Phú, nhất là trong công tác bồi dưỡng học sinh giỏi, bản thân luôn suy nghĩ làm thế nào để các em tiếp cận một cách tốt nhất, dễ hiểu nhất với các thuật toán. Chính vì thế tôi luôn chú trọng đến việc phân tích và hướng dẫn giải thuật để các em có thể vận dụng và giải bài toán  theo phương pháp hiệu quả nhất.
2. Sự cần thiết phải áp dụng giải pháp
Nhiều quốc gia ý thức được tầm quan trọng của tin học và có những đầu tư lớn vào lĩnh vực này đặc biệt là lĩnh vực giáo dục nhằm đào tạo một đội ngũ tri thức trẻ có nền tảng tin học vững vàng nhằm đáp ứng nhu cầu ngày càng cao của xã hội. Việc đưa tin học vào giảng dạy tại các trường từ cấp Tiểu Học đến THPT nhằm mục đích phổ cập các kiến thức cơ bản về Tin học, ngoài ra còn giúp học sinh có khả năng phân tích, tổng hợp, trừu tượng hóa, khái quát hóa vấn đề, đặc biệt là phát triển khả năng tư duy. Muốn vậy ngoài việc dạy đại trà, hướng nghiệp và dạy nghề cần tạo điều kiện cho học sinh có năng khiếu tin học được phát triển khả năng lập trình để giải quyết tốt các bài toán.
Để có thể phát huy những tài năng tin học thông qua ôn luyện đội tuyển học sinh giỏi, đòi hỏi người dạy phải tiếp cận với nhiều dạng bài toán khó và nắm vững các phương pháp giải quyết bài toán đó. Bài toán trong tin học thường rất đa dạng và phức tạp, mỗi bài toán có thể có nhiều phương pháp giải khác nhau. Để có thể lựa chọn phương pháp thích hợp cho bài toán, chúng ta có thể phân chia các bài toán thành các dạng bài toán tổng quan và chỉ ra phương pháp giải phù hợp.
Bài toán liệt kê là một trong những lớp bài toán khó, có nhiều phương pháp giải lớp bài toán này và một trong những cách giải hiệu quả và phù hợp nhất là sử dụng Phương pháp sinh. Chính vì vậy nên tôi chọn đề tài: “Vận dụng phương pháp sinh để giải một số bài toán liệt kê tổ hợp theo thứ tự từ điển” trong ôn luyện học sinh giỏi môn Tin học.
3. Nội dung giải pháp
3.1. Tiến trình thực hiện
Thông thường, để giải một bài toán theo một phương pháp bất kì, tôi thường hướng dẫn học sinh tiếp cận theo quy trình sau:

3.2. Thời gian thực hiện:
Giải pháp được áp dụng trong quá trình bồi dưỡng học sinh giỏi từ năm 2017-2018 đến nay.
3.3 Biện pháp tổ chức
Trong quá trình giải bài tập, để giải được bài toán dạng liệt kê tổ hợp theo thứ tự từ điển bằng Phương pháp sinh thì phải thỏa mãn hai điều kiện sau:
– Từ yêu cầu của đề bài, ta phải xác định được cấu hình đầu tiên và cấu hình cuối cùng;
– Từ cấu hình đang có, nếu chưa phải là cấu hình cuối cùng ta phải xây dựng được thuật toán để sinh cấu hình tiếp theo.
Phương pháp sinh có thể được mô tả như sau:

* Một số ký hiệu được dùng trong lưu đồ thuật toán:

Trong đề tài này, tôi xin trình bài ba dạng toán cơ bản có thể sử dụng Phương pháp sinh để xử lí:
Dạng 1: Liệt kê dãy nhị phân có độ dài n
Input: nhập từ file văn bản NHIPHAN.INP chứa số nguyên dương n (3<=n < =30)
Output: ghi ra file văn bản NHIPHAN.OUT các dãy nhị phân độ dài n, mỗi dãy nằm trên một dòng.
Một dãy nhị phân độ dài n là một dãy A = A1A2…An trong đó Ai € {0, 1}
(  i : 1 ≤ i  ≤ n). Như vậy dãy đầu tiên sẽ là 00…0 (gồm n phần tử có giá trị 0) và dãy cuối cùng sẽ là 11…1 (gồm n phần tử có giá trị 1). Nhận xét rằng nếu dãy A = (A1, A2, …, An) là dãy đang có và không phải dãy cuối cùng thì dãy kế tiếp sẽ nhận được bằng cách cộng thêm 1 ( theo cơ số 2 ) vào dãy hiện tại. Như vậy kỹ thuật sinh cấu hình kế tiếp từ cấu hình hiện tại có thể mô tả như sau: Xét từ cuối dãy về đầu (xét từ phải sang trái), gặp số 0 đầu tiên thì thay nó bằng số 1 và đặt tất cả các phần tử phía sau vị trí đó bằng 0.
Thuật toán sinh có thể mô tả như sau:
Thuật toán chi tiết:

Chương trình tham khảo
const fi= ‘NHIPHAN.INP’;
fo= ‘NHIPHAN.OUT’;
var n: integer;
A: array[1..30] of integer;
procedure Nhap;
begin
read(n);
end;
procedure xuli;
var i,j: integer;
begin
//Sinh cấu hình đầu
for i:=1 to n do A[i]:=0;
repeat
//Xuất cấu hình hiện tại
for i:=1 to n do write(A[i]);                          writeln;
//Tìm vị trí A[i] =0
i:=n;
while (i>0) and (A[i]=1) do dec(i);     //Nếu chưa là cấu hình cuối cùng thì sinh cấu hình //tiếp theo
if i>0 then
begin
A[i]:=1;
for j:=i+1 to n do A[j]:=0;
end;
until i=0;
end;
begin
assign(input, fi); reset(input);
assign(output, fo); rewrite(output);
nhap;
xuli;
close(input); close(output);
end.
Dạng 2: Liệt kê các tổ hợp chập k của n phần tử
Input: file văn bản TOHOP.INP chứa hai số nguyên dương n, k (1 < k < n < 30) cách nhau ít nhất một dấu cách.
Output: file văn bản TOHOP.OUT các tập con k phần tử của tập {1, 2, …, n}, mỗi tập con trên một dòng.

Ta dễ dàng xác định được cấu hình đầu tiên và cấu hình cuối cùng:
+ Cấu hình đầu: {1, 2, …,k}
+ Cấu hình cuối: {n-k+1, n-k+2, …,n}.Giá trị lớn nhất của phần tử thứ i là:
n-k+i (  i : 1 <= i <= K) gọi là giới hạn trên của phần tử thứ i trong mỗi cấu hình).
Như vậy nếu ta đang có một dãy A đại diện cho một tập con, nếu A là cấu hình kết thúc có nghĩa là tất cả các phần tử trong A đều đã đạt tới giới hạn trên thì quá trình sinh kết thúc, nếu không thì ta phải sinh ra một dãy A mới  tăng dần thỏa mãn vừa đủ lớn hơn dãy cũ theo nghĩa không có một tập con k phần tử nào chen giữa chúng khi sắp thứ tự từ điển.
Ví dụ: n = 7, k =5 và cấu hình đang có A = {1, 2, 5, 6,7}. Các phẩn tử A3 đến A5 đã đạt tới giới hạn trên nên để sinh cấu hình mới ta không thể sinh bằng cách tăng một phẩn tử trong số các A5, A4, A3  lên được, ta phải tăng A2 = 2 lên thành A2 = 3. Được cấu hình mới là A = {1, 3, 5, 6, 7}. Cấu hình này đã thỏa mãn lớn hơn cấu hình trước nhưng chưa thỏa mãn tính chất vừa đủ lớn, muốn vậy ta lại thay A3, A4, A5 bằng giá trị trước nó +1 nghĩa là:

Cấu hình hiện tại của A 1 2 3 4 5
1 2 5 6 7

Cấu hình kế tiếp của A 1 2 3 4 5
1 3 4 5 6

Phương pháp sinh có thể mô tả như sau:

Thuật toán chi tiết:

Chương trình tham khảo
const fi=’TOHOP.INP’;
fo=’TOHOP.OUT’;
var n, k: integer;
A: array[1..30] of integer;
procedure nhap;
begin
read(n,k);
end;
procedure xuli;
var i, j: integer;
begin
for i:=1 to k do A[i]:=i;
repeat
for i:=1 to k do write(A[i]);
writeln;
i:=k;
while (i>0) and (A[i]= n-k+i) do dec(i);
if i>0 then
begin
A[i]:=A[i]+1;
for j:=i+1 to n do A[j]:= A[j-1]+1;
end;
until i=0;
end;
begin
assign(input, fi); reset(input);
assign(output, fo); rewrite(output);
nhap;
xuli;
close(input);close(output);
end.Dạng 3: Liệt kê các hoán vị của n phần tử
Input: file văn bản HV.INP chứa số nguyên dương n < 12.
Output: file văn bản HV.OUT các hoán vị của dãy (1, 2, …, n), mỗi hoán vị trên một dòng.

Ở dạng toán này, ta dễ dàng xác định cấu hình đầu tiên và cấu hình cuối cùng của nó:
– Cấu hình đầu: {1, 2, 3 …,n}
– Cấu hình cuối: {n, n-1, n-2,…, n}
Nhận xét:  nếu ta đang có một dãy A đại diện cho một tập con, nếu A là cấu hình kết thúc có nghĩa là tất cả các phần tử trong A phải có giá trị giảm dần, nếu không thì ta phải sinh ra một dãy A mới thỏa mãn vừa đủ lớn hơn dãy cũ theo nghĩa không có một tập A* (A* là một hoán vị của tập A) chen giữa chúng khi sắp thứ tự từ điển.
Giả sử hoán vị hiện tại là A = (3, 2, 6, 5, 4, 1), xét 4 phần tử cuối cùng, ta thấy chúng được xếp giảm dần, điều đó có nghĩa là cho dù ta có hoán vị 4 phần tử này thế nào, ta cũng được một hoán vị bé hơn hoán vị hiện tại. Như vậy ta phải xét đến x2 = 2, thay nó bằng một giá trị khác. Ta sẽ thay bằng giá trị nào? không thể là 1 bởi nếu vậy sẽ được hoán vị nhỏ hơn, không thể là 3 vì đã có A1 = 3 rồi (phần tử sau không được chọn vào những giá trị mà phần tử trước đã chọn). Còn lại các giá trị 4, 5, 6. Vì cần một hoán vị vừa đủ lớn hơn hiện tại nên ta chọn A2 = 4. Còn các giá trị (A3, A4, A5, A6) sẽ lấy trong tập {6, 5, 2, 1}. Cũng vì tính vừa đủ lớn nên ta sẽ tìm biểu diễn nhỏ nhất của 4 số này gán cho A3, A4, A5, A6 tức là (1, 2, 5, 6). Vậy hoán vị mới sẽ là (3, 4, 1, 2, 5, 6), nghĩa là:

Cấu hình hiện tại của A 1 2 3 4 5 6
3 2 6 5 4 1

Ta có cấu hình kế tiếp:
– Tại vị trí A2 không hợp quy luật tăng dần tính từ sau ra trước nên cần đổi: tìm từ vị trí cuối cùng về trước, nếu gặp phần tử nào vừa lớn hơn A2 thì đổi chỗ với A2, ta tìm được A5. Vậy cần đổi chỗ A2 và A5. Ta được:

– Để đảm bảo thứ tự từ điển, thì các phần tử từ A3 đến A6 phải tăng dần vì vậy cần phải đảo ngược giá trị của các phần tử này (Vì đoạn từ A3 đến A6 là giảm dần).

– Vị trí các phần tử cần đảo vị trí là từ 3 đến 6 (gọi vị trí 3 là  x,  6 là y). Ta cần đổi chỗ Ax và Ay với x tăng dần, y giảm dần và quá trình sẽ kết thúc khi x>=y.