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ò chơi NIM có xuât xứ từ Trung Hoa, dành cho hai đấu thủ A và B với các nước đi lần lượt đan nhau trên một đấu trường với N đống sỏi. Người nào đến lượt đi thì được chọn tùy ý một đống sỏi và bốc tối thiểu là 1 viên, tối đa là cả đống đã chọn. Ai đến lượt mình không thể thực hiện được nước đi sẽ thua. Ta giả thiết là A luôn đi trước và hai đấu thủ đều chơi rất giỏi. Cho biết A thắng hay thua?
Thuật toán
   Gọi số viên sỏi trong các đống là S1, S2,…, SN.
Kí hiệu Å là tống loại trừ (xor). Đặt x =  S1Å S2ÅÅSN. Ta chứng minh rằng bất biến thua của trò chơi NIM là x = 0, tức là nếu x = 0 thì đến lượt ai đi người đó sẽ thua.
Trước hết nhắc lại một số tính chất của phép toán Å theo bit.
1) a Å b = 1 khi và chỉ khi a ≠ b.
2) a Å 0 = a
3) a Å 1 = not a
4) Tính giao hoán: a Å b = b Å a
5) Tính kết hợp: (a Å b) Åc = a Å(b Å c)
6) Tính lũy linh: a Å a = 0
7) a Å b Å  a = b
8) Tính chất 7 có thể mở rộng như sau: Trong một biểu thức chỉ chứa phép xor ta có thể xóa đi chẵn lần các phần tử giống nhau, kết quả sẽ không thay đổi.
 Để dễ nhớ ta gọi phép toán này là so khácso xem hai đối tượng có khácnhau hay không. Nếu khác nhau là đúng (1) ngược lại là sai (0).
Bất biến x = 0 có ý nghĩa như sau: Nếu viết các giá trị Si, i = 1..N dưới dạng nhị phân vào một bảng thì số lượng số 1 trong mọi cột đều là số chẵn.

Dạng nhị phân
S1 = 13
1
1
0
1
S2 = 14
1
1
1
0
S3 = 6
0
1
1
0
S4 = 7
0
1
1
1
S5 = 2
0
0
1
0
Å x = 0
0
0
0
0
Bảng bên cho ta S1ÅS2ÅS3ÅS4ÅS5 = 13Å14Å6Å7Å2 = 0.
Nếu x là tổng xor của các Si, i = 1..N, với mỗi i = 1..N ta kí hiệu K(i) là tổng xor khuyết i của các Sivới cách tính như sau: K(i) = S1ÅS2 ÅÅ Si-1 Å Si+1ÅÅ SN. Như vậy K(i) là tổng xor của các Sj sau khi đã loại trừ phần tử Six chính là tổng xor đủ của các Si, i = 1..N. Do Si Å Si= 0 và 0 Åy = y với mọi y nên K(i) = x Å Si.  Để cho tiện, ta cũng kí hiệu K(0) chính là tổng xor đủ của các Si, i = 1..N. Với thí dụ đã cho ta tính được các tổng khuyết như sau:
K(0) = S1ÅS2ÅS3ÅS4ÅS5 = 13Å14Å6Å7Å2 = 0.
K(1) = S2ÅS3ÅS4ÅS5 = 14Å6Å7Å2 = 13,
K(2) = S1ÅS3ÅS4ÅS5 = 13Å6Å7Å2 = 14,
K(3) = S1ÅS2ÅS4ÅS5= 13Å14Å7Å2 = 6,
K(4) = S1ÅS2ÅS3ÅS5= 13Å14Å6Å2 = 7,
K(5) = S1ÅS2ÅS3ÅS4= 13Å14Å6Å7 = 2.
                Ta phát hiện được qui luật lí thú sau đây:
                Mệnh đề 1.  Cho x là tổng xor của N số tự nhiên, Si, x = S1ÅS2Å...ÅSN. Khi đó K(i) =  x Å Si, i = 1,2,...,N. Tức là muốn bỏ một số hạng trong tổng Å ta chỉ việc Å thêm tổng với chính số hạng đó.  Nói riêng, khi x = 0 ta có K(i) =  Si, i = 1,2,...,N. 
Chứng minh
                Gọi xlà tổng xor đủ của các số đã cho, x = S1ÅS2Å...ÅSN. Vận dụng ính giao hoán và tính lũy đẳng ta có thể viết x Å Si = (S1ÅS2Å...ÅSi-1ÅSi+1ÅSN)Å(SiÅSi) = K(i) Å 0 = K(i), i= 1,2,...,N, đpcm.
