bài toán ma trận la tinh. Nhờ mọi người giúp đỡ

[seotop1]

Ma trận n*n được gọi là la tinh nếu các phần tử của nó đuợc đánh số từ 1 đến n sao cho mỗi hàng và mỗi cột của nó đều là các hoán vị của các số từ 1 đến n.
mình và đứa bạn trạnh cãi nhau về bài toán này.nhờ mọi người chỉ giáo giùm thuật toán bài này với.
vì 2 đứa vẫn chưa thống nhất được ý kiến [IMG]images/smilies/biggrin.png[/IMG]

View more random threads:

• Cho mình hỏi cách dùng && và || ?
• Thêm số 0 đằng trước kết quả trong c++
• Anh em xem hộ bài này lỗi ở dâu với...
• Mọi người coi giùm em với! kết quả mỗi lần khác nhau vậy.
• In ra các số nguyên tố?
• lỗi C++ mong mọi người giúp càng nhanh càng tốt
• Giải thích thành phần phần mềm.
• Thắc mắc: làm sao in/xuất chữ tiềng việt ra màn hình\tiệp tin
• Tính giá trị biểu thức hậu tố
• Viết chương trình mô phỏng

[heartless]

Ma trận n*n được gọi là la tinh nếu các phần tử của nó đuợc đánh số từ 1 đến n sao cho mỗi hàng và mỗi cột của nó đều là các hoán vị của các số từ 1 đến n.
mình và đứa bạn trạnh cãi nhau về bài toán này.nhờ mọi người chỉ giáo giùm thuật toán bài này với.
vì 2 đứa vẫn chưa thống nhất được ý kiến [IMG]images/smilies/biggrin.png[/IMG]

Có thấy hai bạn tranh luận gì đâu?

[dungdt]

chẳng lẽ cãi nhau cũng đánh vào đây.
vì 1 đứa cho là xuất ra ma trận hoán vị chỉ có 1ma trận thôi,còn đứa bạn thì bảo xuất ra ma trận kiểu sudoku(như thế này thì với 1 giá trị n cho ra quá nhiều ma trận)

[phuongtrandinh]

thank bro.
giờ thì viết được rồi.

[ichiase24h]

chẳng lẽ cãi nhau cũng đánh vào đây.

Cũng phải đánh vào đây vấn đề mà hai bạn tranh luận chứ, thì mới biết ủng hộ ai chứ. Còn cãi nhau thì thôi.
Mình đưa ra một số thông tin nhé, xem hai bạn có thống nhất được không.

Việc tìm một công thức cho kết quả đếm ngay cả trong trường hợp công thức truy hồi không phải dễ dàng và lúc nào cũng thực hiện được. Cho đến nay còn nhiều bài toán đếm chưa có lời giải dưới dạng một công thức. Đối với những bài toán như vậy, người ta chỉ còn cách chỉ ra một phương pháp liệt kê, theo đó có thể đi qua được tất cả các cấu hình cần đếm. Rõ ràng bản thân phương pháp liệt kê không chỉ ra được một kết quả cụ thể nào nhưng qua đó người ta có thể lập trình cho máy tính điện tử đếm hộ.
Để minh hoạ cho phương pháp liệt kê, ta xét một cấu hình tổ hợp nổi tiếng đó là các hình chữ nhật la tinh. Giả sử S là tập gồm n phần tử. Không mất tính tổng quát ta giả sử S = {1, 2,.., n} Một hình chữ nhật la tinh trên S là một bảng gồm p dòng, q cột sao cho mỗi dòng của nó là một chỉnh hợp không lặp chập q của S và mỗi cột của nó là một chỉnh hợp không lặp chập p của S. Theo định nghĩa ta có p≤n, q≤n. Đặc biệt trong trường hợp q = n, mỗi dòng của hình chữ nhật la tinh là một hoán vị của S, sao cho không có cột nào chứa hai phần tử lặp lại. Hình chữ nhật la tinh dạng này được gọi là chuẩn nếu dòng đầu của nó là hoán vị 1, 2,.., n.
Thí dụ:

<div class="bbcode_description">HTML Code:
1 2 3 4 5 6 7
2 3 4 5 6 7 1
3 4 5 6 7 1 2
</div>là một hình la tinh chuẩn trên tập S = {1, 2, 3, 4, 5, 6, 7 }.
Gọi L(p,n) là số hình chữ nhật la tinh p x n, còn K(p,n) là số hình chữ nhật la tinh chuẩn p x n ta có: L(p,n) = n!K(p,n)
Dễ dàng nhận thấy rằng, số mất thứ tự D(n) là số hình la tinh chuẩn 2 x n, số phân bố U(n) là số hình chữ nhật la tinh chuẩn 3 x n với hai dòng đầu là:

<div class="bbcode_description">HTML Code:
1 2 ... n-1 n
2 3 ... n 1
</div>Riodan J(1946) đã chứng minh công thức:

<div class="bbcode_description">HTML Code:
K(3,n) = C(n,k)D(n-k)D(k)U(n-2k) (tổng lấy theo k từ 0 đến m= [n/2], U(0) = 1).
</div>Bài toán đếm với số dòng nhiều hơn đến nay vẫn chưa được giải quyết. Người ta mới chỉ đưa ra được một vài dạng tiệm cận của L(p,n).

Nếu p=q=n, thì hình chữ nhật la tinh được gọi là hình vuông la tinh. Một hình vuông la tinh cấp n được gọi là chuẩn nếu có dòng đầu và cột đầu là hoán vị 1, 2,..n. Thí dụ một hình vuông la tinh chuẩn cấp 7.

<div class="bbcode_description">HTML Code:
1 2 3 4 5 6 7
2 3 4 5 6 7 1
3 4 5 6 7 1 2
4 5 6 7 1 2 3
5 6 7 1 2 3 4
6 7 1 2 3 4 5
7 1 2 3 4 5 6
</div>Gọi l(n) là số các hình vuông như thế ta có L(n,n) = n!(n-1)!l(n).
Việc tìm một công thức cho l(n) đến nay vẫn bỏ ngỏ. Tuy nhiên ta có thể nhờ máy tính liệt kê tất cả các hình vuông chuẩn cấp n. Dưới đây là một vài giá trị tính được:

<div class="bbcode_description">HTML Code:
n 1 2 3 4 5 6 7
l(n) 1 1 1 4 56 9408 16942080
</div>