Thuật toán liên quan đến random

#1

Em có ví dụ như này: Có mảng A = {1,3,5,6};. Giờ lập một mảng B có 10 phần tử đều là của A, và phải có đầy đủ tất cả phần tử của A. Ko rõ e diễn đạt rõ ràng chưa. Các bác rảnh share e cái thuật toán với. Nghĩ mãi vẫn cứ lì não :sweat_smile:

#2

mảng A có mấy phần tử bạn?

#3

mảng A đã nếu trên rồi đó bạn. Example hard code luôn. Tổng quát sau :smiley:

#4

Ko biết đúng ý bạn ko :c

Đầu tiên random tất cả các phần tử của A vào B.
Sau đó random các số trong A vào chỗ trống còn lại là ok :blush:

for i=0, i<A.size(), i++
  B[rand() % B.size()] = A[i]; 
for i=0, i<B.size(), i++
  if(B[i] == NULL) //giả xử như B[i] chưa có giá trị đặt vào thì sinh giá trị bằng cách chọn ngẫu nhiên 1 số trong A
    B[i] = A[rand()% A.size()];
1 Like
#5

Chưa chuẩn, Mình ví dụ trong cái B[rand() % B.size()] có thể random lặp, thì cái A[i] cũ thay bằng cái A[i] mới.

1 Like
#6

Thêm 1 if + while là đc rồi :c

2 Likes
#7

Mình nghĩ chiến lược cho bài này là trước tiên là mình chọn ra 4 vị trí trước (để ném 4 thằng 1 3 5 6 vào trước đảm bảo có đủ phần tử của A) sau đó 6 vị trí còn lại thì ném lung tung thôi (mỗi vị trí còn lại có thể chọn phần tử nào cũng được).
tính thử thì có 10C4 * 4! * 4^6.
Mà không biết mảng A có phần tử trùng thì có sao không.

1 Like
#8

A ko có phần tử trùng. Mình cũng từng nghĩ cách ép đủ 4 phần tử đã, rồi random sau. Nhưng cảm giác kiểu như thê ko hoàn toàn là random nữa :smiley:

#11

Mình dùng NULL để mô tả v thôi ‘3’
Chứ 1 số ngôn ngữ sẽ hiểu NULL = 0 nên ko xài đc.
-> 1 là dùng số nào đó mà đề ko đụng vào để đánh dấu. (Ví dụ như mảng A toàn số lớn hơn 0 thì chọn đại 1 số âm)
2 là dùng mảng đánh dấu vị trí này đã có giá trị ^^.

2 Likes
#12

Tks bác. e nghĩ là chuẩn rồi :smiley:

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?