Bài toán khối bê tông

Có thể nhanh hơn không?

Nguyễn Xuân Huy

Trong bài ABBA hay phépđối xứng gương và các thao tác đăng trong Tin học và nhà

trường số 1 và số3, 1999 có nói đến hai thuật toán giải bài chuyển k khối bê tông từ đầu

đườngbăng gồm n khối về cuối đường băng chỉ được phép dùng 1 biến phụ để đặt tạm

cáckhối bê tông lấy ra khỏi đường băng. Một thuật toán chuyển tự nhiên k*(n+1)phép

chuyển, một thuật toán chuyển nhanh có ứng dụng phương pháp đối xứng gươngvà dùng

3*n phép chuyển và 1 biến phụ.

Sau đó bạn Nguyễn Xuân Tài,Lớp 11 Chuyên Toán, Nghệ An có cung cấp thuật toán sử

dụng mảng phụ và gọi thủtục move để tăng tốc độ tính toán. Sở dĩ thủ tục move hoạt động

rất nhanh vì nóhoạt động ở mức thấp, thao tác trực tiếp trên RAM và bỏ qua các phép kiểm

tragiới hạn của mảng.

Tiếp đến là bạn Nguyễn BảoGiang, lớp 12 chuyên Lý, THPT năng khiếu, Hà Tĩnh có đề

xuất một ý tưởng, tạmgọi là chuyển vòng, theo chúng tôi là một cải tiến đáng kể, đặc biệt

là trong trườnghợp phép chuyển mỗi khối bê tông đòi hỏi những tốn kém về thời gian và

côngsức.

Trước hết ta nhắc lại bài toán và những đòi hỏi bổsung cho thêm ý nghĩa như sau.

Bàitoán (chuyển các khối bê tông) Chomột đường băng tạo bởi gồm n khối bê tông. Cần

chuyển k khối bê tông từ đầu vềcuối đường băng theo những yêu cầu sau:

- Mỗi lần chỉ cóthể chuyển một khối bê tông từ vị trí này đến vị trí khác.

- Được phép sửdụng một giá đỡ phụ để đặt tạm một khối bê tông.

- Không được đặtcác khối bê tông đè lên nhau.

- Thời gian đểchuyển một khối bê tông là 20 giờ.

- Sau khi côngviệc hoàn tất đường băng vẫn chiếm đúng vị trí cũ trên mặt đất chứ không

bịtịnh tiến đến vị trí khác.

Trướchết ta viết thủ tục mô phỏng chuyển một khối bê tông từ vị trí y đến vị trí x vớithời

gian 20 giờ. Lưu ý rằng sau khi chuyển, khối bê tông không còn ở vị trí ynữa cho nên ta

phải đặt y:=0. Thời gian chuyển được mô phỏng qua thủ tục delay(w),với w = 20.

procedure Chuyen(var x,y: word);

begin