Chủ đề này có 4 trả lời

[tv_thinh]

1. Tổng số bước di chuyển của một con ngựa trên bàn cờ 8x8 ?
2. Tổng số bước di chuyển của một con ngựa trên bàn cờ nxn (n>=3) ?

Bài viết đã được chỉnh sửa nội dung bởi tv_thinh: 28-07-2009 - 07:17

[chuyentoan]

Không hiểu rõ ý của đề lắm. Bạn có thể định nghĩa thế nào là "tổng số bước di chuyển của một con ngựa" không?

[tv_thinh]

Ví dụ 1 bước di chuyển của ngựa trên một bàn cờ 8x8 : Khi con ngựa nằm ở vị trí góc của bàn cờ nó có 2 bước đi.
Nhưng trên bàn cờ, con ngựa có thể nằm ở vị trí bất kỳ trong 64 ô vuông (bàn cờ 8x8) với mổi vị trí thì ngựa có n (số từy ý) bước đi.
Bài toán hỏi rằng, tổng số các bước đi có thể của con ngựa có thể đi trên bàn cờ từ bất cứ vị trí xuất phát nào.

[yeutoan93]

lạ nhỉ
theo mình biết thì ngựa đc 8 bước từ 1 vị trí là cùng
ko hiểu đề lắm

[chuyentoan]

Ví dụ 1 bước di chuyển của ngựa trên một bàn cờ 8x8 : Khi con ngựa nằm ở vị trí góc của bàn cờ nó có 2 bước đi.
Nhưng trên bàn cờ, con ngựa có thể nằm ở vị trí bất kỳ trong 64 ô vuông (bàn cờ 8x8) với mổi vị trí thì ngựa có n (số từy ý) bước đi.
Bài toán hỏi rằng, tổng số các bước đi có thể của con ngựa có thể đi trên bàn cờ từ bất cứ vị trí xuất phát nào.

Nếu theo mình hiểu đề của bạn thì mình giải như sau:

Cứ một hình chữ nhật 2*3 hoặc một hình chữ nhật 3*2 thì xác định đúng 2 cặp ô mà mỗi cặp là 2 bước đi của con mã (cặp 1: ô trên trái và ô dưới phải, cặp 2: ô dưới trái và ô trên phải) => Mỗi một hình chữ nhật như thế xác định đúng 4 bước đi của con mã và ngược lại mỗi một bước đi của con mã chỉ xác định một hình chữ nhật duy nhất. Như vậy bài toán trờ thành tính số hình chữ nhật 2*3 và 3*2 trong bảng n*n. Do bảng đối xứng nên ta chỉ cần tính số hình chữ nhật 2*3 (ngang 2 dọc 3). Ta cho song ánh từ các hình chữ nhật 2*3 đến ô vuông bên trái phía dưới. Nhận xét là ô vuông bên trái phía dưới chỉ có thể nằm trong hình chữ nhật (n-1)*(n-2) bên trái phía dưới. Vậy có tất cả (n-1)*(n-2) hình chữ nhật 2*3 => Có tất cả 2*(n-1)*(n-2) hình chữ nhật 2*3 và 3*2 => Có tất cả 8*(n-1)*(n-2) bước đi của con mã.