Ta chứng minh tiếp các mệnh đề sau:
Mệnh đề 2. Nếu x ≠ 0 thì có cách đi hợp lệ để biến đổi x = 0.
Chứng minh
Do x ¹ 0 nên ta xét chữ số 1 trái nhất trong dạng biểu diễn nhị phân của  x = (xm, xm-1,…,x0), xj = 1, xi= 0, i > j.  Do xlà tổng xor của các Si, i= 1..N, nên tồn tại một Si = (am, am-1,…,a0) để chữ số aj = 1. Ta chọn đống Si này (dòng có dấu *). Khi đó, ta tính được K(i) = xÅ Si  = (xmÅam, xm-1Åam-1,…,x0Åa0) = (bm, bm-1,…,b0) với bi = xiÅai, 0 £ i£ m. Ta có nhận xét sau đây:
* Tại các cột i > j: bi = ai, vì bi = xiÅai = 0 Å ai= ai,
* Tại cột j ta có:  bj = 0, vì bj = xj Å aj= 1 Å 1 = 0.
Do aj = 1, bj = 0 và mọi vị trí  i > j đều có bi = ai nên Si  > K(i). Nếu ta thay dòng Si bằng dòng K(i) thì tổng xor y khi đó sẽ là 

Dạng nhị phân
x3
x2
x1
x0
S1 = 12
1
1
0
0
S2 = 14
1
1
1
0
* S3 = 6
0
1
1
0
S4 = 3
0
0
1
1
S5 = 2
0
0
1
0
Å x = 5
0
1
0
1
y= (x Å Si) Å K(i) = K(i) Å K(i)  = 0.
 Vậy, nếu ta bốc tại đống i số viên sỏi v = Si-K(i) thì số sỏi còn lại trong đống này sẽ là K(i) và khi đó tổng xor sẽ bằng 0, đpcm.
Mệnh đề 3. Nếu x = 0 và còn đống sỏi khác 0 thì  mọi cách đi hợp lệ đều dẫn đến x  ≠ 0.
Chứng minh
Cách đi hợp lệ là cách đi làm giảm thực sự số sỏi của một đống Si duy nhất nào đó, 1 £ i £N. Giả sử đống được chọn là Si=  (am, am-1,…,a0). Do Si bị sửa nên chắc chắn có một bit nào đó bị đảo (từ 0 thành 1 hoặc từ 1 thành 0). Ta gọi bít bị sửa đó là aj. Khi đó tổng số bít 1 trên cột j sẽ bị tăng hoặc giảm 1 đơn vị và do đó sẽ không còn là số chẵn. Từ đó suy ra rằng bit j trong x sẽ là 1, tức là x ≠ 0 đpcm.
                Phần lập luận chủ yếu trong mệnh đề 2 nhằm mục đích chỉ ra sự tồn tại của một tập Si thỏa tính chất Si > xÅSi. Nếu tìm được tập Si như vậy ta sẽ bốc Si-(xÅSi) viên tại đống sỏi i. 
Giả thiết rằng mảng S[1..N] kiểu nguyên chứa số lượng sỏi của mỗi đống đã khởi tạo như một đối tượng dùng chung, ta viết hàm Ket và thủ tục CachDinhư sau.
Hàm Ket sẽ cho ra giá trị là tổng xor x của các đống sỏi. Như vậy, khi x = 0 thì người nào đi sẽ thua, ngược lại, khi x  ≠ 0 thì người nào đi sẽ thắng.  
function Ket(N: integer): integer;
  var x, i: integer;
 begin
   x := 0;
   for i := 1 to N do x := x xor S[i];
   Ket := x;
end;
Thủ tục CachDi hoạt động như sau:
Gọi hàm x = Ket. Nếu x = 0 tức là sẽ thua thì chọn một đống còn sỏi, thí dụ đống còn nhiều sỏi nhất, để bốc tạm 1 viên nhằm kéo dài cuộc chơi. Nếu x = 0 và các đống đều hết sỏi thì đương nhiên là phải chịu thua.  Trường hợp x ¹0 thì ta tìm cách đi chắc thắng như sau:
Bước 1. Tìm đống sỏi i thỏa điều kiện x ÅSi < Si.
Bước 2. Bốc tại đống i đó Si - (xÅSi) viên.
procedure CachDi(N: integer; var D,V: integer);
   var x,i: integer;
begin
  x := Ket(N);  
    if x = 0 then { Thua }
    begin
      D := 1;
      for i := 2 to N do
          if (S[i] > S[D]) then D := i;
      if (S[D] = 0) {Het soi: Dau hang}
        then D := 0
       else S := 1;
      exit;
    end;
      { Chac thang }
     for D:=1 to N do
       if (s[D] > (x xor S[D])) then
         begin
           V := S[D]-(x xor S[D]); {boc V vien tai dong D }
           exit;
         end;
 end;
Trong các hàm C# dưới đây mảng s được khai báo n phần tử, các phần tử được mã số từ 0 đến n-1, trong khi các đống sỏi được mã số từ 1 đến n do đó chúng ta phải lưu ý chuyển đổi chỉ số cho thích hợp.


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