01/10/2018, 14:04
Chọn ngẫu nhiên phần tử trong C++
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 …
Bài liên quan
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 à.
Suy nghĩ rắc rối quá, nếu theo mình hiểu thi sẽ là thế này:
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]
Knuth:
std::random_shuffle()Một thuật toán cho tổ hợp:
stackoverflow.com
Algorithm to select a single, random combination of values?
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.
Cảm ơn mọi người nhé để mình test thử