Mình đang gặp vấn đề ở ngẫu nhiên khi làm cố gắng test thử sắp xếp số sinh viên vào một lớp với yêu cầu là
n/m (với n là số sinh viên và m là số lớp cần xếp sinh viên vào )
ví dụ nếu n=100 sinh viên và m= 3 thì phải chia đều ra 30 , 30 ,30 còn 10 sinh viên còn lại sắp xếp đều vào 3 nhóm nếu nhóm nhóm 1 đủ 30 người thì sẽ cho sinh viên vào nhóm một nữa và nhóm hai cũng vậy đến trường hợp còn 10 mới bát đầu chia đều 3 nhóm .
mở rộng ra các trường hợp n= 100 và m =5 …
Chọn ngẫu nhiên phần tử trong C++
Mình không hiểu đề lắm, theo bạn diễn tả thì chẳng phải chia lấy nguyên và chia lấy dư là xong sao??. B có thể post cả cái đề lên cho mọi người cùng xem
không cái câu hỏi là ý tưởng của mình
ví dụ mình nhập 100 học sinh thì mình cho số lớp học là 3 đi
mình muốn chia đều học sinh vào 3 lớp đó mà vấn đề là chổ radom mình cho radom chạy từ 1>3 nhưng nếu lớp 1 đầy 30 học sinh mình muốn cho radom bắt đầu từ 2 chia đều cho 3 thì còn lại phần dư thì chia đều nữa
Dùng cái Knutt shuffle lấy hẳn 33 luôn chứ làm gì nhiêu khê vậy 
mô phỏng bốc thăm à.
2 Likes
Suy nghĩ rắc rối quá, nếu theo mình hiểu thi sẽ là thế này:
- Cho hàm random chạy 1 3, ra 1 số bốc học sinh vào lớp mang số đó, biến đếm
- Check nếu giá trị biến đếm của lớp đó = 30( giá trị tùy chỉnh ) thì đưa vào danh sách loại trừ
- Random lại check nếu random ra giá trị trong danh sách loại trừ thì random lại đến khi không giống thì thực hiện lại các bước trên
Chuẩn nhất thì [quote=“rogp10, post:4, topic:61006”]
Dùng cái Knutt shuffle lấy hẳn 33 luôn chứ làm gì nhiêu khê vậy
[/quote]
2 Likes
Knuth: std::random_shuffle()
Một thuật toán cho tổ hợp:
Thực ra hai thuật toán ngang nhau O(k) mem phụ, nhưng Knutt dễ viết hơn.
Knuth cơ bản là xử lí tại chỗ. Khi phải giữ nguyên thứ tự thì ta sẽ phải cần k slot mem nữa. Bây giờ ta cần O(k) cặp (key := rand(i, n), val := i) để nhớ khi swap, đặt chúng vào tree. Vậy là O(k) mem.
2 Likes
Cảm ơn mọi người nhé để mình test thử
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?