Tài liệu: Docs.vn Hỗ trợ : Y!M minhu888
Trường Đại học Công Nghệ Thông Tin
Đại học Quốc gia Hồ Chí Minh
------------------
Bộ môn:
Phương pháp luận sáng tạo khoa học
Bài luận :
Trình bày về nội dung vận dụng những kiến
thức về phương pháp luận, sáng tạo để giải
quyết một vấn đề nào đó trong tin học.
GVHD: GS.TSKH Hoàng Văn Kiếm Sinh viên: Nghiêm Xuân Hiệp
MSSV: 06520155
Khoa: MMT&TT 01
Tài liệu: Docs.vn Hỗ trợ : Y!M minhu888
I. Bài toán :
Trong bài toán Josephus, một nhóm binh sĩ bị kẻ thù bao vây và một
binh sĩ được chọn để đi cầu cứu. Việc chọn thực hiện theo cách sau: Một số
nguyên n và một binh sĩ được chọn một cách ngẫu nhiên. Các binh sĩ được
sắp xếp theo vòng tròn, và họ đếm bắt đầu từ binh sĩ được chọn ngẫu nhiên.
Khi đạt đến n, binh sĩ tương ứng được lấy ra khỏi vòng và việc đếm lại bắt
đầu từ binh sĩ tiếp theo. Quá trình này cứ tiếp tục cho đến khi chỉ còn lại một
binh sĩ. Đó là người sẽ được chọn để đi cầu cứu. Viết thuật toán cài đặt cách
chọn và tìm ra binh sĩ sẽ được chọn.
Tài liệu: Docs.vn Hỗ trợ : Y!M minhu888
II. Giải quyết bài toán:
1. Phân tích bài toán:
Các binh sĩ được sắp xếp đứng thành vòng tròn và có thứ tự lần lượt từ
1 đến m (với m là số binh sĩ).
Binh
sĩ
3

Binh sĩ
2
Binh sĩ
6
Binh
sĩ
2
Binh
sĩ
5
Binh
sĩ
4
Binh
sĩ
1
Binh
sĩ
7
Binh
sĩ
m
Binh
sĩ
…..
Chọn n = 3
Binh sĩ thứ 2 được
chọn ngẫu nhiên
Binh sĩ thứ 4 sẽ bị loại
sau khi đếm đến n.