Một ông sao sáng, hai ông sáng sao...
Nguyễn Xuân Huy
Bạn đếm có thạo không?
Chúng ta học đếm từ tấm bé nhưng hình như chưa thật thạo. Nhiều khi chúng ta lúng túng không biết vận dụng các kỹ thuật đếm vào việc giải các bài toán tin học. Bài này giới thiệu với bạn đọc một vài kỹ thuật đếm khá phổ biến trong tin học.
Đếm theo phần
Người xưa đếm sao trên trời theo kiểu "Một ông sao sáng, hai ông sángsao...". Đã bao giờ bạn thử tìm hiểu ý nghĩa của câu hát trên chưa? Xinmách bạn rằng, cho đến tận ngày nay, các nhà thiên văn vẫn áp dụng, phương pháp đơn giản này để đếm sao đấy. Bản chất của kỹ thuật này là như sau. Ngườita chia các ngôi sao trên bầu trời theo từng nhóm căn cứ vào cấp độ sáng củachúng. Các sao sáng nhất gọi là sao cấp 0, sau đó đến các sao cấp 1, cấp 2,...Rồi người ta đếm theo từng nhóm. Dĩ nhiên là bầu trời mênh mông, số lượng saolà vô hạn, đếm mãi cũng không xuể. Ta đang nói đến việc đếm các ngôi sao nhìnthấy được bằng mắt thường. Ta thử vận dụng kỹ thuật đếm theo nhóm để giải bàitoán-tin học sau đây.
Bài 1. (Sơn cột, bài thi học sinh giỏiquốc gia, khối B). Trên mảnh đất hình chữ nhật kích thước m x n ô vuông đơn vị,người ta xây các cột bê tông hình vuông tại các ô. Mỗi cột bao gồm một số khốilập phương đơn vị chồng lên nhau. Các cột có thể cao thấp khác nhau. Sau đóngười ta sơn các mặt bê tông nhìn thấy được của các cột. Tính diện tích cầnsơn.
Dữ liệu vào: Ghi trong tệp văn bản COT.INP, dòng đầu tiên là hai giá trị m và n.Tiếp theo đó là m dòng, mỗi dòng có n số tự nhiên biểu thị chiều cao đo bằng sốlượng khối lập phương tạo nên cột bê tông tại vị trí đó.
m, n và chiều cao của mỗi cột không quá 100.
Dữ liệu ra: Hiển thị trên màn hình diện tích cần sơn tính theo ô vuông đơn vị.
Thí dụ, với m=3, n=4 và tệp COT.INP có dạng sau:
COT.INP
3 4
1 0 3 1
2 2 0 1
0 0 1 4
Thì sau khi thực hiện chương trình trên màn hình phải xuất hiện giá trị
5 4
Lời giải
Gọi mảnh đất hình chữ nhật là ABCD. Ta đếm từng mặt theo trật tự tuỳ ý, chẳng hạn:
1. Đếm số khối trên hai chiều dài AB và DC.
2. Đếm số khối trên hai chiều rộng AD và BC.
3. Đếm số khối nhìn thấy theo chiều ngang giữa các hàng.
4. Đếm số khối nhìn thấy theo chiều dọc giữa các cột.
5. Đếm số khối trên mặt.
Trong chương trình SONCOT.PAS dưới đây thủ tục DOS sẽ đọc dữ liệu từ tệp COT.INT vào mảng a. Thủ tục Xem hiển thị giá trị của mảng a trên màn hình. Thủ tục Dem thực hiện giải thuật 5 bước nói trên.
