[QUESTION] Thuật toán cơ bản

[MrPaint]

Mình cần thuật toán để giải bài sau:
CHo 25 viên bi, hãy đưa thuật toán để người đi sau luôn thắng khi người phải bốc cuối là người thua...

Thanks

[Rikku]

Đề bài còn viết không rõ...
Theo mình đoán, đây là 1 dạng bài cơ bản về lý thuyết trò chơi.
Ta có 1 số định nghĩa như sau:
Trạng thái thắng: Là trạng thái mà từ đó luôn tồn tại một nước đi tới trạng thái thua.
Trạng thái thua: Là trạng thái mà từ đó mọi nước đi đều dẫn tới trạng thái thắng.
Việc thắng hay thua sẽ xác định được ngay khi ván chơi chưa bắt đầu.
Chiến lược của ta là với mọi nước đi đều hướng đối phương về trạng thái thua.
Để xác định một trạng thái nào là thắng hay thua có nhiều cách, nhưng thường dùng là phép cộng không nhớ (phép xor). Tùy vào bài toán mà áp dụng.

Ví dụ cho bài toán: Cho N đống bi, mỗi đống có a[i] viên bi. Mỗi nước đi mỗi người được phép bốc một số bi (>=1) ở 1 nhóm. Người bốc viên bi cuối cùng là người chiến thắng.Xác định người chiến thắng.
Solution:
Mỗi trạng thái ta Lấy tổng Nim: a[1] xor a[2] ...xor a[n].
Trạng thái cuối :Tổng Nim: a[1] xor a[2] ...xor a[n]=0 là trạng thái thua.
Trạng thái đầu : Tổng Nim nếu bằng 0. Chắc chắn thua. Vì với mọi nước đi đều dẫn tới trạng thái Tổng Nim <>0.
Còn Nếu không: tìm cách để đưa tổng Nim vể 0.
Vd:
2=010
3-011
5=101=S
X=100
số bi cần lấy: 5-4 xor 5=4 -> Tổng Nim mới : 2 xor 3 xor 1=0-> trạng thái thua. Vậy ta đã hướng đối phương về trạng thái thua.
Tóm lại là với mỗi nước đi tìm cách để đưa tổng Nim vể 0.

Hơi khó hiểu một chút...mình không nhớ rõ về cái này lắm, có gì sai sót xin chỉ bảo.

[hieept]

tương tự như bài này:
có 3 đống bi, đống thứ nhất có 3 viên, thứ 2 có 5 viên, thứ 3 có 7 viên (tổng cộng là 15 viên) bạn làm sao đề thắng dù bạn bốc trước hay bốc sau, người thua là người bốc viên cuối cùng, mỗi lần bốc chỉ đươc chọn một nhóm và muốn bốc mấy viên trong đống đó tùy ý..
tui thử rồi, bạn chỉ cần bốc cái đầu tiên thôi là biết bạn thắng hay thua đó

[MrPaint]

Thế không ai chỉ ra cách giải cụ thể được a`?
Mọi người toàn nói mà chẳng chỉ rõ gì cả?

TB: Đề bài mình chép nguyên xi rồi đó

[Free4Fun]

Hello các bác,

Bác Mr. Paint ơi bài toán của bác thiếu dữ kiện nên anh em không giúp được là phải. Vì vậy mới có 2 bác cho 2 ví dụ để bác ngâm cứu.

Thiếu dữ kiện ở chỗ này nè:
1. Phải có ràng buộc mỗi người đến lượt đi phải bốc tối thiểu 1 quân, nhiều nhất là ***x quân (nếu không đến lượt đi thì bác A nhường bác B, bác B nhường bác A, thành ra 2 bác ngồi chơi đến thế kỷ 22 cuộc chơi chưa khép lại.

2. Nếu không ràng buộc số quân tôi đa thì người đi trước luôn thắng, thuật toán quá tầm thường ví dụ tôi đi trước bốc 24 quân, còn bác (nếu có ràng buộc phải bốc ít nhất 1 quân) thì mời bác xơi quân cuối cùng ->bác thua thế thôi, còn nếu đến lượt mà không cần bốc cũng được thì đây là loai trò chơi ....???????

Thế bác cho thêm dữ kiện vào nhá, rồi anh em ở đây giúp cho

Thân
TDH

[Rikku]

tương tự như bài này:
có 3 đống bi, đống thứ nhất có 3 viên, thứ 2 có 5 viên, thứ 3 có 7 viên (tổng cộng là 15 viên) bạn làm sao đề thắng dù bạn bốc trước hay bốc sau, người thua là người bốc viên cuối cùng, mỗi lần bốc chỉ đươc chọn một nhóm và muốn bốc mấy viên trong đống đó tùy ý..
tui thử rồi, bạn chỉ cần bốc cái đầu tiên thôi là biết bạn thắng hay thua đó

Bài của anh thế này mà bảo tương tự...
Bài này khó hơn bài em nêu kia, khó hơn nhiều đấy, phải chia ra 2 trưởng hợp là số nhóm có số bi lớn hơn 1 là 0, và trường hợp còn lại...
Việc xác định thắng thua không là biết ngay khi chưa bắt đầu.
Grundy...

[coldsteel]

Thế không ai chỉ ra cách giải cụ thể được a`?
Mọi người toàn nói mà chẳng chỉ rõ gì cả?

TB: Đề bài mình chép nguyên xi rồi đó

Đề bài của bạn như thế mà bảo mọi người không chỉ rõ. Chí ít bạn cũng phải đưa ra số bi tối đa có thể bốc trong 1 lần chứ. Nếu đề bài chỉ có thế thì giải thuật đây: người đi sau bốc số bi sao cho chỉ còn lại 1 hòn bi => người đó thắng chắc rồi .

[Rikku]

Suýt quên, Paint muốn tìm hiểu thêm thì down cuốn Game Theory về mà đọc... hoặc nếu cần thì mình Mail cho..

[misty]

ba`i toa'n bo'c so?i co ba?n thoi ma`... nghien cu'u di, sao la.i ho?i lung tung the'...

[nambkpfiev]

Mình cần thuật toán để giải bài sau:
CHo 25 viên bi, hãy đưa thuật toán để người đi sau luôn thắng khi người phải bốc cuối là người thua...

Thanks

ans:
nguoi di sau phai boc 1 so bi sao cho so bi con lai la so le