Bốc sỏi D

Cho 2 đống sỏi với số viên sỏi lần lượt là N và M viên. Hai người chơi A và B, A luôn đi trước. Lượt chơi: Chọn đống tùy ý, bốc tối thiểu 1 viên và tối đa cả đống. Đấu thủ nào đến lượt mình mà  không đi nổi thì thua. Hãy cho biết A thắng hay thua. Giả thiết rằng hai đấu thủ  đều chơi rất  giỏi.

Thuật toán

                Bài này khá dễ giải.

Bất biến thua cho Bài Bốc sỏi D

Số sỏi của hai đống bằng nhau.

               

Nếu số sỏi của hai đống khác nhau thì A là đấu thủ đi trước sẽ cân bằng hai đống bằng cách chọn đống lớn rồi bốc bớt số sỏi chênh lệch để số sỏi của hai đống trở thành bằng nhau. Khi B đi thì sẽ biến hai đống thành khác nhau, đến lượt A lại cân bằng hai đống…

                Ta cũng dẽ dàng viết được hàm kết như sau:

(* Pascal *)

function Ket(N,M : integer) : integer;

begin

   if N = M then Ket := 0 else Ket := 1;

end;

                Thủ tục CachDi dưới đây sẽ xác định đống và số sỏi cần bốc cho mỗi tình huống. Hàm nhận vào là N - số lượng sỏi của đống thứ nhất và M - số lượng sỏi của đống thứ hai và cho ra hai giá trị: D - đống sỏi cần chọn và S - số viên sỏi cân bốc tại đống đó. Nếu N = M, tức là găp thế thua thì đành bốc 1 viên tại đống tùy chọn, một cách ngẫu nhiên.  Ta qui ước D = 0 là tình huống chịu thua, tức là khi cả hai đống đã hết sỏi.

(* Pascal *)

procedure CachDi(N, M : integer; var D,S : integer);

{ Dong 1: N vien, Dong 2: M vien soi }

begin

   if N = M then { Se Thua }

      begin

         if N = 0 then D := 0 { Het soi: dau hang } 

           else

           begin { Keo dai cuoc choi }

            S := 1; { boc 1 vien }

            D := random(2)+1;{tai 1 dong tuy chon}

           end; 

         exit;

      end;

   { Tinh huong thang }

    if N > M then D := 1 else D := 2; { Chon dong nhieu soi }

    S := abs(N-M); { Boc so soi chenh lech }

end; 

Bạn thử nghĩ 

Tình hình sẽ ra sao nếu ta xét lại bài này với điều kiện thu như sau: đấu thủ bốc những quân cuối cùng còn trên bàn sẽ thua?

 

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH