Các câu hỏi phỏng vấn [27]
Ngô Quang Hưng | 27 tháng 04, 2007 | 
Bản để in
- Có một số
(
lớn tùy ý) các anh lính đứng thành vòng tròn, cầm súng hướng mặt ra ngoài. Mỗi người có bộ nhớ kích thước bằng hằng số (nghĩa là memory space = O(1)) và chỉ có thể trao đổi thông tin với người đứng bên trái và người đứng bên phải. Giả sử thời gian được chia thành các thời điểm rời rạc: 0, 1, 2, 3, … Tại thời điểm số 0, ông tướng vỗ vai một anh lính nào đó và hạ lệnh “bắt đầu”.
Các anh lính phải trao đổi thông tin thế nào để tất cả bóp cò cùng một lúc?
- Có N anh cướp biển sắp bị xử chém. Họ xếp thành một hàng dài. Mỗi người đội một chiếc nón, xanh hoặc đỏ. Cướp biển số 1 chỉ thấy nón (và màu nón) của cướp biển số 2, 3, … N; cướp biển số 2 chỉ thấy nón của số 3, 4, … N; vân vân. Dĩ nhiên, vì thế mỗi cướp biển không biết màu nón mình đang đội và màu nón của các cướp biển đứng trước mình trong hàng.
Đao phủ bắt đầu chém từng cướp biển một, từ số 1 đến số N. Tuy nhiên, trước khi chém mỗi cướp biển thì đao phủ cho hắn một cơ hội: đoán màu nón của mình. Nếu nói đúng màu nón thì được tha. Tất cả các cướp biển đều nghe thấy nhau trả lời, nhưng không biết ai bị chém ai không.
Trước hôm ra xử bắn, bọn cướp biển họp lại và tìm một thuật toán trả lời để cho tổng số cướp biển bị chém là ít nhất trong trường hợp tệ nhất (in the worst case). Ví dụ: nếu cướp biển số 2k-1 trả lời bằng màu nón của cướp biển 2k, và cướp biển 2k lập lại câu trả lời này, thì tệ nhất cũng chỉ có một nửa số cướp biển bị chém.
Nếu bạn là cướp biển thì bạn thiết kế thuật toán thế nào?
77. Cướp biển chỉ cần dùng dùng *1-bit* error detection algorithm. Hi sinh thằng cướp đầu tiên để tính even parity với cặp (Xanh, Đỏ) ~ (0, 1)
77. Chả hiểu anh instcode nói gì nên em đưa cách của em, chết cũng nhiều nhưng sống được hơn một nửa.
Với N=1 thì cơ hội sống là 50%.
Với N=2 thì dùng cách của đề bài.
Với N>=3 Khi đó sẽ chia theo nhóm, mỗi nhóm 3 người. Dư bao nhiêu (1 hay 2) thì đưa về trên.
Xét trong từng nhóm 3 người: (1) (2) (3)
Người (1) chịu hi sinh *_*, nhìn (2) và (3), nếu 2 thằng kia khác màu nhau thì nói là đỏ, nếu giống thì nói là xanh.
Như thế, thằng (2) nhìn thằng đỏ mà đoán cái mình và thằng (3) nghe thằng (2) mà đoán cái của mình.
76. Cháu không hiểu đề lắm. Cái ô nhớ là hằng số đó có thể lưu trữ cái gì? Có phải anh lính này nói cho anh lính kia thời gian để bắn?
76. Gia su x la anh linh bi ong tuong vo vai. Bai toan dc giai neu tat ca anh linh deu biet vi tri tuong doi cua minh so voi anh linh x (goi p(l) la khoang cach cua anh linh l so voi x theo chieu kim dong ho). Vi khi do anh linh x se truyen tin hieu khai hoa toi nguoi ben trai, nguoi do lai tiep tuc truyen tin hieu sang nguoi ben trai, …. de cung nhau khai hoa luc 2^n-p(l) ke tu khi nhan dc tin hieu khai hoa tu x.
De l biet duoc p(l), l truyen tin hieu theo chieu kim dong ho toi x, khi x nhan dc se truyen tin hieu tro lai cho l. Thoi gian tu khi l nhan duoc tin hieu hoi am = 2 * p(l).
Khong biet co cach nao don gian hon khong.
77. Dùng 1 và 0 để mã hoá 2 màu. Người đầu tiên nói tổng số màu (0 or 1 in binary field) của những người đứng trước. Những người tiếp theo dựa theo tổng số màu hiện tại (phải nhớ màu những người trước nói) và tổng số màu những người đứng trước mình (tự đếm) để tính ra màu của mình. Kết quả tệ nhất là N-1.
Chắc đây cũng là cách instcode nói.
Các bác dùng từ “mã hoá”, “0 và 1″ nghe nó Tin học quá, mấy em cướp biển chắc không hiểu đâu quanh năm đi cướp không có online đâu. Em nói lại đơn giản thế này (chắc cũng giống cách của ducha thôi!) em đầu tiên sẽ đếm số mũ xanh đứng trước mình nếu là số chẵn sẽ nói mũ mình là xanh, ngược lại nói là đỏ, em thứ 2 sau khi biết màu của em thứ nhất xong sẽ đếm số mũ xanh của những người đứng trước mình để biết được mũ mình đang đội là màu gì, em thứ 3 biết được màu mũ của em thứ 2 và thứ nhất xong sẽ đếm số mũ xanh còn lại để biết được màu mũ của mình…và như vậy tồi nhất chỉ hi sinh em đầu tiên thôi!
Trình bày như thế này chắc mấy em cướp biển dễ hiểu hơn các bác nhỉ!:D
Phải nói là anh Hưng có câu hỏi hay quá!Em nghĩ trong các cuộc thi học sinh giỏi nên dùng những dạng câu hỏi thế này.
Hehe, bây giờ mới thực sự hiểu cách giải đó, đúng là chỉ ngỏm có 1 người