Liệt kê xâu nhị phân, tam phân không dùng đệ quy và áp dụng vào giải 1 số bài toán liệt kê, quay lui

MỤC LỤC
1. MỞ ĐẦU	
1.1. Lí do chọn đề tài.
	Hiện nay trong vấn đề luyện thi học sinh giỏi môn tin học cấp trung học phổ thông, mà cụ thể là ngôn ngữ lập trình pascal thuộc chương trình tin học 11, chương trình tin học 11 sách giáo khoa chỉ cung cấp một số kiểu dữ liệu và một số các bài tập cơ bản. Bởi vậy đối với các em học sinh, việc cung cấp cho các em hệ thống những bài tập cơ bản đã là một việc khó, giải những bài toán liệt kê hoặc những bài toán mang tính chất đệ quy còn khó khăn hơn nhiều. Đây là một vấn đề rất khó có thể cung cấp cho học sinh bởi vì các nguyên nhân sau:
+ Lượng kiến thức về lập trình của học sinh còn hạn chế.
+ Thời gian dạy đội tuyển học sinh giỏi không nhiều.
+ Đặc biệt bộ môn Tin học là một “môn phụ” nên việc đầu tư thời gian của học sinh còn ít.
Tôi chọn đề tài: “LIỆT KÊ XÂU NHỊ PHÂN, TAM PHÂN KHÔNG DÙNG ĐỆ QUY VÀ ÁP DỤNG VÀO GIẢI 1 SỐ BÀI TOÁN LIỆT KÊ, QUAY LUI” để giúp các em có một cách đơn giản để giải các bài toán liệt kê mang tính chất đệ quy. Giúp cho các giáo viên trung học phổ thông làm nhiệm vụ như tôi có thêm một tư liệu để tham khảo. Trên cơ sở đó cùng nghiên cứu và phát triển rộng hơn các chuyên đề về luyện thi học sinh giỏi cấp trung học phổ thông.
1.2. Mục đích nghiên cứu.
- Để làm tốt công tác luyện thi học sinh giỏi môn tin học cấp trung học phổ thông.
- Về nội dung: Giải một số bài toán liệt kê mang tính chất đệ quy mà không phải dùng cách giải đệ quy.
1.3. Đối tượng nghiên cứu.
- Học sinh các lớp 11 trường trung học phổ thông Mai Anh Tuấn.
1.4. Phương pháp nghiên cứu.
Kinh nghiệm giáo dục của bản thân trong quá trình giảng dạy, luyện thi học sinh giỏi môn tin học.
- Trao đổi với các chuyên môn với đồng nghiệp.
- Nghiên cứu tài liệu liên quan.
1.5. Những điểm mới của SKKN
- Giải 1 số bài toán khó liệt kê nhưng không phải dùng chương trình con đệ quy.
2. Nội dung sáng kiến kinh nghiệm
2.1. Cơ sở lí luận của sáng kiến kinh nghiệm.
2.1.1. Cơ sở lý luận. 
	- Liệt kê xâu nhị phân, tam phân bằng cách sử dụng nguyên lý đếm trong hệ đếm nhị phân và hệ đếm tam phân.
2.1.2. Cơ sở thực tiễn.
	- Đối với các em học sinh việc tiếp cận với cách đơn giản để liệt kê xâu nhị phân, tam phân hoặc các hệ đếm khác là cơ sở để giải một số bài toán liệt kê hoặc quay lui.
2.2. Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm.
Bài toán 1: Liệt kê xâu nhị phân có chiều dài bằng N.
	Đối với giáo viên: Khi giải quyết bài toán liệt kê xâu nhị phân có chiều dài bằng N. Đa phần tất cả chúng ta đều nghĩ tới chương trình con đệ quy. Chương trình được xây dựng như sau:
const
        nmax=9;
type
        data = byte;
var
        n:data;
        res:array[1..nmax]of data;
procedure xuat;
var     i:data;
begin
        for i:=1 to n do
                write(res[i]);
        writeln;
end;
 procedure try(i:data);
var     j:data;
begin
        if i>n then
                xuat
        else
                for j:=0 to 1 do
                                begin
                                        res[i]:=j;
                                        try(i+1);
                                end;
end;
begin
        readln(n);    try(1);
end.
	Đối với học sinh thpt: Việc xây dựng chương trình con đệ quy đòi hỏi học sinh tư duy rất cao. Nên đối với học sinh để tiếp cận cách giải đệ quy là không hiệu quả. Và trên thực tế với quá trình luyện thi học sinh giỏi môn tin học trung học phổ thông của bản thân tôi thấy rằng hầu như tất cả các học sinh đều không hiểu được cách giải đệ quy. Bởi vì đặc thù của học sinh trung học phổ thông có thời gian tiếp xúc với môn tin học rất ngắn. Đặc biệt nếu là học sinh lớp 10 thi học sinh giỏi môn Tin học thpt thì khả năng tiếp cận là không thể.
Bài toán 2: Liệt kê xâu tam phân có chiều dài bằng N.
const
        nmax=9;
type
        data = byte;
var
        n:data;
        res:array[1..nmax]of data;
procedure xuat;
var     i:data;
begin
        for i:=1 to n do
                write(res[i]);
        writeln;
end;
 procedure try(i:data);
var     j:data;
begin
        if i>n then
                xuat
        else
                for j:=0 to 2 do
                                begin
                                        res[i]:=j;
                                        try(i+1);
                                end;
end;
begin
        readln(n);    try(1);
end.
Bài toán 3:
Bài toán 4: Chia quà.
const  fi='chiaqua.inp';
      fo='chiaqua.out';
var   f:text;
      n:byte;
      mx:integer;
      a,kq,x:array[1..20] of byte;
procedure inp;
var   i:byte;
begin
      assign(f,fi);
      reset(f);
      readln(f,n);
      for i:=1 to n do
            read(f,a[i]);
      close(f);
end;
function min(a,b,c:byte):byte;
var   m:byte;
begin
      m:=a;
      if b<m then m:=b;
      if c<m then m:=c;
      min:=m;
end;
function max(a,b,c:byte):byte;
var   m:byte;
begin
      m:=a;
      if b>m then m:=b;
      if c>m then m:=c;
      max:=m;
end;
procedure try(i,t1,t2,t3:byte);
var   j,h:byte;
begin
      for j:=1 to 3 do
      begin
            x[i]:=j;
            case j of
                  1:t1:=t1+a[i];
                  2:t2:=t2+a[i];
                  3:t3:=t3+a[i];
            end;
            if i=n then
            begin
                  h:=max(t1,t2,t3)-min(t1,t2,t3);
                  if h<mx then
                  begin
                        kq:=x;
                        mx:=h;
                  end
            end
            else try(i+1,t1,t2,t3);
            case j of
                  1:t1:=t1-a[i];
                  2:t2:=t2-a[i];
                  3:t3:=t3-a[i];
            end;
      end;
end;
procedure pri;
var   i:byte;
begin
      assign(f,fo);
      rewrite(f);
      writeln(f,mx);
      for i:=1 to n do
            if kq[i]=1 then write(f,i,' ');
      writeln(f);
      for i:=1 to n do
            if kq[i]=2 then write(f,i,' ');
      writeln(f);
      for i:=1 to n do
            if kq[i]=3 then write(f,i,' ');
      writeln(f);
      close(f);
end;
begin
      inp;
      mx:=maxint;
      try(1,0,0,0);
      pri;
