Bài toán khối bê tông
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (89.02 KB, 10 trang )
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
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
Lần thứ sáu: chuyển khối 1 từ giá đỡ x vào vị trí 4:(3,4,5,1,2), x = 0.
Dễ thấy việc làm lý tưởng là, trừ khối số 1 bị chuyển 2lần, với các khối còn lại ta phải săn
sóc sao cho mỗi khối chỉ phải chuyển 1lần đúng vào vị trí cần đặt. Cụ thể là nếu vị trí thứ i
đang trống thì phảichuyển khối bê tông từ vị trí ((i+k-1) mod n)+1 vào đó. Nếu thử làm với
thí dụn=6, k = 2 ta sẽ thấy hình như mọi việc không suôn xẻ như lần trước. Này nhé,
Thí dụ 2: Cấu hình ban đầu:(1,2,3,4,5,6) ; n = 6, k = 2
Lần thứ nhất: chuyển khối 1 ra giá đỡ x: (0,2,3,4,5,6), x= 1
Lần thứ hai: chuyển khối 3 vào vị trí 1: (3,2,0,4,5,6), x= 1
Lần thứ ba: chuyển khối 5 vào vị trí 3: (3,2,5,4,0,6), x =1
Đến đây ta thấy chỉ có thể chuyển khối 1 vào vị trí 5:
Lần thứ tư: chuyển khối 1 vào vị trí 5: (3,2,5,4,1,6), x =0
Bây giờ ta phải xử lý khối 2:
Lần thứ năm: chuyển khối 2 ra giá đỡ x: (3,0,5,4,1,6), x =2
Lần thứ sáu: chuyển khối 4 vào vị trí 2: (3,2,5,0,1,6), x= 2
Lần thứ bảy: chuyển khối 6 vào vị trí 4: (3,2,5,6,1,0), x= 2
Lần thứ tám: chuyển khối 2 từ giá đỡ x vào vị trí 4:(3,4,5,6,1,2), x = 0.
Như vậy có trường hợp đòi hỏi n+1 phép chuyển, có trườnghợp lại đòi hỏi n+2 phép
chuyển. Thuật toán tổng quát sẽ ra sao
Nếu viết dữ liệu theo dạng vòng tròn bạn sẽ phát hiện rarằng sau m lần chuyển thì ta phải
đưa tấm bê tông từ giá đỡ x vào vị trí cầnthiết, trong đó m = n div d và d chính là ước
chung lớn nhất của n và k. Ta gọichu trình gồm m lần chuyển này là một vòng vì lần
chuyển đầu tiên của vòng làmang tấm bê tông từ vị trí i ra giá đỡ và lần cuối cùng của
vòng là mang tấm bêtông từ giá đỡ x vào vị trí thích hợp đang trống. Số vòng chuyển sẽ là
d. Mỗivòng ta cần m+1 lần chuyển, do đó số lần chuyển tổng cộng sẽ là d*(m+1) = d*m
+d = n+d < 3*n.
Thuật toán này tốt hơn thuật toán đối xứng mặc dù nó sẽphải sử dụng thêm vài biến phụ
(không phải giá đỡ phụ, vì các biến phụ này chỉdùng để đếm các bước trong vòng lặp).
Với thí dụ 1, n = 5, k = 2 ta có d = UCLN(5,2) = 1. Do đó m= 5 div 1 = 5. Ta chỉ cần một
vòng với n+1 lần chuyển.
Với thí dụ 2, n = 6, k = 2 ta có d = UCLN(6,2) = 2. Do đóm = 6 div 2 = 3. Ta cần hai vòng
với n+2 lần chuyển.
Thuật toán chuyển vòng khi đó sẽ như sau:
procedureChuyenVong;
varx,i,j,u,v,m,d: word;
begin
d:= ucln(n,k);
m:= n div d;
fori := 1 to d do
begin
chuyen(x,a[i]);
u:=i;
for j := 1 to m-1 do
begin
v := ((ưk-1) mod n)+1;
chuyen(a[u],a[v]);
u := v;
end;
chuyen(a[u],x);
end;
end;
Thuật toán sử dụng 7 biến phụ, trong đó biến x đóng vaitrò như một giá đỡ. Giả sử bạn
phải lập trình để điều khiển một cánh tay máy dichuyển các khối bê tông thì việc giảm số
lần gọi các thủ tục chuyển với thờigian 20 giờ là rất đáng quan tâm.
Chương trình dưới đây chứa 3 test mô phỏng cho 3 thuậttoán chuyển khác nhau:
Test 1 sử dụng giải thuật tự nhiên với k*(n+1) lần chuyển,
Test 2 sử dụng giải thuật đối xứng gương với 3*n lầnchuyển.
Test 3 sử dụng giải thuật chuyển vòng với n+UCLN(n,k) lầnchuyển.
Một lần nữa xin hoan nghênh giải pháp xuất sắc của bạn BảoGiang.
(* CHUYEN.PAS *)
uses crt;
const
N = 48;
K = 10;
w = 20;
bl = ' ';
type
Mang = array[1..N]of word;
var
Nhip: longintabsolute $0000:$046c;
a: Mang;
t1,t2: longint;
procedure Gen;
var i: word;
begin
for i := 1 to N do
a[i] := i;
end;
procedure Xem;
var i: word;
begin
for i := 1 to N do
write(a[i],bl);
writeln;
end;
{ Chuyen khoi be tong tuy vao x. Co thoi gian tre }
procedure Chuyen(varx,y: word);
begin
x:=y;
