PDA

View Full Version : Hỏi về bài toán: tổ hợp!



dongcambiz
19-01-2012, 12:45
Cho n (n<=10) học sinh (các tên đôi một khác nhau) và 1 số k (k<=n); Hãy liệt kê tất cả các cách chọn k học sinh trong n học sinh.
Ví dụ với n=4, k=2 và 4 tên học sinh như sau:

Hùng
Huy
Hân
=> Ta có 6 cách chọn 2 học sinh như sau:
1. Hà Hùng
2. Hà Huy
3. Hà Hân
4. Hùng Huy
5. Hùng Hân
6. Huy Hân
===========Xin các bạn hướng dẫn. Thanks a lot!

HGMinh95
20-01-2012, 22:31
Bài này bạn chỉ cần dùng quay lui như sau:

1 tổ hợp có dạng như sau: a[1], a[2], a[3], ... a[k] với a[i] là thứ tự trong ds học sinh (ký hiệu S) của phần tử thứ i trong hoán vị.

Để tránh trùng hợp, bạn chỉ xét các tổ hợp có a[i] > a[i-1]
-> Thuật toán:
Đầu tiên, chọn 1 phần tử trong S, lưu vào a[1]; với mỗi cách chọn phần tử a[1] tiếp tục chọn 1 phẩn tử trong S lưu vào a[2] sao cho a[2] > a[1]... tiếp tục như vậy cho -> tạo được 1 tổ hợp -> in ra màn hình

thienha20
21-01-2012, 13:08
arrten=array(...);
for i:1->n-1
for j:i+1->n
print(arrten[i] va arrten[j])

HGMinh95
21-01-2012, 20:32
arrten=array(...);
for i:1->n-1
for j:i+1->n
print(arrten[i] va arrten[j])
Bạn hiểu sai đề rồi, k ko nhất thiết phải bằng 2 đâu