end.
2.3.Giải quyết vấn đề.
2.3.1.Khái niệm hệ đếm.
2.3.2.Quy tắc đếm trong các hệ đếm.
2.3.2.1.Hệ dếm nhị phân.
Khái niệm: Là hệ đếm phụ thuộc vào vị trí, trong đó sử dụng 2 ký hiệu là 0 và 1 để biểu diễn số.
Số trong hệ đếm nhị phân xác định giá trị theo quy tắc: Mỗi đơn vị ở hàng bất kỳ có giá trị bằng 2 lần đơn vị ở hàng kế cận bên phải.
Quy tắc đếm trong hệ đếm nhị phân: 
0000
0
0001
1
0010
2
0011
3
0100
4
0101
5
0110
6
0111
7
1000
8
1001
9
1010
10
1011
11
1100
12
1101
13
1110
14
1111
15
Như vậy ta thấy rằng: Khi đếm trong hệ đếm nhị phân ta chỉ cần tìm 1 chữ số bên phải tận cùng có giá trị bằng 0 sau đó tăng lên 1 đơn vị và giảm tất cả các số ở bên phải số 0 đó về 0. Ở đây áp dụng vào giải 1 số bài toán ta chỉ xét các dãy nhị phân có độ dài N(N được xác định tỳ thuộc vào từng bài toán). Với mỗi ký tự trong dãy nhị phân để biểu diễn 1 trạng thái của 1 sự kiện có 2 trạng thái với khả năng xuất hiện là như nhau. Từ đó ta xây dựng thủ tục liệt kê dãy nhị phân không dùng cách đệ quy như sau:
Procedure Sinh_np(n: byte);
Var i:byte;
Procedure Sinh_ke_tiep(var st:xau);
Var
	j:byte;
Begin
	J:=length(st);
	While st[i]=’1’ do
Begin
	St[j]:=’0’;
	J:=j-1;
End;
	St[j]:=’1’;
End;
Begin
	St:=’’;
	For j:=1 to N do st:=st+’0’;
	While pos(‘0’,st)0 do
	Begin
	Writeln(st);
	Sinh_ke_tiep(st);
	End;
End;
Hệ đếm tam phân.
Khái niệm: Là hệ đếm phụ thuộc vào vị trí, trong đó sử dụng 3 ký hiệu là 0,1,2 để biểu diễn số.
Số trong hệ đếm nhị phân xác định giá trị theo quy tắc: Mỗi đơn vị ở hàng bất kỳ có giá trị bằng 3 lần đơn vị ở hàng kế cận bên phải.
Quy tắc đếm trong hệ đếm nhị phân:
0000
0
0001
1
0002
2
0010
3
0011
4
0012
5
0020
6
0021
7
0022
8
0100
9
0101
10
0102
11
0110
12
0111
13
0112
14
0120
15
0121
16
0122
17
0200
18
0201
19
0202
20
0210
21
0211
22
0212
23
0220
24
0221
25
0222
26
Như vậy ta thấy rằng: Khi đếm trong hệ đếm tam phân ta chỉ cần tìm 1 chữ số bên phải tận cùng có giá trị nhỏ hơn 2 sau đó tăng lên 1 đơn vị và giảm tất cả các số ở bên phải số 0 đó về 0(nếu có). Ở đây áp dụng vào giải 1 số bài toán ta chỉ xét các dãy tam phân có độ dài N(N được xác định tỳ thuộc vào từng bài toán). Với mỗi ký tự trong dãy nhị phân để biểu diễn 1 trạng thái của 1 sự kiện có 3 trạng thái với khả năng xuất hiện là như nhau. Từ đó ta xây dựng thủ tục liệt kê dãy tam phân không dùng cách đệ quy như sau:
Procedure Sinh_tp(n: byte);
Var i:byte;
Procedure Sinh_ke_tiep(var st:xau);
Var
	j:byte;
Begin
	J:=length(st);
	While st[i]=’2’ do
Begin
	St[j]:=’0’;
	J:=j-1;
End;
	St[j]:=chr(ord(st[j])+1);
End;
Begin
	St:=’’;
	For j:=1 to N do st:=st+’0’;
	While (pos(‘0’,st)0)and(pos(‘1’,st)0) do
	Begin
	Writeln(st);
	Sinh_ke_tiep(st);
	End;
End;
2.2.3.Hệ đếm với cơ số bất kỳ.
Đối với hệ đếm cớ số b bất kỳ ta cũng có định nghĩa và cách sinh dãy tương tự tùy vào từng bài toán.
2.3.Ứng dụng hệ đếm vào 1 số bài toán.
Bài toán 1: Sinh dãy nhị phân có độ dài N.
Dữ liệu: Vào từ file văn bản INPUT.INP gồm 1 dòng duy nhất ghi số N.(N<10)
Kết quả: Ghi ra fie văn bản có tên OUTPUT.OUT:
Ghi các xâu nhị phân tìm được, mỗi xâu ghi trên 1 dòng.
Chương trình sinh xâu nhị phân như sau:
Type xau=string;
Procedure Sinh_np(n: byte);
Var i:byte;
Procedure Sinh_ke_tiep(var st:xau);
Var
	j:byte;
Begin
	J:=length(st);
	While st[i]=’1’ do
Begin
	St[j]:=’0’;
	J:=j-1;
End;
	St[j]:=’1’;
End;
Begin
	St:=’’;
	For j:=1 to N do st:=st+’0’;
	While pos(‘0’,st)0 do
	Begin
	Writeln(f2,st);
	Sinh_ke_tiep(st);
	End;
End;
Var 
	St:xau;
	F1,f2:text;
Begin
	Assign(f1,’INPUT.inp’);
	Reset(f1);
Assign(f2,’OUTPUT.OUT’);
	Rewrite(f2);
	Readln(f1,N);
	Close(f1)
	Sinh_np(n);
	Close(f2);
End.
Bài toán 2: Sinh dãy tam phân có độ dài N.
Dữ liệu: Vào từ file văn bản INPUT.INP gồm 1 dòng duy nhất ghi số N.(N<10)
Kết quả: Ghi ra fie văn bản có tên OUTPUT.OUT:
Ghi các xâu tam phân tìm được, mỗi xâu ghi trên 1 dòng.
Chương trình sinh xâu tam phân như sau:
Type xau=string;
Procedure Sinh_tp(n: byte);
Var i:byte;
Procedure Sinh_ke_tiep(var st:xau);
Var
	j:byte;
Begin
	J:=length(st);
	While st[i]=’2’ do
Begin
	St[j]:=’0’;
	J:=j-1;
End;
	St[j]:=chr(ord(st[j])+1);
End;
Begin
	St:=’’;
	For j:=1 to N do st:=st+’0’;
	While (pos(‘0’,st)0)and(pos(‘1’,st)0) do
	Begin
	Writeln(f2,st);
	Sinh_ke_tiep(st);
	End;
End;
Var 
	St:xau;
	F1,f2:text;
Begin
	Assign(f1,’INPUT.inp’);
	Reset(f1);
Assign(f2,’OUTPUT.OUT’);
	Rewrite(f2);
	Readln(f1,N);
	Close(f1)
	Sinh_np(n);
	Close(f2);
End.
Bài toán 3: Biểu thức Zero(Nguồn đề thi HSG Tỉnh Thanh Hóa năm 2019)
	Cuội viết liên tiếp các số tự nhiên từ 1 đến N thành dãy:1 2 3 N. Cuội đố Bờm điền các phép toán + hoặc – vào giữa 2 số tự nhiên liên tiếp sao cho biểu thức thu được có kết quả bằng 0. 
Yêu cầu: Bạn hãy giúp Bờm viết chương trình liệt kê tất cả các cách điền dấu phép toán thích hợp.
Dữ liệu: Vào từ file văn bản INPUT.INP gồm 1 dòng duy nhất ghi số N.(N<10)
Kết quả: Ghi ra fie văn bản có tên OUTPUT.OUT:
Dòng đầu tiên: Ghi số M là số cách điền dấu vào biểu thức.
M dòng tiếp theo, mỗi dòng ghi 1 kết quả tìm được.
Ý tưởng:
	Ta thấy rằng ở đây chỉ có 2 toán tử là: + và -. Nếu ta coi toán tử + là 1 toán tử - là 0. Để tìm cách đan xen có kết quả ta chỉ cần liệt kê dãy nhị phân có độ dài là (N-1). Sau đó tính giá trị biểu thức thu được. Nếu giá trị của biểu thức thu được bằng 0 thì xâu nhị phân đó chính là xâu nhị phân cần tìm.
Chương trình như sau:
Type xau=string;
Var 
	St:xau;
	F1,f2:text;
	M,N:longint;
	Luu:array[1..1000000] of xau;
Function kt(st:xau):boolean;
Var
	N1,k:longint;
Begin
	N1:=1;
	For k:=2 to N do
	Begin
	If st[k-1]=’0’ then N1:=N1-k;
	If st[k-1]=’1’ then n1:=n1+k;
	End;
	If N1=0 then kt:=true
	Else 
	Kt:=false;
End;
Procedure Sinh_np(n: byte);
Var i:byte;
Procedure Sinh_ke_tiep(var st:xau);
Var
	j:byte;
Begin
	J:=length(st);
	While st[i]=’1’ do
Begin
	St[j]:=’0’;
	J:=j-1;
End;
	St[j]:=’1’;
End;
Begin
	St:=’’;
	For j:=1 to N do st:=st+’0’;
	While pos(‘0’,st)0 do
	Begin
	If kt(st) then 
Begin
	M:=m+1;
Luu[m]:=st;
end;
	Sinh_ke_tiep(st);
	End;
End;
Begin
	Assign(f1,’INPUT.inp’);
	Reset(f1);
Assign(f2,’OUTPUT.OUT’);
	Rewrite(f2);
	Readln(f1,N);
	Close(f1);
	M:=0;
	Sinh_np(n-1);
	Writeln(f2,m);
	if m >0 then
	for k:=1 to m do
	begin
	write(f2,’1’);
	for i:=2 to n do
	if luu[k][i-1]=’0’ then 
Begin
write(f2,’-’);str(I,st1);
write(f2,st1);
	End
	Else
Begin
write(f2,’+’);str(I,st1);
write(f2,st1);
	End;
	Writeln(f2);
	end;
	Close(f2);
End.
Bài toán 4: Chia quà.
	Cuội viết liên tiếp các số tự nhiên từ 1 đến N thành dãy:1 2 3 N. Cuội đố Bờm điền các phép toán + hoặc – vào giữa 2 số tự nhiên liên tiếp sao cho biểu thức thu được có kết quả bằng 0. 
Yêu cầu: Bạn hãy giúp Bờm viết chương trình liệt kê tất cả các cách điền dấu phép toán thích hợp.
Dữ liệu: Vào từ file văn bản INPUT.INP gồm 1 dòng duy nhất ghi số N.(N<10)
Kết quả: Ghi ra fie văn bản có tên OUTPUT.OUT:
Dòng đầu tiên: Ghi số M là số cách điền dấu vào biểu thức.
M dòng tiếp theo, mỗi dòng ghi 1 kết quả tìm được.
2.4. Hiệu quả của sáng kiến kinh nghiệm đối với hoạt động giáo dục, với bản thân, đồng nghiệp và nhà trường.
3. Kết luận, kiến nghị
3.1. Kết luận.
3.2. Kiến nghị.
Tài liệu tham khảo.
- Tài liệu bồi dưỡng học sinh giỏi môn tin học(lưu hành nội bộ tỉnh Thanh Hóa)
- Giáo trình kỹ thuật lập trình . Tác giả: Lê Minh Hoàng.
DANH MỤC CÁC ĐỀ TÀI SKKN MÀ TÁC GIẢ ĐÃ ĐƯỢC HỘI ĐỒNG SKKN SỞ GD TỈNH THANH HÓA ĐÁNH GIÁ ĐẠT TỪ LOẠI C TRỞ LÊN.
TT
Tên đề tài
Đạt giải
Năm học 
1
Xây dựng phần mềm tính điểm bằng cách sử dụng NNLT VBA trên EXCEL
C
2006-2007
2
Xây dựng sơ đồ khối mô phỏng thuật toán và chương trình với dữ liệu đầu vào động
B
2007-2008
3
Xây dựng bài giảng tương tác sử dụng phần mềm power point trong giảng dạy tin học 11
C
2008-2009
4
Bài toán cơ bản về xử lý số lớn trong luyện thi học sinh giỏi cấp THPT
C
2013-2014