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 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ỏ) di  ô,  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
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.

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