Đề bài: Nhập vào danh sách n bạn nam và n bạn nữ in tất cả các cách xếp 2n người đó vào 1 bàn tròn. Biết bạn nam và bạn nữ phải xếp xen kẽ nhau.
Phân tích
Giả sử mỗi cách xếp hoàn chỉnh 2n bạn là 1 cấu hình. Ta dùng số chẵn biểu diễn vị trí cho bạn nam và số lẻ biểu diễn vị trí cho bạn nữ.
- Khi xếp bạn nam
- Vì mỗi ghế trống trong bàn tròn tương đương nhau. Bạn nam thứ n sẽ chỉ tạo ra 1 cách xếp cho cấu hình
- Bạn nam thứ (n-1) sẽ tạo ra (n-1) cách xếp cho cấu hình
- Bạn nam thứ (n-2) sẽ tạo ra (n-2) cách xếp cho cấu hình
…
=> Tương tự như vậy, khi xếp xong ta sẽ có tất cả (n-1)! cấu hình
- Khi xếp bạn nữ
- Vì đã có 1 bạn nam thứ n làm mốc nên bạn nữ thứ n sẽ tạo ra n cách xếp cho cấu hình
- Bạn nữ thứ (n-1) sẽ tạo ra (n-1) cách xếp cho cấu hình
- Bạn nữ thứ (n-2) sẽ tạo ra (n-2) cách xếp cho cấu hình
…
=> Tương tự như vậy khi xếp xong ta sẽ có tất cả n! cấu hình
Tóm lại: Ta có tất cả (n-1)!n! cấu hình
Thuật toán
- Ta xây dựng một mảng coi như là 1 cái bàn tròn (vì khi ta uốn thẳng một đường tròn ra thì nó cũng tương tự nhau:grinning:)
- Mảng có 2*k+2 phần tử (Dư 2 phần tử không in ra nhưng có tác dụng hỗ trợ cho thuật toán, cái này mình sẽ nói sau)
- Ta sinh hoán vị các phần tử ở vị trí chẵn. Với mỗi phần tử ở vị trí chẵn ta sinh hoán vị tiếp n! cấu hình các phẩn tử ở vị trí lẻ.
Giờ mình sẽ quay lại giải thích cái 2 phần tử dư ra. Giờ bạn hãy nhớ lại bài toán sinh hoán vị n phần tử. Khi đó ta duyệt từ cuối lên đầu mảng để tìm đoạn cuối giảm dần dài nhất -> Chính yêu cầu này sẽ khiến bạn tạo dư ra 1 phần tử. Mà mình tạo ra 2 cái n như thế thì sẽ dư 2 phần tử
Code
Link: https://ideone.com/slxRKB
Trên đây là cách giải bài toán của mình theo phương pháp sinh. Bài toán hoàn toàn có thể giải bằng thuật toán quay lui nhá. Rất mong nhật được sự góp ý vè thuật toán cũng như tối ưu Code từ các pro.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?