Bốc sỏi E

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 bốc những quân cuối cùng còn trên bàn sẽ 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

Dễ thấy khi một trong hai đống chỉ còn 1 viên sỏi, đống thứ hai có sỏi thì ai đi trước sẽ thắng, vì người đó chỉ việc bốc hết đống sỏi còn lại. Ta xét trường hợp N, M > 1. Với trường hợp này ta sử dụng bất biến thua T(N=M) và tìm cách cân bằng hai đống sỏi.               

M
N		‹	u	v	w			…
	i	1	0	1	1	1	1	…
		0	1	1	1	1	1	…
	k	1	1	0	1	1	1	…
	ƒ	1	1	1	0	1	1	…
	m	1	1	1	1	0	1	…
	n	1	1	1	1	1	0	…
…

Gọi A là đấu thủ đi trước, ta kí hiệu f(N,M) là hàm hai biến cho giá trị 1 nếu A thắng, và giá trị 0 nếu A thua, N và M là số sỏi trong hai đống. Dễ thấy f là hàm đối xứng, tức là f(N,M) = f(M,N) vì trật tự của hai đống sỏi không quan trọng. Để tính trị của f ta sử dụng ma trận hai chiều f, các dòng ứng với giá trị N, các cột ứng với giá trị M. Ma trận này đối xứng qua đường chéo chính, do đó ta luôn giả thiết là N £ M và sẽ lân lượt điền trị theo các dòng, tại mỗi dòng N ta bắt đầu điền trị từ các cột M ³ N trở đi. Ta có nhận xét thú vị sau đây:

* f(1,0) = f(0,1) = f(N,N) = 0, N > 1,

* Các giá trị còn lại trong bảng đều bằng 1.

Hàm Ket và thủ tục CachDi sẽ như sau.

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

1. N = M > 1, hoặc 2. (0, 1), (1, 0)

  

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

begin

   if (N + M = 1) or ((N = M) and (N > 1))

     then Ket := 0 else Ket := 1;

end;

Với thủ tục CachDi cho tình huống thắng ta phải xét khá nhiều trường hợp.

Trường hợp 1. Chỉ còn một đống: ta bốc đống kia, bớt lại một viên.

Trường hợp 2. Có một đống chứa duy nhất 1 viên sỏi: ta bốc hết đống kia.

Hai trường hợp 1 và 2 có thể gộp làm 1 như sau:

Trường hợp 1&2. Nếu một đống còn không quá 1 viên sỏi thì bốc ở đống kia số sỏi N+M-1.

Trường hợp 3. Cân bằng số sỏi hai đống bằng cách bốc số sỏi chênh lệch.

Để ý rằng trong cả 3 trường hợp thắng và cả trường hợp thua ta đều chọn đống có nhiều sỏi hơn để bốc.

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

begin

   { Chon dong nhieu soi }

   if N > M then D := 1 else D := 2;

   if (N + M = 1) or ((N = M) and (N > 1))then

      begin  { Se Thua }

         S := 1; { boc 1 vien }

         exit;

      end;

   { Cac tinh huong thang }

   if (N < 2) or (M < 2) then S := N+M-1

     else S := abs(N-M);     

end; 

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH