Thread: Bài toán xếp n người vào bàn tròn !!

Đề rất đơn giản, cho n người, hãy in ra các cách sắp xếp n người vào bàn tròn.
Vd : n = 4
Kết quả :
1 2 3 4
1 3 4 2
1 4 2 3
P/s : Mong được đóng góp nhiều ý tưởng hay và sáng tạo

Bài này khó đó Tuấn kết quả sai rồi kìa!
Ngồi bàn tròn mà:
Vd: 1432 và 1234
là 2 cấu hình hoàn toàn giống nhau chỉ có điều khác chiều thôi. Bài toán nay mong nhiều ý kiến từ các cao thủ

Về tin học thì anh không rành lắm nhưng về toán tổ hợp, phép đếm cho bài toán này được thực hiện theo thuật toán là chọn một người bất kì xếp vào 1 vị trí bất kì sau đó hoán vị n-1 người còn lại tức là có (n-1)! cách xếp.
Cái này chắc chuyên Tin tụi em cũng biết rồi. Nói thừa

Originally Posted by o0DarkLord0o

Về tin học thì anh không rành lắm nhưng về toán tổ hợp, phép đếm cho bài toán này được thực hiện theo thuật toán là chọn một người bất kì xếp vào 1 vị trí bất kì sau đó hoán vị n-1 người còn lại tức là có (n-1)! cách xếp.
Cái này chắc chuyên Tin tụi em cũng biết rồi. Nói thừa

Vậy theo anh thì với n = 4 có 3! = 6 cách xếp, nhưng mà 2 chiều điều tính là 1 nên số cách xếp giảm đi 1 nữa @@

WAO cũng không hiểu rõ lắm, search trên mạng thấy khác chiều vẫn được xem là 2 cấu hình khác nhau. Số cách đúng bằng (N-1)!. Vì là bàn tròn nên sẽ có một người làm tâm, gọi là vị trí cố định để người khác "xoay" theo.
- Giả sử ở ví trí 1 ta chọn 1 người làm vị trí cố định, sẽ có đúng 1 cách chọn.
- Vị trí thứ 2 có N-1 cách chọn, thứ 3 có N-2 cách chọn...thứ N cuối cùng chỉ còn lại 1 cách xếp.
Vị chi ta có tất cả (N-1)! cách xếp.

Bài toán này có thể giải bằng chu trình haminton, có nghĩa là từ tên 1, ta duyệt các cách khác nhau qua các tên còn lại theo trình tự nhỏ->lớn. Duyệt hết cấu hình thì đủ! (Nhiều người hay gọi đây là thuật toán "ziczac" đi giống lắm nếu vẽ ra bàn tròn).

@Mangan:
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
Giả sử đã xếp xong chẳng hạn, chọn vị trí người số 1 ngồi là tâm và bắt đầu đếm thì sẽ có 6 cách như trên. Ý em "số cách xếp giảm đi 1 nữa" là sao? VD với trường hợp lấy 2 làm tâm thì trình tự 2 - 3 - 4 - 1 vẫn không khác đi trong trường hợp bàn tròn.

Là do hồi sáng hỏi thầy kêu 2 chiều vẫn tính 1 cấu hình, nghĩa là đọc theo chiều ngược kim đồng hồ hay cùng chiều kim đồng hồ vẫn là 1, như 1234 với 4321 ý nên em nói cấu hình giảm đi 1 nữa là vậy, còn theo WAO nói 2 chiều vẫn tính là 2 cấu hình khác nhau thì chắc thầy bị nhầm lẫn @@
P/s : Thức khuya cho tâm hồn bay cao