Một kỹ thuật sử dụng mảng

Trong các ứng dụng thông thường thì rất ít khi sử dụng mảng mà thay vào đó chủ yếu là sử dụng danh sách. Tuy nhiên, trong trường hợp các phần tử là hữu hạn thì dùng mảng là tốt nhất. Trong bài viết này, mình viết là một kỹ thuật sử dụng mảng trong thuật toán đơn giản, sẽ có ích với người mới làm quen với kỹ thuật lập trình.

Bài toán

Giả sử, chúng ta có một hình chữ nhật kích thước mxn. Đặt một quân cờ ở một vị trí vào một ô bất kỳ trong hình trên. Tại mỗi bước di chuyển, quân cờ sẽ di chuyển sang một trong bốn ô ở góc của ô hiện tại (như hình dưới). Nếu bước đi tiếp theo ra ngoài hình chữ nhật thì quân cờ sẽ đứng im tại chỗ.

Lời giải

Bài toán trên thực sự là rất đơn giản và thậm chí chỉ là một ví dụ minh họa mà thôi chức chưa hẳn là một bài toán. Tuy nhiên, chúng ta sẽ xem hai cách cài đặt sau đây và phân tích nhé.

Cách thứ nhất

Như chúng ta thấy trong code dưới đây (code C)

Ta sẽ thấy từ dòng 37 đến dòng thứ 53, trong đoạn này ta sẽ tính tọa độ của bước tiếp theo dựa vào tọa độ hiện tại của quân cờ và số r được sinh ngẫu nhiên. Ở đây, ta sẽ xét bốn trường hợp có thể xảy ra vì tại mỗi ô chỉ có tối đa bốn vị trí có thể đi. Nhưng trong các trường hợp khác có thể số lượng bước đi vẫn hữu hạn nhưng có thể sẽ nhiều hơn. Vậy làm thế nào để ta có thể viết đoạn code này một cách ngắn gọn hơn không? Bạn hãy quan sát các dòng code từ 40 đến 41 xem có khác gì không nhé.

Cách thứ hai

Chúng ta hãy xem đoạn code cải tiến của đoạn code thứ nhất nhé.

Bạn có thể thấy rằng, trong đoạn code thứ hai này đã thay thế 16 dòng code (từ 37 đến 53) chỉ với 2 dòng code mà kết quả vẫn thu được như nhau. Ta hãy quan sát, làm thế nào có thể biết được điều đó? Thất đơn giản, ta thấy rằng tại mỗi ô quân cờ có tối đa là bốn bước đi. Gọi tọa độ của quân cờ hiện tại là (curX, curY) thì hướng đi thứ nhất là về góc trên bên trái A(curX - 1, curY - 1), góc trên bên phải B(curX + 1, curY - 1), góc dưới bên phải C(curX + 1, curY + 1) và góc dưới bên trái D(curX - 1, curY + 1). 

Như vậy, mỗi bước đi sẽ làm thay đổi tọa độ của vị trí hiện tại 1 đơn vị. Chính vì thế, ta có thể định nghĩa sẵn các cặp chỉ số mà có thể sẽ sử dụng, theo như cách quy ước, r = 0 đi về hướng A, r = 1 đi về hướng B, r = 2 đi về hướng C và cuối cùng là đi về hướng D với r = 3. Nên ta sẽ định nghĩa hay mạng STEP_X và STEP_Y với bốn phần tử, phần tử thứ i sẽ địa diện cho cặp chỉ số cần dùng tới khi r = i. Khi sinh ngẫu nghiên r ta chỉ cần thay chỉ số r vào hai mảng trên để có được cặp chỉ số cần sử dụng mà thôi.

So sánh & nhận xét

Về cơ bản, hai cách này giống nhau là cần tính cặp chỉ số tiếp theo để quân cơ di chuyển. Nhưng cách thứ hai có một số ưu điểm có thể kể đến như sau:

1. Code ngắn gọn và dễ hiểu hơn.
2. Ít bị nhầm lẫn hơn so với cách thứ nhất (nhất là việc ghi các chỉ số và các dấu +/-)
3. Không bị bỏ xót bất kỳ trường hợp nào.

Kết luận

Bài toán ví dụ là một trường hợp rất đơn giản để minh họa kỹ thuật này. Tuy nhiên, đây cũng là một kỹ thuật đơn giản nhưng cũng rất cơ bản. Mình viết này mong muốn giúp đỡ những bạn bắt đầu làm quen với kỹ thuật lập trình có một cái nhìn rõ ràng.

Cuối cùng là một bài toán có thể áp dụng được phương pháp này. Bài toán mình muốn nêu ra ở đây là bài "Mã đi tuần" nổi tiếng. Gợi ý: tại vị trí trong bàn cờ, con mã có tối đa 8 cách có thể đi. Hãy định nghĩa bảng bước đi của con mã và giải bài toán này nhé (hãy làm với bàn cờ 7x7 trước đã nhé). Thanks for reading!!!