Sáng kiến kinh nghiệm 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
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.
Bạn đang xem tài liệu "Sáng kiến kinh nghiệm 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ải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
đượ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í:
Ví dụ:
NHIPHAN.INP
NHIPHAN.OUT
3
000
001
010
011
100
101
111
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à 111 (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.
Sinh cấu hình đầu {Gán A[i]:=0 với i tăng từ 1 đến n}
Repeat
Xuất cấu hình hiện tại {in A[i] với i tăng từ 1 đến n}
Tìm từ cuối dãy về trước - vị trí A[i] = 0
Nếu chưa hết dãy (i > 0) thì:
+ A[i]:=1;// Vị trí vừa tìm được
+ Gán các phần tử từ vị trí i+1 về sau bằng 0
Until i = 0;
Thuật toán sinh có thể mô tả như sau:
Thuật toán chi tiết:
Sai
Đúng
Đúng
Sai
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.
Ví dụ:
TOHOP.INP
TOHOP.OUT
5 3
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
3 4 5
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à:
Đạt tới giới hạn
(n-k+i)
Xét từ sau ra trước
Cấu hình hiện tại của A
1
2
3
4
5
1
2
5
6
7
Chưa đạt gới giạn
Cấu hình kế tiếp của A
1
2
3
4
5
1
3
4
5
6
+1
+1
+1
Sinh cấu hình đầu {Gán A[i]:=i với i tăng từ 1 đến k}
Repeat
Xuất cấu hình hiện tại {Xuất A[i] với i tăng từ 1 đến k}
Tìm từ cuối dãy về trước - vị trí A[i] chưa đạt giới hạn n –k + i
Nếu chưa hết dãy (i > 0) thì:
+ A[i]:=A[i]+1;
+ A[j]:=A[j-1] +1 với j tăng từ i+1 đến k
Until i = 0;
Phương pháp sinh có thể mô tả như sau:
Thuật toán chi tiết:
Sai
Đúng
Đúng
Sai
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.
Ví dụ:
HV.INP
HV.OUT
3
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
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à:
Giá trị tăng dần
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:
1
2
3
4
5
6
3
4
6
5
2
1
Để đả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).
1
2
3
4
5
6
3
4
6
5
2
1
x
y
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.
x
y
Đổi chổ A3, A6
1
2
3
4
5
6
3
4
1
5
2
6
x
y
Đổi chổ A4, A5
1
2
3
4
5
6
3
4
1
2
5
6
Sinh cấu hình đầu {Gán A[i]:=i với i tăng từ 1 đến n}
Repeat
Xuất cấu hình hiện tại {Xuất A[i] với i tăng từ 1 đến n}
Tìm từ cuối về trước- vị trí A[i] không thỏa tính chất tăng dần
Nếu chưa hết dãy (i > 0) thì:
+ Tìm từ cuối dãy về trước – vị trí A[k] >A[i] rồi đổi chỗ A[k] và A[i]
+ Đảo ngược đoạn cuối từ vị trí i+1 đến n
Until i = 0;
Phương pháp sinh có thể mô tả như sau:
Thuật toán chi tiết:
Sai
Sai
Sai
Chương trình tham khảo
const fi='HV.INP;
fo='HV.OUT';
Var n: integer;
A: array[1..20] of integer;
procedure nhap;
begin
read(n);
end;
procedure doicho(var x, y: integer);
var tam: integer;
begin
tam:=x;
x:=y;
y:=tam;
end;
procedure xuli;
var i, k, x, y: integer;
begin
for i:=1 to n do A[i]:=i;
repeat
for i:=1 to n do write(A[i]);
writeln;
i:=n-1;
while (i>0) and (A[i]>A[i+1]) do dec(i);
if i>0 then
begin
k:=n;
while A[k]<A[i] do dec(k);
doicho(A[i], A[k]);
x:=i+1; y:=n;
while x<y do
begin
doicho(a[x], a[y]);
inc(x);
dec(y);
end;
end;
until i=0;
end;
begin
assign(input, fi); reset(input);
assign(output, fo); rewrite(output);
nhap;
xuli;
close(input); close(output);
end.
Ví dụ:
PT0101.INP
PT0101.OUT
6
110101
101101
011101
101011
011011
010111
010101
001101
010101
001011
010011
010101
* Một số bài tập áp dụng
Bài tập 1: Liệt kê dãy nhị phân có độ dài n. Trong đó các chữ số ‘01’ xuất hiện đúng 2 lần.
Input: nhập từ file văn bản PT0101.INP chứa số nguyên dương n (4 < n < =30)
Output: ghi ra file văn bản PT0101.OUT các dãy nhị phân độ dài n, mỗi dãy trên một dòng.
Hướng dẫn: Yêu cầu của đề là n>4 và các số ‘01’ xuất hiện đúng 2 lần. Vậy để tiết kiệm chi phí chỉ cần sinh nhị phân n-4 phần tử. Ví dụ: n= 8 thì chỉ cần sinh nhị phân 4 phần tử và kết hợp ‘0101’ là 8 phần tử. Do các số ‘01’ xuất hiện đúng 2 lần nên việc sinh 4 phần tử còn lại được xác định như sau:
- Cấu hình đầu: {1, 1, 1, 1}
- Cấu hình cuối:{0, 0, 0, 0}
- Sinh cấu hình kế tiếp: Tìm từ cuối dãy về trước, gặp phần tử bằng 1 ta chuyển về 0. Vậy các cấu sẽ sinh ra trong trường hợp này là: 1111, 1110, 1100, 1000, 0000 (đảm bảo tính chất không có số “01” nào xuất hiện). Tương ứng mỗi cấu hình ta tìm cách sinh ra cấu hình mới kết hợp với ‘0101’ nghĩa là từ 1 cấu hình 1111 ta sẽ có các cấu hình tương ứng: 11110101; 11101101; 11011101; 10111101; 01111101; 11101011; 11011011; 10111011; 01111011; 11010111; 10110111; 01110111; 10101111; 01101111; 01011111
n:=n-4;
Sinh cấu hình đầu {Gán A[i]:=1 với i tăng từ 1 đến n}
i:=n;
Repeat
Sinh các cấu hình: dựa vào cấu hình hiện tại, kết hợp “01” “01”
A[i]:=0;
Dec(i);
Until i < 0;
Phương pháp sinh có thể mô tả như sau:
Ví dụ:
NHOM.INP
NHOM.OUT
5 2
Lan
Tung
Cuc
Chuc
Mai
Lan Tung
Lan Cuc
Lan Chuc
Lan Mai
Tung Cuc
Tung Chuc
Tung Mai
Cuc Chuc
Cuc Mai
Chuc Mai
Bài tập 2: Trong một nhóm có n học sinh, giáo viên muốn chọn ra k học sinh trong số n học sinh để nghiên cứu và báo cáo về một chuyên đề bài học. Hãy giúp giáo viên đưa ra các phương án lựa chọn thích hợp.
Input: file văn bản NHOM.INP gồm
+ Dòng đầu 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.
+ n dòng tiếp theo, mỗi dòng là tên một học sinh
Output: file văn bản NHOM.OUT liệt kê các phương án lựa chọn k học trong n học sinh, mỗi phương án trên một dòng.
Ví dụ:
XAU.INP
XAU.OUT
ABABB
AABBB
ABABB
ABBAB
ABBBA
BAABB
BABAB
BABBA
BBAAB
BBABA
BBBAA
Hướng dẫn: tương tự sinh tổ hợp chập k của n phần tử
Bài tập 3: Nhập vào một xâu văn bản. In ra các hoán vị khác nhau của xâu theo thứ tự từ điển.
Input: file văn bản XAU.INP gồm một dòng duy nhất là xâu văn bản cần tìm các hoán vị khác nhau của nó.
Output: file văn bản XAU.OUT liệt kê các hoán vị khác nhau của xâu gốc, mỗi hoán vị nằm trên một dòng.
Hướng dẫn: Dạng bài liệt kê hoán vị nhưng xử lí trên xâu
- Cấu hình đầu: để có được cấu hình đầu ta phải sắp xếp xâu theo thứ tự tăng dần của các kí tự “AABBB”
- Cấu hình cuối là ngược lại so với cấu hình đầu “BBBAA”
- Điểm khác so với hoán vị trên số là sẽ có các kí tự giống nhau, khi đổi chỗ hai kí tự này cho nhau thì vô nghĩa – giống cấu hình cũ. Vì vậy nếu muốn đổi chỗ hai kí tự này thì chúng phải khác nhau.
Vậy phương pháp sinh có thể mô tả như sau:
Sắp xếp xâu gốc(S) để được cấu hình đầu tăng dần
Repeat
Xuất cấu hình hiện tại
Tìm từ cuối về trước vị trí S[i] < S[i+1]
Nếu chưa hết dãy (i > 0) thì:
+ Tìm từ cuối dãy về trước – vị trí k, sao cho S[k] >S[i] rồi đổi chỗ S[k] và S[i]
+ Đảo ngược đoạn cuối của xâu S từ vị trí i+1 đến n (length(s))
Until i = 0;
Ví dụ:
PTS.INP
PTS.OUT
5
5
4+1
3+2
3+1+1
2+2+1
2+1+1+1
1+1+1+1+1
Bài tập 4: Cho số nguyên dương n (n<=30). Tìm tất cả các cách phân tích số n thành tổng các số nguyên dương (0). Các cách phân tích là hoán vị của nhau thì chỉ tính 1 cách
Input: file văn bản PTS.INP gồm 1 số nguyên dương n
Output: file văn bản PTS.OUT, mỗi dòng là một cách phân tích tìm được
Hướng dẫn: Xác định phương pháp sinh
- Cấu hình đầu: {n}
- Cấu hình cuối : {1,1,1....,1} (n phần tử có giá trị 1);
- Sinh cấu hình kế tiếp: Để dễ cho việc phân tích bài toán, xét ví dụ với n = 8. Ta sẽ có các cấu hình tương ứng là:
1.
{8}
9.
{4, 3, 1}
17.
{3, 1, 1, 1, 1, 1}
2.
{7, 1}
10.
{4, 2, 2}
18.
{2, 2, 2, 2}
3.
{6, 2}
11.
{4, 2, 1, 1}
19.
{2, 2, 2, 1, 1}
4.
{6, 1, 1}
12.
{4, 1, 1, 1, 1}
20.
{2, 2, 1, 1, 1, 1}
5.
{5, 3}
13.
{3, 3, 2}
21.
{2, 1, 1, 1, 1, 1, 1}
6.
{5, 2, 1}
14.
{3, 3, 1, 1}
22.
{1, 1, 1, 1, 1, 1, 1, 1}
7.
{5, 1, 1, 1}
15.
{3, 2, 2, 1}
8.
{4, 4}
16.
{3, 2, 1, 1, 1}
Giả sử ta đang ở cấu hình 14.{3, 3, 1, 1}. Cấu hình kế tiếp 15. {3, 2, 2, 1} được xác định như sau: Tìm từ sau ra trước, vị trí phần tử có giá trị lớn hơn 1 (vị trí thứ 2). Giảm vị trí thứ 2 đi một đơn vị. Vậy tổng còn lại (sau khi trừ hai phần tử đầu) là: k-i+1. Trong đó k là số phần tử của cấu hình hiện có (k=4), vậy tổng còn lại là 4-2+1 =3. Chia đều tổng cho các phần tử tiếp theo một lượng bằng phần tử thứ 2 (có giá trị bằng 2). Phần còn dư sẽ chia cho phần tử cuối cùng. Ta được cấu hình 15 (3, 2, 2, 1). Để dễ hiểu ta xét thêm trường hợp với n =15. Cấu hình hiện có là {4, 4, 1, 1, 1, 1, 1, 1, 1}, cấu hình tiếp theo là {4, 3, 3, 3, 2}.
k=9
Cấu hình
hiện tại
1
2
3
4
5
6
7
8
9
4
4
1
1
1
1
1
1
1
Tìm từ sau ra trước gặp phần tử A[i]>1 (i=2), giảm A[2] 1 đơn vị, A[2] = 4 - 1 = 3;
Tổng= k – i + 1= 9 – 2 + 1 = 8;
8 chia tối đa được 2 phần tử có giá trị A[2]: thương = tổng div A[i] è 8 div 3 = 2. Gán giá trị 2 phần tử A[3], A[4] = 3. Phần dư gán cho phần tử A[5] ( A[5] = 2);
Cập nhật lại k.
k=5
Cấu sinh
kế tiếp
1
2
3
4
5
4
3
3
3
2
Phần dư
Phương pháp sinh có thể mô tả như sau:
A[1]:=n;
K:=1// số phần tử hiện có của cấu hình hiện tại
Repeat
Xuất cấu hình hiện tại;
Tìm từ sau ra trước, vị trí A[i]>1;
Giảm A[i] một đơn vị
Nếu chưa phải là cấu hình cuối cùng (i>0) thì
+ Tổng := k – i +1; Thương := k div A[i]; Dư := thương mod A[i];
+ Gán các phần tử phía sau A[i] có giá trị bằng với A[i] (A[i+j] := A[i], với j:1àthương)
+ Cập nhật lại k: k := i + thương
+ Nếu còn phần dư (Dư > 0) thì gán phần dư cho phần tử A[k+1]
K:=k+1
A[k]:=Dư
Until i = 0;
Bài tập 5: Một cửa hàng nhỏ có N loại bánh khác nhau, mỗi loại bánh có số lượng rất lớn. Có một người mua hàng cần mua k cái bánh. Giả sử người đó chỉ quan tâm đến loại bánh mà không quan tâm tới cái bánh cụ thể và thứ tự chọn chúng. Hãy liệt kê các cách khác nhau mà khách hàng có thể lựa chọn để mua bánh.
Ví dụ:
MHANG.INP
MHANG.OUT
2 3
1 1 1
1 1 2
1 2 2
2 2 2
Input: file văn bản MHANG.INP gồm một dòng ghi hai số nguyên dương N và K. Giữ hai số cách nhau bằng một khoảng cách.
Output: file văn bản MHANG.OUT gồm nhiều dòng, mỗi dòng là một phương án mua hàng của khách hàng
Hướng dẫn:
- Cấu hình đầu: {1, 1, ...,1} - Chọn k cái bánh loại 1
- Cấu hình cuối: {n, n, ..., n}- Chọn k cái bánh loại n
- Sinh cấu hình kế tiếp: xét ví dụ n =3 và k = 5. Ta có các cấu hình:
1.
{1, 1, 1, 1, 1}
8.
{1, 1, 2, 2, 3}
15.
{1, 3, 3, 3, 3}
2.
{1, 1, 1, 1, 2}
9.
{1, 1, 2, 3, 3}
16.
{2, 2, 2, 2, 2}
3.
{1, 1, 1, 1, 3}
10.
{1, 1, 3, 3, 3}
17.
{2, 2, 2, 2, 3}
4.
{1, 1, 1, 2, 2}
11.
{1, 2, 2, 2, 2}
18.
{2, 2, 2, 3, 3}
5.
{1, 1, 1, 2, 3}
12.
{1, 2, 2, 2, 3}
19.
{2, 2, 3, 3, 3}
6.
{1, 1, 1, 3, 3}
13.
{1, 2, 2, 3, 3}
20.
{2, 3, 3, 3, 3}
7.
{1, 1, 2, 2, 2}
14.
{1, 2, 3, 3, 3}
21.
{3, 3, 3, 3, 3}
Phương pháp sinh có thể mô tả như sau:
Sinh cấu hình đầu {Các phần tử đều bằng 1 – lấy k cái bánh loại 1}
Repeat
Xuất cấu hình hiện tại
Tìm từ sau ra trước, vị trí A[i]n
Nếu chưa phải là cấu hình cuối cùng (i>0) thì
+ Tăng A[i] lên một đơn vị
+ Các phần tử sau A[i] bằng A[i]( A[j] := A[i] với (j: i+1 à k))
Until i = 0;
Trên đây, là một số dạng bài toán cơ bản có thể dùng phương pháp sinh để xử lý. Tuy nhiên, mỗi phương pháp lập trình đều có ưu và nhược điểm của riêng nó. Phương pháp sinh có ưu điểm trong trường hợp liệt kê toàn bộ số lượng nhỏ cấu hình, nhưng đối với bộ dữ liệu lớn thì rất hạn chế trong quá trình duyệt.
IV. Hiệu quả của giải pháp
Giải pháp trên giúp học sinh tiếp cận với kỹ thuật lập trình mới, rèn luyện học sinh kỹ năng lập trình, xử lí bài toán, phát huy tính tích cực, sáng tạo của học sinh.
Áp dụng 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” góp một phần không nhỏ vào hiệu quả, chất lượng bồi dưỡng học sinh giỏi tại đơn vị trong những năm gần đây. Một số kết quả đạt được từ khi vận dụng giải pháp (năm học 2017-2018):
Học sinh giỏi cấp tỉnh 2018
Tin học trẻ
2018
Được dự thi học sinh giỏi cấp Quốc gia 2019
Tin học trẻ 2019
01 giải nhì,
01 giải ba
01 giải ba,
01 giải khuyến khích
01 học sinh
02 giải ba
V. Mức độ ảnh hưởng:
Giải pháp đã góp phần mang lại hiệu quả nhất định trong công tác bồi dưỡng học sinh giỏi tại đơn vị và có thể áp dụng ở một số đơn vị khác.
VI. Kết luận
1. Những bài học kinh nghiệm
Quá trình tuyển chọn, bồi dưỡng học sinh giỏi môn Tin học là quá trình giáo dục nâng cao, biến những học sinh có tiềm năng thành học sinh có khả năng, những học sinh ít hoặc chưa bộc lộ niềm say mê, hứng thú với môn tin học thành những học sinh say mê, hứng thú với môn Tin học. Trong quá trình này vai trò của người giáo viên rất quan trọng. Quan trọng từ khâu tuyển chọn, dẫn dắt, truyền dạy, uốn nắn đến việc khích lệ sự cố gắng, tích cực và khả năng tự học, tự sáng tạo của học sinh.
Phẩm chất, uy tín, năng lực của người giáo viên có ảnh hưởng trực tiếp, quan trọng, thậm chí có tính quyết định đối với quá trình học tập và rèn luyện của học sinh. Do vậy, giáo viên phải tự đào tạo, tự cố gắng hoàn thiện về phẩm chất và năng lực chuyên môn; tâm huyết với công việc, yêu thương học trò và giúp đỡ đồng nghiệp. Giáo viên không chỉ truyền dạy kiến thức mà cao hơn là, dạy cho học sinh cách đi tìm kiến thức, chân lý từ những bài giảng của mình. Đặc biệt đây là lĩnh vực thay đổi và phát triển liên tục. Giáo viên phải cập nhật kiến thức kịp thời mới đáp ứng được yêu cầu phát triển của môn học đặc thù này.
Cùng với sự truyền dạy kiến thức, người giáo viên phải truyền được cảm hứng say mê, yêu mến môn học cho học sinh, đặc biệt là học sinh giỏi. Không có niềm say mê, dù có kiến thức cũng ít sáng tạo và khó đạt được kết quả tốt, khó đạt được đỉnh cao trong học tập và thi cử, đặc biệt là lĩnh vực CNTT.
2. Những kiến nghị, đề xuất
Ban giám hiệu nhà trường và phụ huynh học sinh cần tạo điều kiện tốt nhất cho đội ngủ học sinh giỏi của trường. Giáo viên bồi dưỡng cần quản lí và kiểm tra việc học tập của học sinh một cách nghiêm túc.
Trên đây là một vài kinh nghiệm nhỏ của tôi trong quá trình bồi dưỡng học sinh giỏi, rất mong được sự góp ý của đồng nghiệp để đề tài được nhân rộng và đạt kết quả cao hơn. Tôi cam đoan những nội dung báo cáo là đúng sự thật.
Xin chân thành cảm ơn.
Xác nhận của đơn vị áp dụng giải pháp Người viết giải pháp
Nguyễn Phi Hùng
TÀI LIỆU THAM KHẢO
Sách Giáo Khoa Tin Học 11 – Hồ Sĩ Đàm (Chủ biên).
Tài Liệu Sách Giáo Khoa Chuyên Tin Học Quyển 1, 2 – Hồ Sĩ Đàm (Chủ biên).
150 Bài Tập Toán Tin – Lê Minh Hoàng.
Giải Thuật & Lập Trình – Lê Minh Hoàng.
Wedsite:
File đính kèm:
sang_kien_kinh_nghiem_van_dung_phuong_phap_sinh_de_giai_mot.doc
