1
I. ĐẶT VẤN ĐỀ
I.1. Lý do chọn đề tài
Sự phát triển như vũ bão của Công nghệ Thông tin và Truyền thông đóng vai
trò không nhỏ trong sự phát triển chung của nhân loại. Đảng và nhà nước đã xác định
rõ ý nghĩa và tầm quan trọng của tin học, Công nghệ Thông tin và Truyền thông cũng
như yêu cầu đẩy mạnh của ứng dụng Công nghệ Thông tin, đào tạo thế hệ trẻ năng
động, sáng tạo, nắm vững tri thức khoa học công nghệ để làm chủ trong mọi hoàn cảnh
công tác và hoạt động xã hội trong thời kỳ công nghiệp hóa và hiện đại hóa đất nước.
Chính vì xác định được tầm quan trọng đó nên nhà nước đã đưa môn tin học vào
trong nhà trường và ngay từ tiểu học học sinh được tiếp xúc môn tin học để làm quen
dần với lĩnh vực công nghệ thông tin, tạo nền móng ban đầu để học những phần nâng
cao tiếp theo. Đối với các em học sinh, có thể nói đây là một hành trang để giúp các
em vững bước đi tới tương lai - tương lai của thời đại công nghệ thông tin bùng nổ!
Trong chương trình Tin học THPT lớp 10 học sinh được giới thiệu các kiến thức
đại cương về tin học, lớp 11 học sinh được giới thiệu về lập trình, lớp 12 học sinh
được học về cơ sở dữ liệu. Đặc biệt, chương trình Tin học lớp 11 là phần được cho là
khó cho Thầy Cô giáo cũng như học sinh, vì phải làm thế nào để học sinh có thể hiểu
được ngôn ngữ lập trình, để từ đó có thể lựa chọn và thiết kế thuật toán. Chương trình
tin học lớp 11 nhằm rèn luyện tư duy về thuật toán cho học sinh, rèn luyện kĩ năng lập
trình, tính kiên trì, tỉ mỉ cẩn thận. Đối với học sinh thì phải làm quen với lối suy nghĩ
logic với sự hoạt động của máy tính, mà đây lại là một lối suy nghĩ hoàn toàn khác với
các môn học khác.
Từ thực tiễn giảng dạy học sinh đại trà cũng như học sinh đội tuyển học sinh giỏi
Tin học của trường THPT tôi thấy rằng, học sinh gặp khó khăn khi chuyển lời giải các
bài toán từ toán sang ngôn ngữ lập trình. Đặc biệt là việc phân tích bài toán, nhận biết
bài toán đó có thể giải quyết bằng phương pháp nào, cỏ lời giải tối ưu hay không?
Để hệ thống lại các chuyên đề bồi dưỡng học sinh giỏi (HSG) Tin học mà tôi đã
dạy trong nhiều năm qua, đồng thời qua quá trình nghiên cứu, giảng dạy, tham khảo ý
kiến đồng nghiệp, tôi thấy rằng một số bài toán tin học có liên quan đến việc đếm.
Chính vì vậy tôi chọn viết đề tài về chuyên đề “Sử dụng thuật toán “lùa bò vào
chuồng” để giải các bài toán đếm”.
2
I.2. Mục tiêu nghiên cứu
"Đếm" là công việc quan trọng và đơn giản mà chúng ta làm thường ngày, điều
đó thì không cần phải bàn đến làm gì? Điều đáng nói ở đây là công việc có vẻ nhàm
chán đó lại chứa bao điều thú vị, nhất là khi gặp những bài toán yêu cầu ta phải "đếm".
"Đếm" ở đây không phải đơn thuần là đếm 1, 2, 3, ... mà còn cần ở người đếm
một sự khéo léo và có thể có một chút kỹ thuật. Bên cạnh đó để giúp các em học sinh
có kiến thức khoa học cơ bản, hiện đại, tiến tiến, có tính tự lập và khả năng sáng tạo,
nhận thức ở mức độ cao, tư duy tốt về lập trình. Các phương pháp đếm đơn giản là một
trong những vấn đề mà bất cứ người lập trình tin học đều cần phải nắm vững.
I.3. Nhiệm vụ nghiên cứu
Trước hết là thực hiện đổi mới phương pháp giảng dạy Tin học làm cho học sinh
tìm ra những kết quả sáng tạo, lời giải hay trên một số “dạng bài toán tin có liên quan
đến việc đếm”; giúp bản thân nắm vững hơn nữa về tư duy thuật toán, khả năng lập
trình, đồng thời để trao đổi và học tập kinh nghiệm với các quý thầy cô giáo trong
nhóm Tin học của nhà trường nói riêng và các quý thầy cô giảng dạy môn Tin học
trong ngành nói chung.
I.4. Đối tượng nghiên cứu
Trong nghiên cứu này, các học sinh được chọn là các em học sinh học môn Tin
học khối 10, khối 11, các học sinh là thành viên của đội tuyển HSG môn Tin học, và
một số giáo viên đứng lớp dạy Tin học ở các trường THPT trên địa bàn.
I.5. Các phương pháp nghiên cứu
* Phương pháp suy luận, tổng hợp: kết hợp từ nhiều nguồn tài liệu tham khảo của
các tác giả và tra cứu trên mạng internet với các đề thi HSG rút ra những kinh nghiệm,
hệ thống lại kiến thức, mở ra các hướng mới.
* Phương pháp trò chuyện – phỏng vấn: trao đổi tâm tình với nhiều HSG để nắm
tình hình trong việc giải các bài toán tin về dãy số (mảng).
* Phương pháp khảo sát: bản thân được tham gia giảng dạy các lớp, đội tuyển
HSG, các kỳ tập huấn; tham khảo các thầy cô, đồng nghiệp giảng dạy đội tuyển nhiều
năm nên có tìm hiểu thêm về các phương pháp làm bài của các em học sinh.
* Phương pháp phân tích lý luận: phân tích giúp học sinh nắm thật rõ bản chất
vấn đề, lựa chọn được phương pháp giải cho phù hợp.
3
II. NỘI DUNG ĐỀ TÀI
II. 1. Lịch sử của vấn đề nghiên cứu
Trong những năm liên tiếp dạy bồi dưỡng HSG môn Tin Học lớp 10, 11, 12 thi
HSG cấp Tỉnh, cũng như tham khảo ý kiến các đồng nghiệp chuyên dạy bồi dưỡng đội
tuyển ở trong trường, trong ngành và các Tỉnh bạn, ở các trường THPT Chuyên, tôi rút
ra một điều là “công việc đếm rất quan trọng trong dạy lập trình”, vì vậy tôi mạnh
dạn chọn viết đề tài: Sử dụng thuật toán “lùa bò vào chuồng” để giải các bài toán
đếm.
II. 2. Cơ sở lý luận của đề tài
Kết hợp các bài giảng chuyên đề bồi dưỡng HSG của cá nhân tôi và các tài liệu
tham khảo để phân tích, tổng hợp, hệ thống.
II. 3. Thực trạng của vấn đề nghiên cứu
Đa số HSG tin rất ngại, sợ khi giải các bài toán tin có liên quan đến việc đếm; rất
lúng túng trong quá trình phân tích, tổ chức dữ liệu, tìm thuật toán hiệu quả để hiểu
được bản chất và vận dụng kiến thức một cách thích hợp.
II. 4. Nội dung nghiên cứu và kết quả nghiên cứu
A. NỘI DUNG NGHIÊN CỨU
Tư tưởng của thuật toán được xây dựng dựa trên suy nghĩ thực tế là để đếm số
lượng bò trên một vùng xác định thì người ta phải tìm cách lùa chúng vào các chuồng
(để chúng khỏi chạy rông) cho dễ đếm. Đương nhiên là những con bò cùng loại phải
được lùa vào cùng một chuồng để dễ phân biệt hoặc lùa mỗi con vào một chuồng thì
càng tốt. Tương tự như vậy, muốn giải bài toán đếm các đối tượng thì ta dùng một cấu
trúc dữ liệu hợp lý (thường dùng kiểu mảng hoặc kiểu con trỏ) với ý nghĩa giống như
các “chuồng” để lưu các đối tượng, mỗi phần tử của mảng tương ứng với một chuồng.
Trên cơ sở đó ta dễ dàng thực hiện được mục đích của mình là thực hiện thao tác đếm.
Để hiểu rõ hơn thuật toán ta xét ví dụ sau: “Viết chương trình nhập từ bàn phím
một xâu ký tự S và thông báo ra màn hình số lần xuất hiện của mỗi chữ cái tiếng Anh
trong S (không phân biệt chữ hoa hay chữ thường)” – Bài 2. Bài tập và thực hành 5 -
sách Tin học 11 - trang 73. Rõ ràng với bài toán này ta có thể duyệt toàn bộ xâu S và
mỗi lần duyệt ta thực hiện thao tác đếm một chữ cái. Sau 26 lần duyệt tương ứng với
26 chữ cái thì ta thu được toàn bộ kết quả. Tuy nhiên, vì việc duyệt xâu như vậy tương
4
đối chậm và có thể xâu văn bản đã cho rất dài nên về thời gian là không chấp nhận
được. Ta vận dụng thuật toán “lùa bò vào chuồng” bằng cách sử dụng một mảng tĩnh
A:array[′A′..′Z′] of Longint; với ý nghĩa như sau: giá trị A[c] trong đó c thuộc [′A′..′Z′]
lưu số lần xuất hiện của ký tự c trong file văn bản. Mảng A được khởi tạo với tất cả
các giá trị bằng 0, khi duyệt xâu ta đọc lần lượt các ký tự trong xâu ra một biến trung
gian ch nào đó, và tăng giá trị của mảng tại vị trí tương ứng có chỉ số ch lên một đơn
vị qua câu lệnh: A[ch]:=A[ch] + 1. Như vậy, bài toán được giải quyết chỉ với một lần
duyệt xâu duy nhất.
Sau đây chúng ta cùng khảo sát một số ví dụ điển hình vận dụng thuật toán này.
1. Bài 1: Đếm bò
Tên chương trình: DEMBO.*
Bài toán đặt ra là giả sử trên cánh đồng rộng thả rất nhiều bò (N con), mỗi con bò
đeo một thẻ có số hiệu nguyên dương (là số tháng tuổi của nó).
Tất nhiên, hai con bò cùng tháng tuổi thì đeo thẻ có số hiệu như nhau. Làm thế
nào để đếm được loại bò nào có nhiều nhất?
Bài toán này có thể phát biểu lại như sau:
+ Nhập từ bàn phím số nguyên dương N (0 < N ≤ 200) và các phần tử của mảng
một chiều A(N) có giá trị nguyên dương (0 < A[i] ≤ 100).
+ Giá trị nào xuất hiện nhiều nhất trong A và xuất hiện bao nhiêu lần?
+ Ví dụ: A(12) = {2, 3, 2, 4, 5, 6, 2, 6, 7, 1, 6, 2} thì A(12) có số phần tử giá trị
bằng 2 là nhiều nhất. Số lượng phần tử này là 4.
Thuật toán “Lùa bò vào chuồng”
Để giải bài toán này người ta dùng thuật toán “lùa bò vào chuồng” gồm 3 bước:
- Bước 1: Đóng dãy chuồng bò và đánh số các chuồng bằng các số tự nhiên liên
tiếp từ 1 đến max (max là số tháng tuổi của con bò già nhất), ban đầu mọi chuồng đều
chưa có bò ở trong.
- Bước 2: Lùa bò vào chuồng có số hiệu bằng số thẻ của nó.
- Bước 3: Duyệt dãy chuồng bò tìm chuồng có nhiều bò nhất.
Áp dụng thuật toán vào bài tập: