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);
x:=y;
y:=0;
Delay(w);
end;
Cóthể minh họa ý tưởng của bạn Bảo Giang như sau: Giả sử ta có đường băng gồm 5khối bê tông và ta cần chuyển 2 khối 1 và 2 về cuối đường. Thay vì 3*5=15 lầnchuyển như thuật toán đối xứng ta thực hiện 6 lần chuyển như sau:
Thí dụ 1: Cấu hình ban đầu: (1,2,3,4,5); n = 5, k = 2
Lần thứ nhất: chuyển khối 1 ra giá đỡ x: (0,2,3,4,5), x =1
Lần thứ hai: chuyển khối 3 vào vị trí 1: (3,2,0,4,5), x =1
Lần thứ ba: chuyển khối 5 vào vị trí 3: (3,2,5,4,0), x = 1
Lần thứ tư: chuyển khối 2 vào vị trí 5: (3,0,5,4,2), x = 1
Lần thứ năm: chuyển khối 4 vào vị trí 2: (3,4,5,0,2), x =1
