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



Bàn cờ là một tấm bảng chữ nhật N dòng mã số từ trên xuống lần lượt là 1, 2,...,N và M cột mã số từ trái sang lần lượt là 1,2,...,M; 2 £ N £ 500, 2 £M £50. Một quân cờ @ được đặt tại dòng x, cột y. Hai đấu thủ A và B luân phiên  mỗi người đi một nước như sau: buộc phải chuyển quân cờ @ từ cột hiện đứng là y sang cột k tùy chọn nhưng phải khác cột y. Việc chuyển này phải được thực hiện nghiêm ngặt  như sau: trước hết đẩy ngược quân cờ @ lên k dòng. Nếu quân cờ vẫn còn trong bảng thì rẽ phải hoặc trái để đặt quân cờ vào  cột k, ngược lại nếu quân cờ rơi ra ngoài bảng thì coi như thua.
Như vậy, nếu quân cờ đang đặt tại vị trí (x,y) muốn chuyển quân cờ sang cột k ¹ y thì trước hết phải đẩy quân cờ đến dòng x-k. Nếu x-k ³ 1 thì được phép đặt quân cờ vào vị trí mới là  (x-k,k).
Giả thiết A luôn luôn là đấu thủ đi nước đầu tiên và hai đấu thủ đều chơi rất giỏi. Biết các giá trị N, M, x và y. Hãy cho biết A thắng (ghi 1) hay thua (ghi 0)?
s
u
v
w
x
j

A3


k




l
B2



m


A1

n




o




p

@


q




Với N = 8, M = 4, quân cờ @ đặt tại vị trí xuất phát  (7,2) và A đi trước ta thấy A sẽ thắng sau 3 nước đi đan xen tính cho cả hai đấu thủ như sau:
1. A chuyển @ từ vị trí @(7,2) sang vị trí A1(4,3)
2. B chuyển @ từ vị trí A1(4,3) sang vị trí B2(3,1)
3. A chuyển @ từ vị trí B2(3,1) sang vị trí A3(1,2)
B chịu thua vì hết cách đi!
Thuật toán
   Ta thử vận dụng kĩ thuật Nhân - Quả để điền  trị 1/0 vào mỗi ô (i, j) của bảng a với ý nghĩa như sau: nếu gặp thế cờ có quân cờ @ đặt tại vị trí (i, j) thì ai đi trước sẽ  thắng (1) hay  thua (0). Ta sẽ duyệt theo từng dòng  từ 1 đến N, trên mỗi dòng ta duyệt từ cột 1 đến cột M.
Ta có nhận xét quan trọng sau đây. Nếu ô (i, j) = 0 tức là gặp thế thua thì các ô đi đến được ô này sẽ là những thế thắng. Đó chính là các ô (i+j, k) với 1 £ k £ M và k ¹ j. 
Nhận xét
Nếu [i, j] = 0 thì mọi ô trên dòng i+j,
 trừ ô (i+j, j) đều nhận trị 1.
[i, j] = 0 Þ  [i+j, k] = 1, k = 1..M, k ¹ j.
Từ nhận xét này ta viết ngay được  hàm Ket - kiểm tra xem người đi trước với quân cờ @ tại ô (x,y) trên bàn cờ N´M sẽ thắng (1) hay thua (0).
Trước hết ta lấp đầy trị 0 cho bảng - mảng hai chiều a[1..N, 1..M] kiểu byte, sau đó lần lượt duyệt các phần tử của bảng và điền trị 1 theo nhận xét trên.
function Ket(x,y: integer): integer;
  var i,j,k: integer;
begin
   fillchar(a,sizeof(a),0);
   for i := 1 to x-1 do
       for j := 1 to Min(x-i,M) do
            if (a[i,j] = 0) then
           { Điền 0 cho các ô (i+j, k); k=1..M, k ¹ j }
                for k := 1 to M do
                   if (k <> j) then a[i+j,k] := 1;
   Ket := a[x,y];   
end;     
Thuật toán trên đòi hỏi độ phức tạp cỡ N.M2.

u
v
w
x


u
v
w
x
j
0
0
0
0


0
0
0
0
k
0
0
0
0


0
1
1
1
l
0
0
0
0


1
1
1
1
m
0
0
0
0


1
1
0
1
n
0
0
0
0


1
1
1
0
o
0
0
0
0


0
0
0
0
p
0
0
0
0


1
1
1
1
q
0
0
0
0


0
0
0
0
Lấp đầy 0 (bảng trái) rồi điền trị (bảng phải)
cho cờ bảng N = 8, M = 4.
Kết quả với x = 7, y = 2: a[7,2] = 1 (A thắng).
Để tham gia cuộc chơi với các giá trị N, M và (x,y) cho trước dĩ nhiên bạn cần tính trước bảng a theo thủ tục Ket nói trên. Sau đó, mỗi lần cần đi bạn chọn nước đi theo hàm CachDi như mô tả dưới đây.  Hàm nhận vào các giá trị N, M là kích thước dòng và cột của bảng; dòng sx, cột sy là vị trí đang xét của quân cờ @ và cho ra một trong ba giá trị loại trừ nhau như sau:
CachDi = 1 nếu tìm được một vị trí chắc thắng (nx,ny) để đặt quân cờ;
CachDi = 0 nếu không thể tìm được vị trí chắc thắng nào nhưng còn nước đi do đó buộc phải đi đến vị trí (nx,ny);
CachDi = -1 nếu hết cách đi, tức là chấp nhận thua để kết thúc ván cờ.
Ta thấy sau khi gọi thủ tục Ket thì dòng đầu tiên của bảng a chứa tòan 0 và phần tử a[2,1] cũng nhận trị 0. Đó là những thế buộc phải đầu hàng vì đã hết cách đi. Vậy tình huống đầu hàng (hay hết cách đi) sẽ là
sx  = 1, hoặc
sx = 2 và sy = 1.
Ngoài ra, do thủ tục Ket đã được gọi, tức là bảng a đã được điền thể hiện mọi cách đi của cuộc chơi nên a[sx,sy] cho ta ngay giá trị chắc thắng hoặc chắc thua của tình huống xuất phát từ ô (sx,sy). 
Nếu a[sx,sy] = 0 ta đành chọn nước đi có thể thua chậm theo Heuristic sau đây: Tìm cách đẩy quân cờ @ từ vị trí (sx,sy) lên càng ít ô càng tốt.
Nếu a[sx,sy] = 1 ta chọn nước đi có thể thắng nhanh theo Heuristic sau đây: Tìm cách đẩy quân cờ @ từ vị trí (sx,sy) lên cao nhất có thể được, tức là lên vị trí (nx, ny) thỏa đồng thời các điều kiện
a[nx, ny] = 0,
nx càng nhỏ càng tốt.
Sau này ta sẽ thấy các Heuristics trên chỉ là một cách đi tốt  chứ chưa phải là cách đi tối ưu.
function CachDi(M, sx, sy: integer; var nx,ny: integer): integer;
begin
  if (sx = 1) or ((sx = 2) and sy = 1)) then
   begin { Het cach di: Dau hang }
     CachDi := -1;
     exit;
   end;
  CachDi := a[sx,sy];
  if CachDi = 0 then { Con nuoc di nhung se thua }
     for ny := 1 to Min(sx-1,M) do
        if (ny <> sy) then
         begin
           nx := sx – ny;
           exit;
         end;
  { Chac thang } 
    for ny := Min(sx-1,M) downto 1 do
     if  (ny <> sy) then
       if (a[sx-ny,ny] = 0) then
           begin { chac thang }                           
              nx := sx – ny; exit;
           end;
       end;
end;
Hàm Min(a,b) cho ra giá trị min giữa hai số a và b cần dược mô tả trước như sau:
function Min(a,b: integer): integer;
begin
  if (a < b) then Min := a else Min := b;
 end;
Chương trình C# dưới đây mô tả một ván Cờ Bảng 50 ´ 7 giữa hai đấu thủ A (đi trước) và B. Quân cờ xuất phát tại vị trí (49,5). Ván này A sẽ thắng.
using System;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication1 {
  class Program {
    static int maxn = 501, maxm = 51;
    static int[,] a = new int [maxn,maxm];
    static void Main(string[] args){
      Game(50, 7, 49, 5);         
      Console.WriteLine("\n \n Fini");
      Console.ReadLine();
    }
    static void Game(int n, int m, int x, int y) {
      Console.WriteLine("\n The co " + n +
                        " X "+m+" @ = ("+x+","+y+")");
      Ket(m, x, y);
      Show(a, x, m);
      while (true) {
         Console.Write("\n A: ( " + x + " , " + y + " ) ");
         if (CachDi(m, x, y, ref x, ref y) == -1) {
            Console.Write("Dau hang !!!");
            Console.ReadLine();
            return;
         }
         else Console.Write(" ==> ( " + x + " , " + y + " ) ");
           if (Console.Read() == '.') return;
           Console.Write("\n B: ( " + x + " , " + y + " ) ");
           if (CachDi(m, x, y, ref x, ref y) == -1) {
              Console.Write("Dau hang !!!");
              Console.ReadLine();
              return;
           }
           else Console.Write(" ==> ( " + x + " , " + y + " ) ");
           if (Console.Read() == '.') return;
         } // while
     }
     static int CachDi(int m, int sx, int sy, ref int nx, ref int ny)
     {
        if (sx == 1 || (sx == 2 && sy == 1)) return -1;
        if (a[sx, sy] == 0) { // Di duoc, nhung thua
           for (ny = 1; ny <= Min(sx-1,m);++ny)
             if (ny != sy) {  nx = sx - ny; return 0; }
        }           
            for (ny = Min(sx-1,m); ny > 0; --ny)
              if (ny != sy)
                if (a[sx - ny, ny] == 0) // Chac thang
                { nx = sx - ny; return 1; }
            return 0;
    }
       static int Min(int a, int b) { return (a < b) ? a : b; }
       static int Ket(int m, int x, int y) {
         Array.Clear(a,0,a.Length);
         for (int i = 1; i < x; ++i) { // voi moi dong i
            int minj = Min(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
                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
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.
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
                    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.
 

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