Hãy đặt bút trước khi đặt tay vào bàn phím
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 (104.53 KB, 6 trang )
Hãy đặt bút trước khi đặt tay vào bàn phím
Nguyễn Xuân Huy
Bài toán 1 . (Cắt bánh,phỏng theo bài thi học sinh giỏi chuyên tin toàn quốc, khối B) Bà
Tiên cho hai chị em Quyên và Phong mộtcái bánh hình chữ nhật được ghép bằng nhiều
mảnh hình vuông đơn vị. Biết kíchthước cái bánh là n x m đơn vị. Chị Quyên cắt bánh theo
đườngchéo. Hỏi có bao nhiêu ô bánh bị cắt, nghĩa là nhát cắt đi qua ít nhất hai điểmcủa ô
(xem hình 1).
Chúng ta đã gặpbài toán này trong bài 'Giải thuậtBresenham' đăng trong TH&NT số 3(6)
năm 2000. Nhiều bạn đọc nói với tôirằng hình như có thể lập công thức để tính số ô vuông
đơn vị bị đường chéo cắtnhưng... vấn đề có thể hơi bị khó. Chúng ta thử xem sao.
Gọi f(m,n) làcông thức tính số ô bị cắt trong hình chữ nhật kích thước n x m đơn vị. Đầu
tiên ta nhận thấy rằngcông thức này phải đối xứng, tức là f(m,n) = f(n,m). Một công thức
hai biến xvà y, f(x,y) được gọi là đối xứng nếudạng của nó không thay đổi khi ta đổi chỗ
các biến x và y cho nhau, thí dụ côngthức f(x,y) = x
2
+ y
2
- 3xy là đối xứng vì f(y,x) = y
2
+
x
2
- 3yx = x
2
+ y
2
- 3xy, còn công thứcf(x,y) = x
2
+ y
2
- 3xy + y thì không.
Ta cũng thấydf(n,m)=f(dn,dm) vì theo định lý về các đoạn thẳng tỷ lệ ta có m:dm=n:dn do
đósố ô bị cắt trong hình chữ nhật kích thước dn x dm sẽ gấp d lần số ô bị cắttrong hình chữ
nhật kích thước n x m (xem hình 2).
Giả sử n m và d làước chung lớn nhất của n và m. Đặt n' = n:d và m' = m:d. Ta xét hình
chữ nhậtABCD kích thước n' x m' ô vuông đơn vị có các tọa độ đỉnh mang các giá
trịnguyên. Ta thấy vì n' và m' là hai số nguyên tố cùng nhau nên trong tất cả cácđiểm có tọa
độ nguyên của lưới ô vuông n' x m' chỉ có duy nhất hai điểm D và Bnằm trên đường chéo
DB. Nếu đi theo đường chéo từ D đến B ta sẽ thấy đường chéocắt qua n'-1 đường thẳng
đứng của lưới (không tính 2 cạnh biên). Như vậy DB cắtít nhất là n ô vuông đơn vị. Tương
tự, ta cũng thấy đường chéo DB phảicắt m'-1 đường nằm ngang của lưới (không tính 2
cạnh biên). Mỗi lần cắt qua mộtcạnh ngang đường chéo DB lại cắt thêm 1 ô đơn vị nữa.
Vậy số ô bị cắt thêm sẽlà m'-1. Tổng cộng đường chéo DB của hình chữ nhật ABCD kích
thước n' x m' cắtn'+m'-1. Tổng hợp lại ta có f(n,m) = df(n',m') = d(n'+m'-1), trong đó d
=ucln(n,m). Để ý rằng dn'=n và dm'=m, ta có f(n,m) = n+m-ucln(n,m). Đây chính làcông
thức cần tìm.
Chương trình CAT.PAS dưới đây triển khai hai hàm:Hàm Cat(n,m) như đã giới thiệu
trong bài 'Giảithuật Bresenham' đăng trong TH&NT số 3(6) năm 2000; hàm f(n,m)
theocông thức vừa tìm. Thủ tục Test tính và so sánh trị của hai hàm trên với cáccặp n và m
biến thiên trong khoảng 1..50. Nếu phát hiện lỗi thì chương trình sẽthông báo.
(* CAT.Pá *)
Uses crt;
(*------------------------------------
Xem lai bai Giai thuat Bresenham
trong TH&NT so 3(6) nam 2000
-------------------------------------*)
Function Cat(n, m: word): word;
var t, i,d: word;
Begin
if n > mthen
begin
t := m;
m := n;
n := t;
end;
t := 0; d:= m;
for i := 1to m do
begin
t := t +n;
if t >m then inc(d);
if t>= m then t := t - m;
end;
Cat := d;
End;
Function ucln(n, m: word): word;
var r:word;
Begin
while m<> 0 do
begin
r:= nmod m;
n:=m;
m:=r;
end;
ucln:=n;
End;
(*------------------------------------
Tinh theo cong thuc moi
-------------------------------------*)
Function f(n, m: word): word;
Begin
f :=n+m-ucln(m,n);
End;
Procedure Test;
var n, m:word;
Begin
clrscr;
for n:=1 to50 do
for m :=1to 50 do
begin
write(m,'',n,' ');
ifcat(m,n) <> f(m,n) then
begin
writeln('saí);
readln;
end
elsewriteln('Dung');
end;
End;
BEGIN
Test;
END.
Lời bình: Nếu phương ánmới này tốt hơn phương án cũ thì tại sao người ta lại hay sử
dụng thuật toánBresnham? Câu trả lời khá đơn giản: vì thuật toán Bresnham giải trình
được cácbước tính còn thuật toán cải tiến nói trên, tức là hàm f chỉ cho kết quả cuốicùng.
Bạn thử thêm yêu cầu "hãy liệtkê các ô bị cắt" thì sẽ thấy ngay sự tiện lợi của thuật toán
Bresnham.Trong đồ họa máy tính khi phải vẽ các đường thẳng người ta phải xác định
từngđiểm nằm trên đường thẳng. Nếu coi mỗi điểm ứng với một ô vuông đơn vị thì
việcxác định các ô bị cắt sẽ chính là việc xác định các điểm nằm trên đường thẳngcần vẽ.
Trong một số tớichúng ta sẽ bàn luận về lời giải cho bài toán sau đây:
Bài toán 2 . (Xanh, đỏ, tím,vàng)
Cho 4 thùng, mỗi thùng đựng các đoạn thẳng thuộc mộttrong 4 màu là xanh, đỏ, tím và
vàng. Các đoạn thẳng cùng màu thì dài bằngnhau. Biết chiều dài của mỗi loại đoạn thẳng
là lx, ld, lt và lv theo trật tựlần lượt của các màu xanh, đỏ, tím và vàng. Cần chọn ra không
quá n đoạn thẳngđể xếp thành cạnh của một hình chữ nhật có màu lần lượt là cạnh xanh,
cạnh đỏ,cạnh tím và cạnh vàng sao cho diện tích của hình là lớn nhất.
Dữ liệu vào: Tệp văn bản XDTV.INP gồm 5 số tự nhiêncách nhau bởi dấu cách: n lx ld lt
lv.
Dữ liệu ra: Tệp văn bản chứa 6 số tự nhiên cách nhaubởi dấu cách: m dx đ dt dv s biểu thị
các giá trị sau:
m: tổng số đoạn thẳng cần chọn
dx: số đoạn thẳng màu xanh
đ: số đoạn thẳng màu đỏ
