Tài liệu giải thuật BRESENHAM
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 (87.11 KB, 7 trang )
Giải thuật BRESENHAM
Nguyễn Xuân Huy
Tư tưởng.
Trong lập trình, đôi khi chúng taphải làm việc với các số thực. Tính toán với các số thực có
hai điều phiền toái.Thứ nhất, do biểu diễn của chúng tốn nhiều đơn vị lưu trữ nên máy tính
xử lýcác số thực lâu hơn so với các số nguyên. Thứ hai, phép chia số thực trong máytính có
thể cho các kết quả không chính xác. Bạn biết chắc rằng 1/3 + 2/3 =1,trong khi máy tính lại
cho bạn kết quả 1/3 + 2/3 = 0.33 + 0.66 = 0.99. Bresenham tìm cách tránh các phép chia số
thực thông qua việc tích luỹ dần các đại lượng tỷ lệ và nguyên hóa chúng sau mỗi bước xử
lý. Chính vì vậy mà giải thuật này tỏ ra đặc biệt hữu hiệu trongcác bài toán có liên quan
đến các phép chia tỷ lệ.
Bài toán 1 (Chia kẹo) BàTiên cho hai chị em Quyên và Phong một đống kẹo. Quyên muốn
chia cho em theo tỷlệ: chị 5 phần, em 9 phần. Bạn hãy giúp Quyên chia kẹo chính xác đến
mức tối đamà không được đếm trước số kẹo.?
Ta hãy khoan nói đến việc lậptrình để tập trung vào việc chia kẹo cho chính xác.
Lưu ý rằng, ngay cả trong trườnghợp biết trước số kẹo, chúng ta cũng có thể chia không
công bằng. Giả dụ, bàTiên cho hai chị em 20 cáI kẹo. Vì chị được 5 phần, em được 9 phần
nên tổngcộng có 14 phần cả thảy. Vị chi mỗi phần có 20: 14 = 1 cái kẹo. Do đó Quyên
sẽđược nhận 5 cái, Phong được 9 cái. Số kẹo còn dư sẽ là 20 - ( 5+9 ) = 6. Tachia 6 cái kẹo
dư này ra sao đây?
Chúng ta sẽ giải bài toán trên bằngthuật giải Bresenham.
Tỷ lệ giữa chị và em là 5 : 9,chúng ta nhận xét sau:
Nếu em nhận được 1 cái kẹo thìchị nhận được 5/ 9 cái.
Nếu em nhận được 2 cái kẹo thìchị nhận được 10/ 9 = 1 + 1/ 9 cái.
Nếu em nhận được 3 cái kẹo thìchị?nhận được? 1 + 6/ 9 cái.
Nếu em nhận được 4 cái kẹo thìchị nhận được? 1 + 11/ 9 cái = 2 + 2/ 9 cái
Nếu em nhận được 5 cái kẹo thìchị nhận được? 2 + 7/ 9 cái
Nếu em nhận được 6 cái kẹo thìchị nhận được 2 + 12/ 9 = 3 + 3/ 9 cái
Nếu em nhận được 7 cái kẹo thìchị nhận được 3 + 8/9 cái
Nếu em nhận được 8 cái kẹo thìchị nhận được? 3 + 13/9 cái = 4 + 4/ 9 cái
Nếu em nhận được 9 cái kẹo thìchị nhận được 4 + 9/ 9 cái = 5 cái
Nếu em nhận được 10 cái kẹo thìchị nhận được 5 + 5/ 9 cái
Nếu em nhận được 11 cái kẹo thìchị nhận được 5 + 11/ 9 cái = 6 + 2/ 9 cái
Nếu em nhận được 12 cái kẹo thìchị nhận được 6 + 7/ 9 cái
Nếu em nhận được 13 cái kẹo thìchị nhận được 6 + 12/ 9 cái = 7 + 3/ 9 cái
Tổng số kẹo là 20 do đó ta chiacho em 13 cái và chị nhận 7 cái. Phần thiệt của chị là 3/ 9
cái kẹo là khôngđáng kể.
Ta thử tổng quát hóa lời giải trêntrong trường hợp không biết trước tổng số kẹo.
Giả sử tỷ lệ kẹo giữa chị và em làn: m, trong đó n <= m.
Nếu không biết trước tổng số kẹo,ta cũng theo phương pháp trên, nghĩa là mỗi khi chia cho
em một cái kẹo, ta tạmghi nhận chia thêm cho chị n/m cái. Vì đại lượng m không thay đổi
trong suốtquá trình chia cho nên ta chỉ cần tích luỹ tử số cho chị. Ta gọi đại lượng tíchlũy
tử số này là t. Giá trị ban đầu của t là 0. Mỗi khi em nhận được một chiếckẹo ta cho t tăng
thêm n phần trong số m phần của đơn vị. Khi t >= m, tacó phân số t/ m lớn hơn hoặc bằng
đơn vị. Lúc này ta chia cho chị một chiếc kẹovà chỉnh lại t:= t - m , vì t/ m = 1 + ( t - m ) /
m. Quá trình chia như trênsẽ kết thúc khi số kẹo đã được chia hết.
Đến đây chúng ta đã có thể vậndụng giải thuật Bresenham để giải bài toán lý thú sau.
Bài toán 2. (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ột cá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ích thước cái bánh là n x m đơn vị. Chị Quyên cắt bánh theo
đường chéo.Hỏi có bao nhiêu ô bánh bị cắt, nghĩa là nhát cắt đi qua hai điểm của ô
( xemhình 1 ).
Đếm số ô bị cắt trong cái bánh 5 x 9. Các? dòng (1) và (2) cho biết sự biến thiên của tử số
t. Dòng (3) cho biếtsố ô bị cắt được tăng thêm nếu:
t ≤ m thì thêm 1; ngược lại khit > m thì thêm 2. Dòng (2) là kết quả chỉnh lại t khi t ≥ m.
Có 13 ôbánh được cắt qua được đánh số trong hình.
Nói vắn tắt, bài toán 2 yêu cầuđếm số ô vuông đơn vị bị đường chéo của hình chữ nhật cắt
qua. Trong thí dụ ởhình 1, kết quả là 13 ô bị cắt. Tuy nhiên với các giá trị n và m lớn ,
chúngta khó có thể đếm bằng mắt được.
Dễ thấy tỷ lệ giữa hai cạnh củahình chữ nhật sẽ là n: m. Ta cần xác định chiều dài của
hình, tức là cạnh lớnhơn ( ứng với phần của em trong bài toán chia kẹo ). Giả sử n < m.
Chúngta duyệt dần từng điểm i =1..m theo nghĩa chia cho em một chiếc kẹo. Mi lần
nhưvậy chị sẽ nhận được thêm n phần trong số m phần của đơn vị... Nếu t ≤ m thìchỉ có
đúng 1 ô bi dao cắt qua. Ngược lại, khi t > m sẽ có đúng 2 ô bị daocắt qua. Tóm lại, với
mỗi i= i.. m luôn luôn có một ô bị dao cắt qua. Ta dùngmột biến d để đếm số lượng các ô
bị cắt. Giá trị của d được khởi trị là m. Khit > m ta tăng d thêm 1 đơn vị. Ta nhớ chỉnh lại
giá trị của t trong cả haitrường hợp: khi t = m và khi t > m.
Gọi Cat (n, m) là hàm cho ra số ôbị đường chéo của hình chữ nhật kích thước n x m cắt. Sơ
đồ tính toán chohàm Cat khi đó sẽ như sau:
Sơ đồ cho hàm Cat
- Hoán vị, nếu cần để cho n <>
- Khởi trị:
+ Con đếm d:= m, vì chắcchắn có ít nhất là m ô bị cắt;
+ Giá? trị của tử số t:= 0;
- Tính với mỗi i = 1..m
+ Tăng thêm t một lượng m
+ Nếu t > m tăng d thêm 1đơn vị
+ Nếu t >= m chỉnh lạit:= t - m
Hàm Cat
Function Cat (n, m: word): word;
Var t, i, d : word;
Begin
If n > m then
Begin
t:= m;
m:= n;
n:= t;
End;
t:= 0; d:=m;
for i:= 1 to m do
begin
t:=t + n;
if t > m then inc (d);
if t>= m then t:= t - m;
end;
Cat:=d;
End;
Chương trình Pascal: CATBANH.PAS
Uses crt;
Function Cat (n, m: word): word;
Var t, i, d: word;
Begin
If n > m then
Begin
T:= m;
M:= n;
N:= t;
End;
T:=0; d:=m;
For i:=1 to m do
Begin
T:= t + n;
If t > m then inc (d)
If t >= m then t:= t - m;
End;
Cat:= d;
End;
Procedure Test;
Var n, m : word;
Begin
Clrscr;
Repeat
Writeln;
Write( Nap n, m:);
Readln(n, m);
If (n=0) or (m=0) then exit;
Writeln (Cat (n, m));
Until false;
End;
BEGIN
Test;
END.
