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 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 CachDicho 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
LẬP TRÌNH


tcaviet@gmail.com

0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts