1) Phương pháp dấu dữ liệu : Bít đầu tiên của D được dấu vào k điểm ảnh đầu
tiên của F (k là khóa, k lẻ), bít thứ hai của D được dấu vào k điểm ảnh tiếp theo
của F,...
Giả sử chúng ta cần dấu bít b là bít thứ i (1<=i<=L) của xâu D vào trong ảnh
F, ta dùng phương pháp như sau :
Bước 1: Đọc liên tiếp k điểm ảnh tiếp theo của ảnh F và gọi là f.
Bước 2: Ký hiệu sum(f) là tổng số bít có giá trị 1 có trong f.
Bước 3:Dấu dữ liệu bít b trong f bằng cách sửa bít trong f :
Cơ sở để sửa bít trong f là so sánh tính chẵn lẻ giữa bít b với sum(f):
+Nếu b và sum(f) cùng chẵn (có phần dư khi chia cho 2 bằng 0) hoặc
cùng lẻ (có phần dư khi chia cho 2 bằng 1) thì không sửa bít nào trong f.
+Nếu b và sum(f) không cùng chẵn hoặc không cùng lẻ thì ta sửa đúng 1
bít trong f để sum(f) và b có cùng chẵn hoặc cùng lẻ. Việc sửa tiến hành như
sau:
Sửa bít cuối cùng của đoạn cùng màu lớn nhất ở trong f.
Ví dụ :
- Cho bít b= 0 và khóa k= 9 :
a) Giả sử f=110100010 => sum(f) = 4
b và sum (f) cùng chẵn. Do đó không sửa bít nào cả (xem như đã dấu b
vào f).
b) Giả sử f=110111011 => sum(f) = 7
b và sum (f) không cùng chẵn hoặc lẻ . Do đó, người ta sửa 1 bít trong
f:
Sửa bít cuối cùng của đoạn cùng màu lớn nhất ở trong f là 111 thành
Bạn đang xem 1) - KỲ THI CHỌN HỌC SINH GIỎI LỚP 12 Môn: Tin học