Thuật toán lùa bò vào chuồng

Thuật toán Lùa bò vào chuồng

Văn Sơn

Trong kỹ thuật lập trình, các bài toán có liên quan đến đếm các đối tượng rất gần gũi và dễ

giải đối với chúng ta vì tính dễ xây dựng thuật toán cho nó. Tuy nhiên, những bài toán

″đếm″ thường yêu cầu với dữ liệu rất lớn. Nếu không biết tổ chức dữ liệu và thuật toán

hiệu quả thì khó có thể đưa ra lời giải. Một trong những cách tiếp cận để xử lý hiện tượng

này là sử dụng thuật toán ″lùa bò vào chuồng″.

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 là mảng tĩnh hay mảng động) 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 thuật toán ta xét ví dụ sau: ″Hãy đếm và cho biết số lần xuất hiện của các chữ cái

La tinh trong một file văn bản. Giả sử văn bản được viết toàn chữ hoa″. Rõ ràng với bài

toán này ta có thể duyệt toàn bộ file 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 file tương đối chậm và có thể file 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 trên 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 file ta đọc lần lượt các ký tự trong file 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 file 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.

Bài 1. Tần số (Đề thi Olimpic sinh viên 2001, khối đồng đội)

Cho một văn bản gồm không quá N (N ≤500) dòng, mỗi dòng chứa không quá 80 ký tự. Ta

gọi tần số của một ký tự trong văn bản là số lần xuất hiện của ký tự đó trong văn bản.

Yêu cầu: Tìm tần số lớn nhất trong các tần số của các chữ cái (không phân biệt chữ hoa

hay chữ thường) trong văn bản đã cho.

Dữ liệu vào: từ file văn bản có tên là FREQ.INP:

Dòng đầu tiên chứa N là số lượng dòng văn bản.

N dòng tiếp theo mỗi dòng chứa một dòng của văn bản đã cho.

Kết quả: ghi ra file văn bản có tên FREQ.OUT tần số lớn nhất tìm được.

Ví dụ:

FREQ.INP

4

faculty of technology

Hanoi National University