Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# - Tập 2 - Chương 3: Trò chơi

in(x - i, m); 
 for (int j = 1; j <= minj; ++j) // xet cot j 
 if (a[i, j] == 0) 
 for (int k = 1; k <= m; ++k) 
 if (k != j) a[i + j, k] = 1; 
 } 
 return a[x, y]; 
 } 
 static void Show(int[,] s, int n, int m) { 
 Console.WriteLine(); 
 for (int i = 1; i <= n; ++i) { 
 Console.Write("\n"+i+". "); 
 for (int j = 1; j <= m; ++j) 
 Console.Write(a[i, j] + " "); 
 } 
 } 
 }// Program 
} 
 Nếu N có kích thước lớn, thí dụ, cỡ triệu dòng, còn số cột M vẫn đủ nhỏ, thí dụ M  50 và đề ra chỉ 
yêu cầu cho biết người đi trước thắng hay thua chứ không cần lý giải từng nước đi thì ta vẫn có thể sử dụng 
một mảng nhỏ cỡ 5151 phần tử để giải bài toán trên. Ta khai báo kiểu mảng như sau: 
const mn = 51; 
type 
 MB1 = array[0..mn] of byte; 
 MB2 = array[0..mn] of MB1; 
var a: MB2; 
 N: longint; 
 M: integer; 
.... 
Ta sử dụng mảng index dưới đây để chuyển đổi các số hiệu dòng tuyệt đối thành số hiệu riêng trong 
mảng nhỏ a. bạn chỉ cần lưu ý nguyên tắc sau đây khi xử lý các phép thu gọn không gian: Không ghi vào 
vùng còn phải đọc dữ liệu. Thực chất đây là một hàm băm các giá trị i trong khoảng 1..N vào miền 0..M 
bằng phép chia dư: i  (i-1) mod (M+1) như mô tả trog hàm index. 
function index(i,M: integer): integer; 
begin 
 index := i mod (M+1); 
end; 
function Ket(M: integer; 
 x: longint; y: integer): integer; 
 var i: longint; j,k: integer; 
begin 
 fillchar(a,sizeof(a),0); 
 for i:= 1 to x-1 do 
 begin 
 k := index(i+M,M); 
 fillchar(a[k],sizeof(a[k]),0); 
 for j:=1 to Min(x - i, M)do 
 if (a[index(i,M),j] = 0) then 
 for k := 1 to M do 
 111 
 if (k j) then 
 a[index(i+j,M),k] := 1; 
 end; 
 Ket := a[index(x,M),y]; 
end; 
//C# 
static int Index(int i, int m) { return i % (m + 1); } 
static int Ket(int m, int x, int y){ 
 int id, Minj, i, j, k, v ; 
 Array.Clear(a, 0, b.Length); 
 for (i = 1; i < x; ++i) { 
 id = Index(i + m, m); 
 for (v = 1; v <= m; ++v) a[id, v] = 0; 
 minj = Min(x - i, m); 
 for (j = 1; j <= minj; ++j) // xet cot j 
 if (a[Index(i, m), j] == 0) 
 for (k = 1; k <= m; ++k) 
 if (k != j) a[Index(i + j, m), k] = 1; 
 } 
 return a[Index(x,m), y]; 
} 
Đến đây ta thử mở rộng điều kiện của bài toán như sau: Hãy cho biết, với các giá trị cho trước là 
kích thước bảng N M, vị trí xuất phát của quân cờ @ (x,y) và đấu thủ A đi trước thì A thắng hoặc thua sau 
bao nhiêu nước đi ? 
Nguyên tắc của các trò chơi đối kháng 
 Nếu biết là thắng thì tìm cách thắng nhanh nhất, 
 Nếu biết là sẽ thua thì cố kéo dài cuộc chơi để 
có thể thua chậm nhất. 
 Ta vẫn sử dụng bảng A để điền trị với các qui ước mới sau đây: 
Nếu từ ô (i, j) người đi trước có thể thắng sau b nước đi thì ta đặt a[i,j] = +b; ngược lại nếu từ ô này 
chỉ có thể dẫn đến thế thua sau tối đa b nước đi thì ta đặt a[i,j] = b. Một nước đi là một lần di chuyển quân 
cờ của một trong 2 người chơi. Ta cũng qui ước a[i,j] = 0 có nghĩa là đấu thủ xuất phát từ ô (i,j) sẽ hết cách 
đi do đó chấp nhận thua ngay. Kí hiệu (i,j)  (u,v) nếu có nước đi hợp lệ từ ô (i,j) sang ô (u,v). Từ nguyên 
tắc của các trò chơi đối kháng ta suy ra 
 (1) Nếu từ ô (i,j) có những nước đi hợp lệ dẫn đến thế (làm cho đối phương) thua thì ta chọn 
cách thắng nhanh nhất bằng cách đặt 
a[i,j] = min { a[u,v] | (i,j)  (u,v), a[u,v]  0 } + 1 
 (2) Nếu từ ô (i,j) mọi nước đi hợp lệ đều dẫn đến thế (tạo cho đối phương thắng) thì ta phải 
chọn cách thua chậm nhất bằng cách đặt 
a[i,j] =  (max { a[u,v] | (i,j)  (u,v), a[u,v] > 0 } + 1) 
 1 2 3 4 
1 0 0 0 0 
 112 
Sau khi lấp đầy 0 cho bảng a ta lần lượt duyệt các dòng i từ 1 đến x. Với mỗi 
dòng ta duyệt các cột j từ 1 đến M. Nếu gặp trị a[i,j] = 0 ta hiểu là vị trí này sẽ dẫn 
đến thua. Ta cần tính số bước thua chậm nhất rồi gán cho a[i,j]. Tiếp đến, do vị trí 
(i,j) là thua nên ta phải cập nhật lại các giá trị a[u,v] ứng với các vị trí (u,v)  (i,j). 
Bạn thử điền trị cho bảng a với N = 12, M = 4. Trong thí dụ này, a[8,2] = - 4 
có nghĩa là nếu quân cờ @ đặt ở vị trí (8,2) thì người đi trước sẽ thua sau 4 nước 
đi. Thật vậy, gọi A là người đi trước, ta thấy nếu A di chuyển @ đến (7,1) thì B sẽ 
đi tiếp để thắng sau 3 nước đi; A không thể đên dòng 6 (?). Nếu A đến (5,3) thì B 
sẽ đi tiếp để thắng sau 1 nước. Nếu A đến (4,4) thi B sẽ đi tiếp 1 nước nữa để đến 
(1,3) là thắng. 
Tại sao trong hàm Ket ta phải tính thế thua trước khi tính thế thắng. Vì khi 
gặp a[i,j] = 0 thì ta cần cập nhật giá trị này để biết được là sẽ thua sau bao nhiêu 
nước đi. Sau đó, do cơ chế lập luận lùi, chỉ khi nào ta biết số nước thua tại a[i,j] thì 
mới tính tiếp được các thế thắng dẫn đến hế thua này. 
function Ket(M,x,y: integer): integer; 
 var i, j: integer; 
begin 
 fillchar(a,sizeof(a), 0); 
 for i := 1 to x do 
 for j := 1 to M do 
 if (a[i,j] = 0) then 
 begin 
 TinhNuocThua(M,i,j); 
 TinhNuocThang(M,x,i,j); 
 end; 
 Ket := a[x,y]; 
end; 
Procedure TinhNuocThua(M,i,j: integer); 
 var k, vmax: integer; 
begin 
 vmax := -1; 
 for k := 1 to Min(i-1,M) do 
 if (k j) then 
 vmax := Max(vmax, a[i-k,k]); 
 a[i,j] := -(vmax + 1); 
end; 
Procedure TinhNuocThang(M,x,i,j: integer); 
 var k, d, v: integer; 
begin { Xet dong i+j } 
 d := i+j; 
 if (d <= x) then { quan co con trong vung can xu ly } 
 begin 
 v := -a[i,j] + 1; 
 for k := 1 to M do 
 if (k j) then 
 if (a[d,k] > 0) then a[d,k] := Min(a[d,k], v) 
 else a[d,k] := v; 
 end; 
end; 
// C# 
 static int Ket(int n, int m, int x, int y) { 
 Array.Clear(a, 0, a.Length); 
 for (int i = 1; i <= x; ++i) { // voi moi dong i 
 for (int j = 1; j <= m; ++j) // xet cot j 
2 0 1 1 1 
3 1 1 1 1 
4 1 1 -2 1 
5 1 1 1 -2 
6 -2 -2 -2 -2 
7 3 3 3 3 
8 3 -4 3 3 
9 3 3 3 3 
10 3 3 3 5 
11 -4 -4 -4 -4 
12 -4 5 5 5 
Tab Game với 
N = 12, M = 4. 
 113 
 if (a[i, j] == 0) { 
 TinhNuocThua(m, i, j); 
 TinhNuocThang(m, x, i, j); 
 } 
 } 
 return a[x,y]; 
 } 
 static void TinhNuocThua(int m, int i, int j) { 
 int vmax = -1, km = Min(i-1,m); 
 for (int k = 1; k <= km; ++k) 
 if (j != k) vmax = Max(vmax, a[i - k, k]); 
 a[i,j] = -(vmax + 1); 
 } 
 static void TinhNuocThang(int m, int x, int i, int j){ 
 int d = i + j; 
 if (d > x) return; 
 int vmin = -a[i,j]+1; 
 for (int k = 1; k <= m; ++k) 
 if (k != j) 
 a[d,k] = (a[d, k] > 0) ? Min(a[d, k], vmin) : vmin; 
 } 
Với N cỡ triệu và M đủ nhỏ bạn cũng có thể vận dụng các kĩ thuật tương tự như đã trình bày để có 
thể tính số nước thắng/thua, tuy nhiên trong trường hợp này bạn phải khai báo mảng a rộng gấp đôi, tức là a 
phải chứa 2M+2 dòng gồm M dòng trước dòng đang xét và M dòng sau dòng đang xét. các dòng trước và 
sau này dùng để cập nhật số nước đi thắng/thua. 
Đến đây ta có thể sử dụng thuật toán Cờ bảng để giải bài Cờ Đẩy 
sau đây. 
Bài 3.13. Cờ đẩy 
 Bàn cờ là một giải băng chia ô mã số từ 1 đến N. Hai đấu thủ A và 
B đan xen nhau, mỗi người đi một nước, A luôn đi trước. Một quân cờ @ 
đặt cạnh ô x. Tại nước đi thứ i phải đẩy quân cờ lên (về phía chỉ số nhỏ) d i 
ô, 1  di  M và không được lặp lại cách vừa đi của đấu thủ trước, tức là 
di  di-1. Đấu thủ nào đến lượt mình không đi nổi thì thua. Giả thiết là hai 
đấu thủ đều chơi rất giỏi. Biết N, M, x và A là đấu thủ đi trước. Hãy cho 
biết 
a) A thắng (ghi 1) hay thua (ghi 0). 
b) A thắng hay thua sau bao nhiêu nưới đi? 
Giả sử hai đấu thủ đi v nước đi với mức đẩy lần lượt là d1, d2 ,..., dv 
thì giả thiết của đề bài cho biết hai mức đẩy kề nhau là di-1 và di phải khác 
nhau. Giả sử bàn cờ có N = 12 ô, quân cờ đặt cạnh ô x = 7, mỗi nước đi 
phải di chuyển quân cờ lên 1, 2.., hoặc M = 4 ô và không được lặp lại nước 
vừa đi của người trước. Nếu A đi trước thì sẽ có thể thắng sau tối đa 4 nước 
đi. Chẳng hạn, A đi lên 1 bước d1 = 1 để đến ô 6. B có thể chọn một trong 3 
cách đi ứng với d2 = 2, 3, hoặc 4. để đến ô 4, ô 3 hoặc ô 2. Nếu B chọn d2 = 
2 để đến ô 4 thì A di chuyển lên theo d3 = 3 để đến ô 1 khiến cho B thua. 
Nếu B chọn d2 = 3 để đến ô 3 thì A di chuyển lên theo d3 = 2 để đến ô 1 
khiến cho B thua. Cuối cùng, nếu B chọn d = 4 để đến ô 2 thì A di chuyển lên theo d3 = 1 để đến ô 1 khiến 
cho B thua. các giá trị di theo từng phương án khi đó là như sau: 
 Phương án 1: (1, 2, 3). 
 Phương án 2: (1, 3, 2). 
 Phương án 3: (1, 4, 1). 
 Thuật toán 
 0 1 2 3 4 
1 0 0 0 0 
2 0 1 1 1 
3 1 1 1 1 
4 1 1 -2 1 
5 1 1 1 -2 
6 -2 -2 -2 -2 
7 @ 3 3 3 3 
8 3 -4 3 3 
9 3 3 3 3 
10 3 3 3 5 
11 -4 -4 -4 -4 
12 -4 5 5 5 
Cờ đẩy N = 12, M = 4, x = 7 
và Tab Game tương ứng. 
 114 
Chúng ta hãy thiết lập sự tương ứng giữa cờ đẩy và cờ bảng và chỉ ra rằng A thắng cờ đẩy khi và chỉ 
khi A thắng cờ bảng tương ứng. Cờ đẩy N ô, giới hạn bước đi M và ô xuất phát x tương ứng với cờ bảng N 
ô dài, M ô ngang và vị trí xuất phát (x,y) trong đó y = d1 là nước đi hợp lệ đầu tiên đến 1 ô thua, x := x-d1. 
Có một cách tư duy để có thể dễ dàng tính được (x,y) như sau. Ta thêm cho cờ bảng một ô giả mang 
mã số 0 và qui định rằng quân cờ bảng xuất phát tại ô (x,0) - dòng v, cột 0. Sau đó, trong cuộc chơi với cờ 
bảng này không ai được phép di chuyển đến cột 0. Nếu A đi đầu tiên thì chắc chắn sẽ di chuyển từ ô (x,0) 
đến một ô mà B chắc thua. Trong thí dụ này, nước đi đầu tiên của A sẽ là (7,0)  (6,1), tức là chuyển quân 
cờ từ cột 0 sang cột 1. 
Bài cờ đẩy mới xem tưởng như đơn giản nhưng để giải được ta lại phải xét bài khó hơn nhưng có lời 
gỉai trong sáng, dẽ hiểu 
Bài 3.14. Bốc sỏi H 
Dạng phát biểu khác của bài Cờ đẩy 
Cho đố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ối thiểu 1 viên, tối đa M viên trong đống và không được lặp lại nước vừa đi của người trước. Thí 
dụ, nếu đấu thủ A vừa bốc v viên sỏi thì đến lượt mình, đấu thủ B không được bốc v viên nữa. Đấ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. Cho biết a) A thắng hay thua. b) A 
thắng hay thua sau bao nhiêu nưới đi?