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, N, M  > 1. 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 nửa số viên của đố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
Mới xem ta thấy rằng bất biến thua cho bài này cũng là N = M. Dự đoán của bạn gần đúng vì N = M chỉ là một trường hợp đặc biệt của bất biến thua. Dễ thấy, nếu N = M =1 thì hết cách đi. Nếu N = M > 1 và A đi trước thì B chỉ việc cân bằng lại số sỏi của hai đống là chắc thắng. Vậy N = M là một điều kiện thua (cho người đi trước). 
Để lập bảng tính trị của hàm f(N,M) ta cũng nhận xét rằng hàm này đối xứng, tức là f(N,M) = f(M,N) vì trật tự của các đống sỏi là không quan trọng. Cũng chính vì f(N,M) là hàm đối xứng nên ta chỉ cần tính trị của f(N,M) với N £ M rồi lấy đối xứng qua đường chéo chính của bảng trị. Với mỗi N cho trước ta lần lượt điền từng dòng N của bảng với M = N, N+1, N+2,… Theo nhận xét trên ta có ngay f(N,N) = 0 với mọi N. Từ thế thua này ta thấy ngay f(N,N+d) = 1 với mọi d = 1,2,…N vì từ các thế này ta có thể bốc d viên từ đống thứ hai (đống có M=N+d viên) để dẫn đến thế thua f(N,N). Từ đây suy ra thế thua tiếp theo sẽ là f(N,N+N+1) = f(N,2N+1). Tương tự, thế thua tiếp sau thế này phải là f(N,2(2N+1)+1) = f(N,22N+2+1). Tổng qúat hóa ta thu được kết quả sau:
                Nếu đống sỏi thứ nhất có N viên thì các thế thua sẽ có dạng f(N,M) với M = 2kN+2k-1+…+2+1 = 2kN+(2k-1+…+2+1). Áp dụng công thức
2k-1 = (2-1)(2k-1+2k-2+…+2+1) = 2k-1+2k-2+…+2+1
ta thu được M = 2kN+2k-1 hay M+1 = 2k(N+1).
   Vậy
Bất biến thua  cho Bài Bốc sỏi F
Số sỏi trong hai đống thỏa hệ thức
(N+1) = 2k(M+1), k ³ 0   (*)
                Từ hệ thức (*) ta suy ra N = M là trường hợp riêng khi k = 0. 
                Hàm Ket và thủ tục CachDi khi đó sẽ như sau.
Để ý rằng các số nguyên trong máy tính được biểu diễn dưới dạng nhị phân nên giá trị 2k tương đương với toán tử dịch trái 1 k bit,  1 shl k.
function Ket(N,M : integer) : integer;
   var N1,M1,t: integer;
begin
    N1 := N+1; M1 := M+1;
  if N1 < M1 then
    begin
       t := N1; N1 := M1; M1 := t;
    end; { N1 ³ M1 }  
  while M1 < N1 do M1 := M1 shl 1; { 2*M1 }
  if (M1 = N1) then Ket := 0 else Ket := 1;
end;
Với thủ tục CachDicho tình huống thua thì A đành bốc 1 viên ở đống nhiều sỏi. Trong trường hợp thắng ta cũng chọn đống nhiều sỏi để bốc bớt S viên sao cho số sỏi giữa hai đống thỏa hệ thức (*). Ta tính S như sau. Giả sử N > M và k là số nguyên đầu tiên thỏa hệ thức N+1  <  2k(M+1). Khi đó, do điều kiện thắng nên ta phải có 2k-1(M+1) < N+1 < 2k(M+1) . Vậy số sỏi chênh lệch cần bốc bớt ở đống nhiều sỏi sẽ là S = N+1-2k-1(M+1). Ta chứng minh rằng 1 £ S £N/2. Thật vậy, vì 2k-1(M+1) < N+1 nên S = N+1-2k-1(M+1) ³1. Mặt khác, nếu S > N/2 thì 2S > N hay 2N+2-2k(M+1) > N. Từ đây rút ra N+1 >  2k(M+1)-1, hay N+1 ³  2k(M+1), mâu thuẫn với giả thiết về k.
procedure CachDi(N,M : integer; var D,S : integer);
    var N1,M1,t: integer;
begin
   { N = M = 1: dau hang }
   if (N = M) and (N = 1) then
    begin
       D := 0; S := 0;
       exit;
    end;
   { Chon dong nhieu soi }
   if N > M then D := 1 else D := 2;
   N1 := N+1; M1 := M+1;
   if N1 < M1 then
    begin
       t := N1; N1 := M1; M1 := t;
    end; { N1 ³ M1 }
   while M1 < N1 do M1 := M1 shl 1; { 2*M1 }
   if (M1 = N1) then { Thua }
      begin  { Se Thua }
         S := 1; { boc 1 vien }
         exit;
      end;
   { Cac tinh huong thang }
   M1 := M1 shr 1;
   S := N1-M1;
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