SKKN Giúp học sinh hiểu rõ hơn về bit ở lớp 10 và áp dụng bit giải các bài tập học sinh giỏi lớp 11

MỤC LỤC
 Trang
 Mở đầu	 2
 Lí do chọn đề tài	 2
 Mục đích nghiên cứu	2
 Đối tượng nghiên cứu	2
 Phương pháp nghiên cứu	3
Nội dung sáng kiến kinh nghiệm	3	 
 2.1 Cơ sở lí luận của bit và các phép xử lí bit	3
A. Khái niệm về bit và nội dung liên quan đến bit	3
a. Khái niệm bit	3
b. Mã hóa thông tin trong máy tính	3
c. Hệ đếm 	3
B. Các phép xử lí bit	4
Phép cộng bit	4
Phép đảo bit.	4
Phép nhân bit .	5
Phép loại trừ bit	5
Phép dịch bit phải	6
Phép dịch bit trái	6
 Thực trạng vấn đề trước khi áp dụng SKKN	6
 Các giải pháp giải quyết vấn đề	7
Giúp học sinh lớp 10 hiểu về bit và chuyển đổi sang hệ nhi phân của bộ mã ASCII	7
Áp dụng bit giải các bài toán học sinh giỏi tin lớp 11	10
 Hiệu quả của sáng kiến kinh nghiệm	21
III. Kết luận và kiến nghị	 22 
3.1 Kết luận	.. 22
3.2 Kiến nghị	...22
3.3 Tài liệu tham khảo	23
IV. Danh mục các sáng kiến kinh nghiệm đã đạt	24
V. Phụ lục 	25
I. MỞ ĐẦU
1.1 Lí do chọn đề tài
 Với sự phát triển như vũ bảo của Tin học tôi luôn trăn trở làm thế nào đào tạo ra các thế hệ học sinh có trình độ về tin học cụ thể hơn là về lập trình, vậy để làm được điều đó tôi luôn phải đổi mới phương pháp giảng dạy cho phù hợp với từng bài học, tiết học, từng đối tượng học sinh, đặc biệt là trong bồi dưỡng đội tuyển học sinh giỏi.
Trong những năm gần đây, trong các đề thi học sinh giỏi tỉnh, quốc gia cũng như các bài tập trên các trang giải bài trực tuyến nhưvn.spoj.com, vnoi.info,  có nhiều bài tập mà nếu chúng ta sử dụng các kiến thức như đệ quy, duyệt, quy hoạch động,  có thể giải quyết được nhưng gặp nhiều khó khăn về mặt tốc độ cũng như giới hạn dữ liệu. Trong khi đó nếu chúng ta sử dụng kĩ thuật xử lí theo bit hoặc các phương pháp trên có kết hợp với các thao tác xử lý theo bit lại cho một hiệu quả rất rất cao. Chính vì thế tôi chọn đề tài “Giúp học sinh hiểu rõ hơn về bit ở lớp 10 và áp dụng bit giải các bài tập học sinh giỏi lớp 11” làm đề tài nghiên cứu của mình để đáp ứng được lí do trên..
Mục đích nghiên cứu
Mục đích nghiên cứu của sáng kiến kinh nghiệm là nghiên cứu cơ sở lí luận và thực tiễn để học sinh nắm vững các khái niệm về bit (mã nhị phân), mã hóa được các số thành mã nhị phân như trong bộ mã ASCII.
Cung cấp thêm một số kiến thức sâu hơn về bit (phần này học sinh được học ở chương trình lớp 10 nhưng không sâu) và ứng dụng của phương pháp xử lí bit giải một số bài toán học sinh giỏi tin học một cách hiệu quả hơn.
Đối với bản thân và đồng nghiệp cùng trao đổi để bồi dưỡng thêm về kiến thức chuyên môn, nâng cao trình độ, mở rộng thêm vốn kiến thức hạn hẹp của mình.
Nếu thực hiện được mục tiêu trên học sinh và giáo viên sẽ hứng thú khi học về bit cũng như giải các bài toán khó bị giới hạn dữ liệu và thời gian.
1.3 Đối tượng nghiên cứu
-Học sinh khối 10 trường THPT Thiệu Hóa.
- Học sinh khối 11 trường THPT Thiệu Hóa.
- Nội dung kiến thức bài 2: “ Thông tin và dữ liệu”, bài đọc thêm số 2.
- Cách xử lí bit và ứng dụng vào giải các bài tập học sinh giỏi THPT, các bài tập trên các trang trực tuyến: vnoi.info, laptrinh.ntu.edu.vn,
1.4 Phương pháp nghiên cứu
- Nghiên cứu cơ sở lí luận về bit, các phép xử lí bit
 - Nghiên cứu tài liệu về các chuyên đề như loang, DFS, BFS, ..., lí thuyết về các phép toán trên bit.
Trên cơ sở đó phân tích, tổng hợp, khái quát,  rút ra những vấn đề cần thực hiện trong đề tài.
Tham khảo và trao đổi ý kiến với bạn bè, đồng nghiệp, cấp trên. Tham gia giải bài, phân tích, đánh giá, góp ý trên các câu lạc bộ, diễn đàn trực tuyến.
II. NỘI DUNG SÁNG KIẾN KINH NGHIỆM
2.1 Cơ sở lí luận
 A. Khái niệm về bit, mã hóa thông tin, hệ đếm.
	a. Bit
Bit (Binary digit) là đơn vị nhỏ nhất dùng để biểu diễn thông tin trong máy tính. Mỗi bit là một chữ số nhị phân 0 hoặc 1 thể hiện hai trạng thái với khả năng xuất hiện như nhau. 
Ví dụ : Tung đồng xu có hai mặt hoàn toàn cân xứng với khả năng xuất hiện của mỗi mặt là như nhau. Kí hiệu mỗi mặt của đồng xu là 1 và mặt kia là 0 thì sự xuất hiện kí hiệu 1 hay 0 sau khi tung đồng xu cho ta một lượng thông tin là 1 bit.
b. Mã hóa thông tin
Thông tin có nhiều dạng khác nhau nhưng khi đưa vào máy tính chúng đều được biến đổi thành dạng chung – dãy bit. Dãy bit đó là mã nhị phân của thông tin mà nó biểu diễn. cách biến đổi như vậy được gọi là mã hóa thông tin.
 c. Hệ đếm 
- Hệ thập phân:
Sử dụng tập kí hiệu gồm 10 chữ số 0,1,2,3,4,,9 để biểu diễn.
Giá trị số trong hệ thập phân được xác định theo quy tắc: mỗi đơn vị ở một hàng bất kì có giá trị bằng 10 đơn vị ở hàng kế cận bên phải.
Hệ nhị phân
Chỉ dùng hai kí hiệu là chữ số 0 và 1
Vd: 1012= 1x22+0x21+1x20=510
Hệ hexa (cơ số 16)
Sử dụng các kí hiệu: 0,1,2,3,,9,A,B,C,D,E,F
	Vd: 1BE16= 1x162+11x161+14x160=44610
 B. Các phép xử lý bit cơ bản
Các phép toán xử lý bit đối với 2 dãy bit x, y sẽ xử lý lần lượt bit thứ nhất của x với bit thứ nhất của y, bit thứ 2 của x với bit thứ 2 của y,  bit thứ k của x với bit thứ k của y, cứ như vậy cho đến hết.
 Phép cộng bit (or)
Phép toán trên thao tác bit or lấy hai dãy bit có độ dài bằng nhau và thực hiện phép toán lí luận bao hàm or trên mỗi cặp bit tương ứng. Kết quả ở mỗi vị trí sẽ là 0 nếu cả 2 bit là 0, ngược lại thì kết quả là 1.
X
y
x or y
0
0
0
0
1
1
1
0
1
1
1
1
Ví dụ 	 x = 0101 (số thập phân 5).
 y = 0011 (số thập phân 3).
 x or y = 0111 (số thập phân 7).
Phép đảo bit (not)
Toán tử đảo bit not (còn gọi là toán tử lấy phần bù) là toán tử một ngôi thực hiện phủ định luận lý trên từng bit, tạo thành bù 1 của giá trị nhị phân cho trước. Bit nào là 0 thì sẽ trở thành 1 và 1 sẽ trở thành 0.
x
not x
0
1
1
0
Ví dụ
x = 0111 (số thập phân 7).
not x = 1000 (số thập phân 8).
Phép nhân bit (and)
Toán tử thao tác bit and lấy hai toán hạng nhị phân có chiều dài bằng nhau và thực hiện phép toán lý luận and trên mỗi cặp bit tương ứng bằng cách nhân chúng lại với nhau. Nhờ đó, nếu cả 2 bit ở vị trí được so sánh đều là 1 thì bit hiển thị ở dạng nhị phân sẽ là 1 (1 x 1 = 1), ngược lại kết quả sẽ là 0 (1 x 0 = 0).
X
y
x and y
0
0
0
0
1
0
1
0
0
1
1
1
Ví dụ
x = 0101 (số thập phân 5).
y = 0011 (số thập phân 3).
x and y = 0001 (số thập phân 1).
Phép loại trừ bit (xor)
Phép toán thao tác bit xor lấy hai dãy bit có cùng độ dài và thực hiện phép toán logic bao hàm or trên mỗi cặp bit tương ứng. Kết quả ở mỗi vị trí là 1 chỉ khi bit đầu tiên là 1 hoặc nếu chỉ khi bit thứ 2 là 1, nhưng sẽ là 0 nếu cả hai là 0 hoặc cả hai là 1. Ở đây ta thực hiện phép so sánh 2 bit, kết quả là 1 nếu hai bit khác nhau và là 0 nếu hai bit giống nhau.
X
y
x xor y
0
0
0
0
1
1
1
0
1
1
1
0
Ví dụ
x = 0101 (số thập phân 5). 
y = 0011 (số thập phân 3).
x xor y = 0110 (số thập phân 6).
 Phép dịch bit phải (shr k)
Dịch chuyển dãy sang phải k bit.
Ví dụ
x = 13(00001101).
x shr 2 = 3(00000011).
 Phép dịch trái (shl k)
Dịch chuyển dãy sang trái k bit.
Ví dụ
x = 13(00001101).
x shl 2 = 54(00110100).
2.2 Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm
a. lớp 10
- Khi học sinh học bài 2 “Thông tin và dữ liệu” các em đã nắm bắt được đơn vị đo lượng thông tin là Bit nhưng các em mới thấy loáng thoáng. 
- Rồi đến bộ mã ASCII các em đều thấy phức tạp với dãy các con số 0 và 1 dày đặc. Và đến đây các em phải nhớ máy móc các dãy bit trong bộ mã ASCII này.
Vấn đề ở đây là có những cách nào giúp các em tự chuyển đổi được sang mã nhị phân mà không cần phải nhớ máy móc nữa. Tôi mạnh dạn đưa ra cách mới ngoài sách giáo khoa.
- Tuy dãy bit trong bài này chỉ là nội dung nhỏ của chương trình nhưng nếu không biết sẽ không hiểu máy tính mã hóa thông tin như thế nào và các ứng dụng của bit ra sao.
b. lớp 11
Khi học sinh cũng như giáo viên làm đến các bài toán học sinh giỏi thì vấn đề cần quan tâm là làm sao để giải được với dữ liệu lớn, ít bộ nhớ mà tốc độ cao.
Khi tìm ra giải pháp giải quyết vấn đề trên thì các bài tập được giải dễ dàng hơn, output được tối đa hơn.
 Vậy làm thế nào để làm được điều đó tôi mạnh dạn ứng dụng Bit vào giải các bài toán này.
2.3 Các giải pháp giải quyết vấn đề
 A. Giúp học sinh lớp 10 hiểu rõ hơn về bit và tự hoàn thành bộ mã ASCII
- Các khái niệm về Bit sách giáo khoa đã trình bầy nên tôi không trình bầy lại nữa.
Vậy nên giờ tôi chỉ giới thiệu thêm cách chuyển số từ hệ thập phân sang hệ nhị phân như sau:
Cách 1: Chuyển theo cách ở bài đọc thêm số 2 sách giáo khoa.
Lấy số thập phân chia liên tiếp cho 2 (hoặc 16 ở hệ hexa) cho đến khi nhận được thương số bằng 0. Để có dãy nhị phân ta viết các số dư theo thứ tự ngược lại (số dư sau cùng viết trước và tiếp tục cho đến hết).
VD: 	1110= ?2=?16
Chia 11 cho 2 được các số dư là 1,1,0,1. Viết ngược lại được 1011 nhưng để biểu diễn 8 bit thì ta thêm các bit không phía trước thành: 00001011
Tương tự hệ 16 là: B biểu diễn 3 bit thì thành 00B.
Cách 2: Kẻ bảng điền các bit 0 hoặc 1 để được các số cần biểu diễn.
Vấn đề là làm sao để điền nhanh các bit mà vẫn chính xác
Ta có: nếu có n bit thì có 2n số thập phân được biểu diễn và phạm vi biểu diễn là từ 0 đến 2n-1.
Ví dụ1: 2 bit có 22=4 số thập phân từ 0 đến 3 được biểu diễn ở mã nhị phân.
Ta có bảng sau: gồm cột mã thập phân, và có 2 bit nên mã nhị phân có 2 cột.
Mã thập phân
Mã nhị phân
0
0
0
1
0
1
2
1
0
3
1
1
Ví dụ 2: 3 bit có 23=8 số thập phân từ 0 đến 7 được biểu diễn ở mã nhị phân.
Ta có bảng sau:
Mã thập phân
Mã nhị phân
0
0
0
0
1
0
0
1
2
0
1
0
3
0
1
1
4
1
0
0
5
1
0
1
6
1
1
0
7
1
1
1
Đến đây giáo viên hỏi học sinh tìm ra quy luật để điền các bit 0 và 1 vào các cột của mã nhị phân.
Nhiều học sinh không tìm ra và nghĩ là phải học thuộc lòng như trong bảng mã ASCII. Đến đây giáo viên gợi ý và đưa ra phương pháp như sau:
Phương pháp: 
Ta có nếu có n bit:
Thì có 2n số thập phân được biểu diễn và phạm vi biểu diễn là từ 0 đến 2n -1.
Đầu tiên xác định số cột của mã nhị phân: chính là số bit để biểu diễn
Vd: n=3 bit thì có 3 cột ở mã nhị phân.
Điền các bit 0 và 1 vào các cột lần lượt từ cột phải sang trái theo quy luật:
+ Đầu tiên phải là các bit 0 trước rồi mới xen kẽ các bit 1
+ số lượng bit 0 và 1 đặt xen kẽ nhau là bằng 2n (với n bắt đầu từ 0 đến n-1).
Vd: n=3 thì
 Cột 1 từ phải sang sẽ là 20=1 tức cứ một bit 0 rồi đến bit 1 rồi bit 0 cứ thế cho hết hàng.
Cột 2 từ phải sang là 21=2 Tức cứ 2 bit 0 rồi xen 2 bit 1, rồi 2 bit 0, cứ thế cho hết. 
Cột 3 từ phải sang là 22=4 Tức cứ 4 bit 0 rồi xen 4 bit 1, rồi 4 bit 0, cứ thế cho hết.
Nhận xét: 
Điền như vậy ta được bảng như trên.
Và đến đây các em mở bộ mã ASCII ra và so sánh. Ta thấy ở bộ mã biểu diễn giống bảng ta biểu diễn. chỉ khác có thêm các bit 0 đứng trước cho đủ 8 bit.
Như vậy các em tự biểu diễn được các số thập phân sang nhị phân một cách đơn giản mà không phải nhớ máy móc như trước.
Tương tự các em lập bảng với n=4 cho cô.
Kết quả các em điền dễ ràng như sau:
Mã thập phân
Mã nhị phân
0
0
0
0
0
1
0
0
0
1
2
0
0
1
0
3
0
0
1
1
4
0
1
0
0
5
0
1
0
1
6
0
1
1
0
7
0
1
1
1
8
1
0
0
0
9
1
0
0
1
10
1
0
1
0
11
1
0
1
1
12
1
1
0
0
13
1
1
0
1
14
1
1
1
0
15
1
1
1
1
B. Áp dụng bit vào giải các bài tập học sinh giỏi lớp 11
Tôi tình bày thông qua các bài toán cụ thể như sau:
Bài 1. Liệt kê tập con
Cho tập hợp con N phần tử khác nhau, liệt kê tất cả các tập hợp con của tập N phần tử đã cho (kể cả tập rỗng).
Nhận xét: Xét một dãy gồm N bit. Khi đó với mỗi tập con của tập N phần tử đều có thể biểu diễn bằng dãy N bit này và ngược lại mỗi dãy bit có độ dài N đều biểu diễn một tập con của tập N phần tử. Do đó ta có thể duyệt tất cả các dãy bit độ dài N để xuất ra tập con tương ứng. Mặt khác ta có với tất cả các dãy bit độ dài N tương ứng với giá trị 0 cho đến 2n – 1.
00000 = 0
00001 = 1
00010 = 2
.
11110 = 2n - 2
11111 = 2n - 1 
Do đó với bài toán trên ta có thể giải quyết như sau: Duyệt biến x chạy từ 0 đến 2n-1. Với mỗi giá trị x, xuất ra tập con dựa vào dãy bit của nó.
Chương trình tham khảo:
program bai_1;
const
fi = 'bai4.inp';
fo = 'bai4.out';
var
a: array[0..30] of longint;
n,i,j,t: longint;
function geb(x, y: longint): longint;
begin
exit(1 and (x shr y));
end;
begin
assign(input,fi); 
reset(input);
assign(output,fo); 
rewrite(output);
readln(n);
for i:= 1 to n do read(a[i]);
for i:= 0 to (1 shl n)-1 do
begin
for j:= 1 to n do
begin
t:= geb(i, j-1);
if t=1 then write(a[j],' ');
 end;
writeln;
end;
close(input); 
close(output);
end.
Bài 2. Hoán đổi giá trị hai biến
Cho 2 số a và b. Viết chương trình hoán đổi vị trí của hai số a và b cho nhau.
Nhận xét: Với bài toán trên chúng ta thường giải quyết theo 2 phương pháp là sử dụng biến trung gian để hoán đổi hoặc không sử dụng biến trung gian. Chương trình như sau:
Chương trình 1: Không sử dụng biến trung gian.
program doi_cho_1;
var a,b:real;
begin
write('nhap vao hai so a, b:=');
readln(a,b);
a:= a+b;
b:= a-b;
a:= a-b;
writeln('gia tri sau khi hoan doi la: a = ',a:8:2,' b = ',b:8:2);
readln
end.
Chương trình 2: Sử dụng biến trung gian.
program doi_cho_2;
var a,b,t:real;
begin
write('nhap vao hai so a, b:=');
readln(a,b);
t:= a;
a:= b;
b:= t;
writeln('gia tri sau khi hoan doi la: a = ',a:8:2,' b = ',b:8:2);
readln
end.
Phân tích, đánh giá: Với hai chương trình trên chúng ta thấy mỗi chương trình đều có ưu điểm và nhược điểm riêng của nó. Với chương trình 1 dù là kiểu dữ liệu là kiểu số nguyên hay kiểu số thực thì khi a và b lớn thì tổng (a + b) sẽ vượt qua giới hạn của các kiểu dữ liệu (tràn dữ liệu) nên dẫn đến kết quả bài toán sẽ sai. Với chương trình 2 thì khắc phục được lỗi của chương trình 1 nhưng về mặt tốc độ sẽ chậm hơn do phải khai báo thêm một biến t và thực hiện các câu lệnh gán. Chúng ta có thể khắc phục được nhược điểm của mỗi cách trên bằng phương pháp xử lí bit với chương trình như sau:
Chương trình 3:Dùng xử lý bit, tính chất của phép xor.
program doi_cho_3;
var a,b: real;
begin
write('nhap vao hai so a, b:=');
readln(a,b);
a:= a xor b;
b:= b xor a;
a:= a xor b;
writeln('gia tri sau khi hoan doi la: a = ',a:8:2,' b = ',b:8:2);
readln
end.
Bài 3. Sắp xếp dãy 
Cho tệp data.dat gồm các số nguyên không âm nhỏ hơn 500 000 đôi một khác nhau. Hãy sắp xếp tệp theo thứ tự tăng dần và đưa ra tệp result.dat
Nhận xét:Bài toán sắp xếp là một bài toán chúng ta đã biết và chúng ta cũng đã có nhiều thuật toán dùng để sắp xếp. Tuy nhiên với bài toán trên chúng ta thấy điều đặc biệt ở đây là về giới hạn của dữ liệu. Nếu ta sử dụng mảng để lưu trữ và sắp xếp thì thật khó khăn vì dung lượng bộ nhớ cũng như thời gian sắp xếp đã chiếm một mức thời gian lớn. Ta cũng có thể sử dụng phương pháp sắp xếp ngoài bằng file nhưng đây cũng chưa phải là một phương pháp tối ưu vì vấn đề thời gian.
Tuy nhiên, phương pháp sắp xếp đánh dấu bằng một vài thủ thuật dùng bit thô sơ lại cho ta một kết quả tốt. Ta chỉ cần dùng một mảng kiểu byte với khoảng 63000 phần tử là đủ để xử lý bài toán này. Khởi tạo một mảng ban đầu với tất cả các phần tử đều bằng 0. Với mỗi phần tử đọc từ file ra ta đánh dấu bit tương ứng trong mảng cho tới khi hết file bằng thủ tục batbit. Để lấy kết quả ghi ra file, ta dùng hàm laybit.
Chương trình tham khảo:
program bai_3;
const
fi = 'data.dat';
fo = 'result.dat';
bt=8;
max=63000;
var
a:array[0..max] of byte;
f:text;
procedure finish;
var
i,j:longint;
function laybit(x,j:longint):byte;
begin
laybit:=(x shr j) and 1;
end;
begin
assign(f,fo);rewrite(f);
for i:=0 to max do
for j:=0 to bt-1 do
if laybit(a[i],j)=1 then write(f,(i*bt+j),' ');
close(f);
end;
procedure start;
var
i,tg:longint;
procedure batbit(x,y:longint);
begin
a[x]:=a[x] or (1 shl y)
end;
begin
fillchar(a, sizeof (a), 0);
assign(f,fi);reset(f);
while not seekeof(f) do
begin
read(f,tg);
batbit(tg div bt,tg mod bt)
end;
close(f);
end;
begin
start;
finish;
end.
Bài 4. Số đặc biệt
Cho dãy gồm n số nguyên dương, trong đó có duy nhất một số xuất hiện lẻ lần, các số còn lại có số lần xuất hiện là một số chẵn lần.
Yêu cầu: Tìm ra số xuất hiện lẽ lần.
Dữ liệu vào: Tệp SNUM.INP có cấu trúc:
Dòng đầu tiên ghi giá trị n;
N dòng tiếp theo mỗi dòng ghi một số nguyên dương;
Dữ liệu ra: Tệp SNUM.OUT có cấu trúc:
Gồm một dòng ghi số đặc biệt tìm được.
Giới hạn:
1<=n<=2*10^6, mỗi số nguyên có giá trị<=10^9.
Thời gian thực hiện mỗi test không quá 1s.
Ví dụ
SNUM.INP
SNUM.OUT
5
12345
9876
12345
145
9876
145
Nhận xét:Với bài toán trên, ta có các cách làm như sử dụng đếm phân phối hoặc sắp xếp dãy lại theo một thứ tự nhất định rồi duyệt tìm số xuất hiện lẽ lần.
Đoạn chương trình 1: Dùng đếm phân phối.
oo:= trunc(1e7);
readln(n);
fillchar(c, sizeof(c), 0); 
	// c có ý nghĩa c[i] là số lần xuất hiện giá trị i trong dãy
for i:= 1 to n do
begin
readln(x);
inc(c[x]); // tăng số lần xuất hiện x lên 1
end;
for i:= 1 to oo do
if c[i] mod 2 = 1 then
begin
writeln(i);
break;
end;
Đoạn chương trình 2: Dùng sắp xếp, xin chỉ được trình bày đoạn xử lý sau khi đã sắp xếp.
readln(n);
for i:= 1 to n do readln(a[i]);
// sử dụng mảng a để lưu dãy số
sort(1, n); // phần xử lí sắp xếp
a[n+1]:= a[n]+1; dem:= 1;
for i:= 2 to n+1 do
if a[i] = a[i-1] then inc(dem)
else
begin
if dem mod 2 = 1 then
begin
writeln(a[i-1]);
break;
end;
dem:= 1;
end;
Phân tích, đánh giá:Với hai chương trình trên mỗi cách đều có ưu và nhược điểm riêng.
Với việc sử dụng đếm phân phối, độ phức tạp chỉ là O(oo) song lại không thể qua được hết test, vì oo trong bài lên đến 10^9, tức là nó phụ thuộc vào giá trị của các số trong dãy số.
Với việc sử dụng sắp xếp, giá trị của các số nguyên trong dãy số không bị phụ thuộc, quá trình duyệt chỉ tốn độ phức tạp O(n), tổng độ phức tạp chung của thuật toán là O(n^2) hoặc O(nlogn), tức là phụ thuộc vào độ phức tạp của quá trình sắp xếp. Với giới hạn đề bài n<=2000000, thì việc chạy qua những test có n lớn chỉ là do may mắn!
Để khắc phục được các nhược điểm trên ta sử dụng phương pháp xử lí bit, cụ thể với bài này ta sử dụng tính chất của phép xor. Với cách này chương trình sẽ chạy qua hết mọi test của bài toán chỉ với độ phức tạp O(n) mà không có bất kỳ một hạn chế nào.
Đoạn chương trình 3: Dùng xử lý bit, phép xor.
readln(N);
ans:= 0; // biến ans chính là kết quả cần tìm
for i:= 1 to n do
begin
readln(x);
ans:= ans xor x;
end;
writeln(ans);
Bài 5. Lại là chuỗi (Nguồn: laptrinh.ntu.edu.vn – Mã bài: STRAIGAIN)
Cho một xâu S chỉ gồm hai kí tự A và B. Tại mỗi bước đi, bạn phải chọn ra 2 hoặc 3 kí tự liên tiếp, sau đó đảo ngược nó lại (A thành B và B thành A). Hỏi cần tối thiểu bao nhiêu bước để tất cả các kí tự trong xâu S đều giống nhau.
Dữ liệu vào: Tệp STANDARD.INP có cấu trúc:
Dòng đầu tiên chứa một số nguyên dương N là số lượng kí tự của xâu S (2 ≤ N ≤ 20).
Dòng thứ hai chứa xâu S gồm N kí tự.
Dữ liệu ra: Tệp STANDARD.OUT ra có cấu trúc:
Gồm một dong là số bước biến đổi ít nhất để tất cả các kí tự trong xâu S đều giống nhau. Dữ liệu đảm bao luôn có kết quả.
Ví dụ
STANDARD.INP
STANDARD.OUT
7
AABBBAA
1
Nhận xét: Với bài này chúng ta cũng dùng tư tưởng BFS. Trong quá trình biến đổi để sinh cấu hình, nếu ta dùng xử lý bình thường, thì sẽ mất rất nhiều thời gian vì mỗi lần vậy phải duyệt đến N ký tự, không thể chạy qua hết test. Với xử lý bit, ta sẽ chỉ cần dùng trong vài phép gán.
Chương trình tham khảo:
program bai_4;
const
fi = 'standard.inp';
fo = 'standard.out';
var
b, q: array[0..1 shl 21] of longint;
bit: array[0..21] of longint;
n, oo, s: longint;
procedure docdl;
var
i: longint;
c: string;
begin
readln(n);
readln(c);
oo:= (1 shl n)-1; s:= 0;
for i:= n downto 1 do s:= s*2+ord(c[i])-65;
bit[0]:= 1;
for i:= 1 to 21 do bit[i]:= bit[i-1]*2+1;
end;
function daobit(x, d, c: longint): longint;
begin
daobit:= x xor bit[c];
if d0 then daobit:=daobit xor bit[d-1];
end;
procedure xuly;
var
l, r, i, j, u, v: longint;
begin
fillchar(b, sizeof(b), 0);
if (S=0)or(S=oo) then
begin
writeln(0);
exit;
end;
l:= 1; r:= 1; Q[1]:= S; b[S]:= 1;
repeat
u:= Q[l]; inc(l);
for i:= 1 to 2 do
for j:= 0 to n-i-1 do
begin
v:= daobit(u, j, j+i)