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
Binh
sĩ
2
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.
Binh
sĩ
2
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ĩ
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.

nghĩa là “Dữ liệu của bài toán sẽ được biểu diễn lại dưới dạng các
biến của chương trình thông qua các quy tắc xác định của ngôn ngữ
lập trình”.
• Gọi số lượng các binh sĩ là : m.
• Số thứ tự (vị trí) của các binh sĩ : sẽ được biểu diễn dưới dạng 1
danh sách ta sẽ phân tích ở dưới. Trong đó mỗi binh sĩ là 1 phần
tử element_type và số thứ tự này sẽ đại diện cho mỗi
element_type đó.
• Số thứ tự của binh sĩ được chọn ngẫu nhiên đầu tiên : k.
• Một số đếm n ngẫu nhiên : n.
• Phần tử cuối cùng được chọn trong danh sách chính là binh sĩ
được chọn : element.
• m, k, n, element_type, element đều là các số nguyên dương.
b) Nguyên lý 2:
Chuyển đổi quá trình tính toán của bài toán thành các cấu trúc của
chương trình, có nghĩa là “Mọi quá trình tính toán đều có thể mô tả và
thực hiện dựa trên ba cấu trúc cơ bản: Cấu trúc tuần tự, cấu trúc rẽ
nhánh và cấu trúc lặp”.
- Ở đây ta sẽ sử dụng cấu trúc tuần tự: để biểu diễn các phần tử
(binh sĩ) ta dùng một list (danh sách) dạng : node.
- Trong node ta quan tâm đến phần tử đầu tiên và phần tử cuối cùng:
first và last.
Cấu trúc node
first
(element_type)
next
(element_type)
last
(element_type)
........ ........