- Ta có n mẫu máu. Mỗi mẫu máu thuộc về một trong m nhóm máu. (Ta không biết chính xác m là bao nhiêu, và m không nhất thiết phải là hằng số.) Có một thiết bị mà nếu bỏ vào đó hai giọt máu từ hai mẫu máu khác nhau thì thiết bị sẽ cho biết hai mẫu máu có cùng nhóm máu hay không. Nếu bỏ vào thiết bị này hơn hai giọt máu thì câu trả lời không đáng tin cậy nữa.
Ta muốn trả lời câu hỏi sau đây: có hay không hơn n/2 mẫu máu thuộc về cùng một nhóm máu. Dùng thiết bị trên để thử, làm thế nào để trả lời câu hỏi này với tổng số ít nhất các phép thử? (Chỉ cần ít nhất về mặt asymptotic là được.) Ví dụ: cách dễ nhất là thử tất cả các cặp mẫu máu nhưng như vậy cần dùng đến
phép thử.
Ngoài ra, ta cũng giả sử rằng mỗi mẫu máu có khá nhiều giọt.
6 Comments
Số lần thử tối đa: [(n+1)/2]*[(n+1)/2]
[(n+1)/2]*[(n+1)/2] thì vẫn là
thôi.
Em nghi la can O(n/2) phep thu.
Hi Nguyên:
có thể làm được, hơi mẹo một chút.
Ta chia bài toán thành 2 bước, bước 1 là thử tìm mẫu máu duy nhất “có thể” xuất hiện hơn n/2 lần trong dãy, bước 2 đơn giản chỉ là kiểm tra xem mẫu đó có thực sự xuất hiện > n/2 lần ko ?
Bước 1:
Chia n mẫu ban đầu thành n/2 cặp, rồi so sánh các cặp với nhau. Cặp nào ko giống nhau thì loại ra luôn, ko xét nữa, chỉ xét những cặp giống nhau thôi.
Trong trường hợp ko có cặp giống nhau nào thì có thế kết luận là ko thể có > n/2 mẫu giống nhau đc.
Trong trường hợp tìm được k>0 cặp giống nhau, thì nếu thực sự có > n/2 mẫu giống nhau, thì có hơn k/2 cặp giống nhau là mẫu đó. Do đó ta có thể thu nhỏ bài toàn về tìm xem trong k cặp, có hơn k/2 cặp có cùng mẫu máu ko ? Tiếp tục tìm đến khi còn 1 cặp thì dừng. Trả về mẫu máu duy nhất còn lại.
Bước 2:
Dựa vào mẫu máu kết quả của bước 1, dùng n bước thử để kiểm tra xem nó có xuất hiện đúng n/2 lần ko ?.
Độ phức tạp của bước 1 là O(n) vì sau mỗi lần chia cặp + thử, k bài toán là O(n)
Trang2: nice solution!