Vua Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
kinh doanh, bán hàng, tư vấn, bảo hiểm Những cá nhân, tổ chức, đại lý,muốn bán, hợp đồng bảo hiểm
Monday, December 16, 2013



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
LẬP TRÌNH
tcaviet@gmail.com

0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts