Bước tới nội dung

Bài toán Josephus

Bách khoa toàn thư mở Wikipedia

Bài toán Josephus, hay hoán vị Josephus, là một câu hỏi toán lý thuyết trong khoa học máy tính và toán học.

Có người đang đứng thành một vòng tròn. Và, bắt đầu từ vị trí , bài toán sẽ đếm từ người đó theo một hướng nhất định. Sau khi có người được bỏ qua, người thứ sẽ bị xử tử. Quy luật sẽ lặp đi lặp lại với số người còn lại trong vòng tròn đó, bắt đầu với người tiếp theo, theo cùng một chiều quay, và bỏ qua cùng số người p cho đến khi nào chỉ còn một người sống sót.

Điều cốt lõi của bài toán, chính là tìm ra vị trí trong vòng tròn để có thể là người sống sót.

Lịch sử

[sửa | sửa mã nguồn]

Bài toán được đặt tên theo Flavius Josephus, một sử gia người Do Thái sinh sống vào thế kỷ thứ nhất. Theo bản tường trình của Josephus về cuộc bao vây Yodfat, ông và 40 người lính bị những người lính La mã vây trong một hang động. Họ thà tự tử còn hơn là bị bắt giữ và giải quyết cách tự tử bằng cách rút thăm. Josephus tuyên bố rằng bằng may mắn hoặc có thể là do bàn tay của Thiên Chúa, ông và một người khác còn sống cho đến cuối cùng và đầu hàng người La Mã thay vì tự tử. Đây là câu chuyện được đưa ra trong Sách 3, chương 8, phần 7 của Chiến tranh Do Thái của Josephus (viết về bản thân mình với ngôi thứ ba):bài toán này được sử dụng với mọi cấp độ

Tham khảo

[sửa | sửa mã nguồn]

Sách tham khảo

[sửa | sửa mã nguồn]
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001). “Chapter 14: Augmenting Data Structures”. Introduction to Algorithms . MIT Press and McGraw-Hill. tr. 318. ISBN 0-262-03293-7.Quản lý CS1: nhiều tên: danh sách tác giả (liên kết)
  • Dowdy, James; Mays, Michael E. (1989), “Josephus Permutations”, Journal of Combinatorial Mathematics and Combinatorial Computing, 6: 125–130

Liên kết ngoài

[sửa | sửa mã nguồn]
Lấy từ “https://vi.wikipedia.org/w/index.php?title=Bài_toán_Josephus&oldid=72211386”