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



Trên bàn có một đống sỏi N viên, hai đấu thủ A và B lần lượt đi, A đi nước đầu tiên. Mỗi nước đi đấu thủ buộc phải bốc từ 1 đến M viên sỏi khỏi bàn. Đấu thủ nào đến lượt mình không đi nổi thì thua. Cả hai đấu thủ đều chơi rất giỏi. Với hai số N và M cho trước hãy cho biết A thắng (ghi 1) hay thua (ghi 0).
                Ta thử chơi với M = 3 và vài dữ liệu ban đầu N = 1, 2 ,…  Để tính nước đi cho đấu thủ A bạn hãy kẻ một bảng gồm 2 dòng. Dòng thứ nhất là các giá trị của N. Dòng thứ hai được ghi 0 ứng với tình huống A thua và 1 cho tình cho trường hợp A thắng, nếu A là đấu thủ đi nước đầu tiên.

M = 3
         N = 
0
1
2
3
4
5
6
7
8
9
10
11
12
13
A thắng (1) hay thua (0)?
0
1
1
1
0
1
1
1
0
1
1
1
0
1
Cách đi: số viên cần bốc để chắc thắng
#
1
2
3
#
1
2
3
#
1
2
3
#
1
Một vài tình huống cho bài Bốc sỏi A, M = 3; # - đầu hàng/bốc tạm 1 viên
               
                Thí dụ, với M = 3 cho trước và cố định, A là đấu thủ đi trước, ta có
                N = 0 là một thế thua, vì A không có cách đi.
                N = 1 là một thế thắng, vì A sẽ bốc 1 viên, B hết cách đi.
N = 2 là một thế thắng, vì A sẽ bốc 2 viên, B hết cách đi.
                N = 3 là một thế thắng vì A sẽ bốc 3 viên, B hết cách đi.
                N = 4 là một thế thua, vì dù A bốc 1, 2, hoặc 3 viên đều dẫn đến các thế thắng là 3, 2, 1…
                Làm thế nào để xác định được bất biến của trò chơi? Phương pháp đơn giản là tư duy Nhân - Quả hay là lập luận lùi. Cụ thể là, nếu biết kết quả là Q ta hãy gắng tìm nguyên nhân N sinh ra Q. Ta để ý rằng,

Qui  tắc xác định thế thắng / thua
Từ một thế X đang xét,
·         nếu tìm được một  nước đi dẫn đến thế thua T thì X sẽ là thế thắng V, và
·         nếu mọi nước đi từ X  đều dẫn đến thế thắng thì X  sẽ là thế thua T. 

                Trước hết ta sẽ tìm một thế thua nhỏ nhấtcủa cuộc chơi hay còn gọi  thế thua kết hoặc thế thua cuối cùng, vì đấu thủ nào gặp thế này đều phải đầu hàng và ván chơi kết thúc.
                Dễ thấy thế thua kết sẽ là N = 0: Hết sỏi, không thể thực hiện được nước đi nào.
                Vậy trước đó, những nước đi nào có thể dẫn đến thế thua T(N = 0)?
                Do mỗi đấu thủ chỉ được phép bốc 1, 2 hoặc 3 viên nên các thế thắng V trước đó chỉ có thể là N = 1, 2, hoặc 3.  Ta viết
T(N = 0) ßV(N = 1 | 2 | 3) ßT(N = ?)
                trong đó T là kí hiệu cho thế thua, V là kí hiệu cho thế thắng.
                Ta thử xác định thế thua T(N = ?). Dễ thấy với N = 4 thì mọi cách bốc 1, 2 hoặc 3 viên sỏi đều dẫn đến  thế thắng V(N = 3 | 2 | 1). Ta có,
T(N = 0) ß V(N = 1 | 2 | 3) ß T(N = 4)…
                Đến đây ta có thể dự đoán bất biến thua sẽ là N = 4k, cho trường hợp M = 3, hoặc tổng quát hơn, N = k(M+1), k ³ 0.
                Vậy bất biến thua là: 
T: Số viên sỏi trong đống là bội của M+1: N = k(M+1), k ³ 0.
                Ta sẽ chứng minh rằng nếu N = k(M+1), k = 0, 1, 2,…thì người đi trước (là A) luôn luôn thua.
                Trước hết để ý rằng nếu đấu thủ A gặp số sỏi là bội của M+1 thì với mọi cách đi của A số sỏi còn lại sẽ không phải là bội của M+1. Thật vậy, muốn bảo toàn tính chất là bội của M+1 thì A buộc phải bốc một bội nào đó của M+1, đây là điều không được phép vì vi phạm luật chơi.  
                Giả sử N = k(M+1), k ³ 1. Gọi số sỏi A bốc là s. Ta có, do  1 £ s £  M nên  B sẽ bốc u = (M+1)-s viên sỏi và do đó số sỏi còn lại sẽ lại là N = k(M+1) – s – ((M+1) – s) k(M+1)–(M+1) = (k–1)(M+1). Đây là một bội của (M+1).
                Nếu số sỏi là bội của M+1 thì với mọi cách đi hợp lệ, số sỏi còn lại sẽ không còn là bội của M+1. Nếu số sỏi không phải là bội của M+1 thì luôn luôn tồn tại một cách đi để chỉnh số sỏi trở thành bội của M+1.
Kết luận Bài Bốc sỏi A
Nếu số sỏi N =  k(M+1),  k ³ 0
thì đấu thủ nào đi trước sẽ thua.


                Với giả thiết A là đấu thủ đi trước, ta viết hàm Ket(N,M) cho ra giá trị 1 nếu A thắng, ngược lại hàm cho giá trị 0 nếu A thua.  Hàm có hai tham biến: N là số viên sỏi trong đống, M là giới hạn số viên sỏi được phép bốc. Hàm đơn thuần chỉ kiểm tra xem trị N có là bội của M+1 hay không.
(* Pascal *)
function Ket(N,M: integer): integer;
begin
   if (N mod (M+1) = 0) then ket := 0 else Ket := 1;
end;
                Hàm CachDi(N,M)dưới đây đảm nhận chức năng hướng dẫn người chơi chọn một cách đi. Trước hết cần kiểm tra xem thế đang xét là thắng hay thua. Nếu đó là thế thua và còn sỏi thì bốc 1 viên nhằm kéo dài thời gian thua. Nếu đó là thế thắng thì bốc số sỏi dư để số sỏi còn lại sẽ là bội của (M+1).
(* Pascal *)
function CachDi(N,M: integer): integer;
  var  r: integer;
begin
    r := N mod (M+1);
    if  r = 0 then { thua }
     begin
       if  N = 0 then CachDi := 0 else CachDi := 1;
       exit;
     end;
    CachDi := r;
end;

Nguồn:

SÁNG TẠO
TRONG THUẬT TOÁN
LẬP TRÌNH


0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts