PDA

View Full Version : Josephus(sos!!!)



GiangPhiNgu
20-11-2004, 21:25
Các bạn làm ơn giúp mình thuật toán JOSEPHUS. Lập trình bằng C++, theo hướng đối tượng(tức là đưa tất cả thuộc tính, phương thức vào lớp). Đây là sự sơ nét về thuật toán này:
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 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ứ lặp lại cho đến khi chỉ còn lại một binh sĩ.

Rikku
20-11-2004, 22:31
Mình có thuật O(n) đó, chơi không, dùng Quy Hoạch Động.

GiangPhiNgu
21-11-2004, 11:24
Làm theo danh sách liên kết vòng đó bạn.nếu bạn có thì gửi ngay cho mình nhé.Thank

Rikku
21-11-2004, 12:29
a[i]:=( ( k mod i - 1 + a[i-1] ) ) mod i + 1;

k là số đếm, ở bài này là n. a[i] là người còn lại cuối cùng với i người..., tui thấy đâu cần dùng ds lkết đâu?

bete
21-11-2004, 13:51
Thân gửi Rikku: tui nghĩ nếu GiangPhiNgư đang học về danh sách thì xài danh sách là phải thôi. Ngoại trừ phần con trỏ của danh sách dễ bị sai, nói chung logic tương đối đơn giản (loại 1 người => loại 1 nút khỏi danh sách) => dễ trúng

Bạn đưa ra công thức: nếu đưa thêm phần chứng minh nữa thì sẽ hay hơn nhiều (phe ta có thể nhìn vô phần lý luận để biết đúng/sai). Tui đoán bạn lập luận như sau:

a[i-1]: có (i-1) người => a[i-1] là người còn lại cuối cùng
Nếu có i người: thêm 1 người => đi thêm 1 vòng nữa => nhảy thêm k bước. Nhảy k bước = nhảy (k mod i) bước
Nhưng vì mới loại 1 người ở bước (i-1) nên chỉ cần nhảy (k mod i) - 1 bước
=> người còn lại cuối cùng sẽ là (k mod i) - 1 + a[i-1]
=> mod i để chỉ số rơi đúng vào trong mảng
=> cuối cùng: + 1 (để chỉ số chạy từ 1 đên i thay vì từ 0 đến (i-1))

Nếu bạn lập luận cách khác thì xin cho biết; còn nếu bạn lập luận như trên thì tui xin thắc mắc:

1) giả sử có (i-1) người => phải đi (i-1) vòng (mỗi vòng nhảy k bước)

2) giả sử có i người => phải đi i vòng (mỗi vòng nhảy k bước). Vòng kế chót là vòng thứ (i-1): để tới được vòng kế chót này thì phải đi (i-1) vòng (mỗi vòng nhảy k bước). Tuy nhiên người chọn ra ở vòng này chưa chắc là người chọn ra ở (1): vì tuy rằng làm tương tự nhau: phải đi (i-1) vòng (mỗi vòng nhảy k bước); nhưng ở (1) mảng chỉ có (i-1) phần tử (ứng với i-1 người), còn ở đây thì mảng có tới i phần tử (ứng với i người) !?

(có gì sai sót xin các bạn chỉ giúp, cám ơn rất nhiều)

-thân

Rikku
21-11-2004, 22:56
Thế này nhé: a[i-1] là số thứ tự của người còn lại nếu ta xét chỉ có i-1 người, ta tính a[i] bằng cách:

1)Loại người thứ k mod i ra khỏi vòng "chiến" => còn lại i-1 người.
2)Cộng với a[i-1]-1 để ra được số thứ tự của người còn lại trong i người.
...
Cuối cùng ra được số thứ tự của người còn lại cuối cùng trong n người, thực chất chỉ cần dùng 2 biến, vì tính a[i] chỉ cần đến a[i-1].