Mô tả vấn đề
--
Vấn đề đặt ra: Có m người đứng thành một vòng tròn, đánh số từ 0 đến m-1. Bắt đầu từ người thứ 0, họ bắt đầu đếm, người đếm đến k-1 sẽ bị loại ra khỏi vòng tròn. Người tiếp theo tiếp tục đếm từ 0 và người đếm đến k-1 tiếp theo cũng bị loại ra... quá trình này lặp lại cho đến khi chỉ còn lại một người trong vòng tròn. Cần xác định số thứ tự của người cuối cùng còn lại.
Cách đơn giản nhất để giải quyết vấn đề này là sử dụng cấu trúc dữ liệu danh sách liên kết để mô phỏng quá trình loại bỏ người. Tuy nhiên, có một cách tiếp cận khác dựa trên việc phát hiện mối quan hệ đệ quy, sau đó sử dụng phương pháp đệ quy để giải quyết.
Cơ sở
--
Giả sử chúng ta có 10 người, đánh số từ 0 đến 9, và k=4, nghĩa là mỗi lần đếm đến 3 thì người đó bị loại ra. Hình dưới đây thể hiện toàn bộ quá trình.
Từ hình trên, có thể thấy ở lượt đếm đầu tiên, số mà mỗi người sẽ gọi ra chính là số thứ tự của họ. Mỗi lần một người bị loại ra, số mà các người còn lại gọi ra sẽ thay đổi, ví dụ 4 trở thành 0, 5 trở thành 1, v.v. Như vậy, số mà mỗi người gọi ra sẽ thay đổi ở mỗi lượt đếm. Chúng ta cần tìm ra số thứ tự ban đầu của người cuối cùng bị loại ra (người này gọi số 0 ở lượt cuối cùng và là người duy nhất còn lại).
Nhận thấy, dựa trên hai cột của vòng 10 người và vòng 9 người, để xác định số mà một người đã gọi ở lượt trước, ta chỉ cần cộng thêm k vào số mà họ gọi ở lượt sau rồi lấy modulo với số lượng người ở lượt trước. Khi chỉ còn lại một người, số mà họ gọi chắc chắn là 0. Vì mỗi lượt đếm, ta có thể xác định được số mà người đó đã gọi ở lượt trước và số lượng người giảm đi mỗi lượt, điều này phù hợp với tính chất của đệ quy, do đó ta có thể sử dụng phương pháp đệ quy để giải quyết vấn đề.
Đoạn mã dưới đây minh họa cách giải quyết bằng đệ quy:
int timNgươiCuoi(int soNguoi, int buocNhay){
if(soNguoi == 1) return 0; // Trong trường hợp còn lại 1 người, người đó chắc chắn gọi số 0
else {
int viTriTruoc = (timNgươiCuoi(soNguoi - 1, buocNhay) + buocNhay) % soNguoi;
return viTriTruoc;
}
}
int timViTriBanDau(int soNguoi, int buocNhay, int luotDiem) {
if(luotDiem == 1) return (buocNhay - 1) % soNguoi; // Nếu ở lượt đầu tiên, người bị loại ra chắc chắn gọi số (buocNhay - 1)
else return ((timViTriBanDau(soNguoi - 1, buocNhay, luotDiem - 1) + buocNhay) % soNguoi);
}
for(int i = 1; i <= soNguoi; i++) { // In ra thứ tự bị loại ra của từng người từ lượt 1 đến lượt cuối cùng
cout << timViTriBanDau(soNguoi, buocNhay, i) << endl;
}