ThỬ TrÍ ThÔng Minh BẰng MỘt ThuẬt ToÁn Cho CÁc BẠn

[langtuquen]

Có 2 người cùng chơi trò bốc que>mỗi người lần lượt bốc số que nhiều nhất có thể lấy cho mỗi lần bốc là 4 que. Cứ như thế cho đến hết số que đã có. Người nào lấy que cuối cùng sẽ thua cuộc> hãy lập thuật toán & nghĩ ra cách chơi sao cho người đi sau luôn thắng cuộc.

Các bạn giúp mình bài này nhé...
Có thể nó đơn gỉan với mấy bạn nhưng với mình thì không, các bạn có thể chỉ cho mình tận tình một chút nha....

ĐỪNG CÓ CÁI KIỂU POST BÀI MÀ CÓ VÀI DÒNH ĐẠI LOẠI NHƯ : HAY QUA! HOẶC BÀI NÀY DỄ ẸT MÀ CŨNG HỎI HOẶC CHÈN thêm emoticon vào lò xong một bài POST nha, mình ghét nhất là cái kiểu POST bài ấy, đã post thì post cho nó đàng hoàng,không post thì thôi, làm như vậy diễn đàn mất đi cái hay, thất toàn lá rác không hà....

Mình là NEWBIE, mình biết điều đó, nhưng Đ1O LÀ SUY NGHĨ THẬT LÒNG CỦA MÌNH với mong muốn làm cho những diễn đàn hay như thế này ngày một tốt hơn lên.

Cảm ơn các bạn!

[khangle]

Tổng số que được bốc là bao nhiêu que? Dựa vào đó mới có thuật giải được.

[vokeo]

minh co suy nghi nay khong biet co dung khong :
nếu tổng dố que là n và mỗi lần bốc không quá 4 thì
nếu ở lần gần cuối chỉ cần ép sao cho chỉ con 1 que và đến lượt đối thủ thì mình sẽ thắng thôi
ví dụ như có 10 que thi ở lần gần cuối chỉ cần mình bốc số que để sao cho chỉ còn 1 que còn lại thì khi đó mình thắng
bạn cứ theo suy nghĩ đó mà lần ra từ cuối đến đầu thôi . bạn hiểu chứ.
n=10 ta suy nghi bốc làm sao cho mình được
4 que khi đó đối phương buộc phải bốc 1 số que nào đó nhưng chắc chắn tổng số que <=8
dến lược mình mình bốc 1 thế là thắng

[pfiev]

Yes! Có N que, đặt N=1+5q+r, 0<=r<=4.
Nếu r=0 bốc đại thôi, tùy cơ may. Trường hợp này người đi sau thắng.
Nếu r từ 1 đến 4: người đi trước bốc r que. Sau đó mỗi lần người đi sau bốc k que thì người đi trước bốc 5-k que.

[Rongkhongcanh]

Qui ước: Người đi trước là A và Người đi sau là B.
Theo mình nên đặt tổng số que là N=5q+r (0<=r<=4). Khi đó:
+Nếu r=0, nghĩa là N chia hết cho 5 thì B luôn thắng bằng cách: Nếu A bốc k que (0<=k<=4) thì B bốc 5-k que. Nghĩa là phải bốc sao cho số que còn lại chia hết cho 5.
+Nếu r=1,2,3,4 thì A luôn thắng bằng cách: Đầu tiên bốc r que để số que còn lại chia hết cho 5. Sau đó nếu B bốc k que (0<=k<=4) thì A bốc 5-k que.
Từ đây có thể suy ra giải pháp tổng quát cho những bài toán dạng trên: Nếu cho bốc tối đa k que thì người nào bốc còn lại một số que mà chia hết cho k+1 thì sẽ thắng.

[Rongkhongcanh]

Ah, sorry. Giải thuật trên là giành cho bài toán người bốc cuối cùng thắng.

[unfriendlyboy]

Tổng quát bài của pfiev:

Giả sử có N que, và mỗi lần bốc tối đa là K que.
Với cách này người đi trước luôn thắng:

Đặt N = q.K + r + 1 với 0<=r<K
Nếu r = 0 thì bốc K que
Nếu r<>0 , tìm cách đưa về dạng trên ( tức là bốc K-r que )

:)

[unfriendlyboy]

E, hổng có ai hưởng ứng hết zị :)

[general2000vn]

Người ta đưa ra bài toán là người đi sau thắng mà, híc híc, sai đề bài, 0 điểm , về chổ

[daem0n]

Các bạn xem chương trình của mình nhé, có cả đồ họa trực quan sinh động, hé hé, mỗi lần bốc từ 1->3 token, người nào bốc sau cùng thua.
http://home.ripway.com/2004-3/80347/nim/Nim.htm
Chú ý là khi nhấn nút Restart thì chương trình chạy hơi bị "ba trợn", có thể là do vấn đề Threading, tuy nhiên có thể Refresh để chơi lại, have fun!