Lấy ngẫu nhiên n số không trùng, với trung bình cộng bằng 1 số cho trước (2 người xem)

ptm0412 · 4/1/17

Có 1 bài toán thế này:

Some one on fb đã viết:
Hiện tại em cần viết một hàm lấy ngẫu nhiên n số trong 300 số cho trước, điều kiện là các số không trùng nhau và trung bình cộng n số đó bằng 1 hằng số

Tôi đề nghị 1 thuật toán như thế này:

- Đặt 1 biến Avr = trung bình cộng cho trước, n = số lượng số cần tìm, X = số lượng số cho trước
- Lấy ngẫu nhiên số đầu tiên
- Tìm số thứ 2 bằng Avr x 2 - số thứ 1. Nếu không có số chính xác thì lấy số gần nhất
- Lấy ngẫu nhiên số thứ 3, điều kiện khác 2 số trên
- Tìm số thứ 4 giống cách tìm số thứ 2, điều kiện khác 3 con phía trên
- Lập lại đến khi có n - 1 con số
- Tìm con số thứ n = trung bình của các số phía trước
- Trường hợp tìm thấy: kết thúc
- Trường hợp không tìm thấy: Lặp lại từ đầu.
- Lặp một số lần vẫn không thấy thì ngưng.

Tôi tranh thủ viết 1 đoạn:
- Chưa bắt trùng
- Không tìm thấy thì lấy kết quả gần gần giống (sai số trung bình cộng nhỏ hơn 1)
- Kết quả: chưa lần nào được kết quả chính xác

Các bạn có hứng thú thì làm giúp (tại tôi bận quá không giúp bạn ấy được)

File đính kèm:
Cột A chứa 300 con số ngẫu nhiên
B1 là số lượng số cần lấy
B2 trở xuống là kết quả
C1 là trung bình cộng mong muốn
D1 là trung bình cộng của kết quả
E1 là số đếm duy nhất của kết quả
F1 là thời gian chạy

ptm0412 · 4/1/17

Ghi chú:

- Tìm số thứ 2 bằng Avr x 2 - số thứ 1. Nếu không có số chính xác thì lấy số gần nhất

Có thể là 1 bài toán nhỏ

doveandrose · 4/1/17

ủa vậy có khác gì với việc chọn ngẫu nhiên các số sao cho có tổng là B1 x C1 không ta ?

ptm0412 · 4/1/17

doveandrose đã viết:
ủa vậy có khác gì với việc chọn ngẫu nhiên các số sao cho có tổng là B1 x C1 không ta ?

Không khác (đương nhiên, hỏi hơi thừa). Vấn đề là:
- Mỗi lần chạy phải ra 1 bộ kết quả không giống lần chạy trước
- Mỗi bộ là những số không trùng
- Các thành phần của bộ kết quả lấy từ 300 con số ban đầu, 300 con đó là số ngẫu nhiên và có thể đang trùng

Con số trung bình mong muốn phải nằm trong 1 phạm vi nào đó mới có thể ra kết quả (dù đúng hay gần đúng). Ngoài phạm vi đó kết luận ngay là không có đáp án.

Lưu ý: Các bạn có thể dùng thuật toán khác

huuthang_bd · 4/1/17

ptm0412 đã viết:
Không khác (đương nhiên, hỏi hơi thừa). Vấn đề là:
- Mỗi lần chạy phải ra 1 bộ kết quả không giống lần chạy trước
- Mỗi bộ là những số không trùng
- Các thành phần của bộ kết quả lấy từ 300 con số ban đầu, 300 con đó là số ngẫu nhiên và có thể đang trùng

Con số trung bình mong muốn phải nằm trong 1 phạm vi nào đó mới có thể ra kết quả (dù đúng hay gần đúng). Ngoài phạm vi đó kết luận ngay là không có đáp án.

Lưu ý: Các bạn có thể dùng thuật toán khác

Chỗ in đậm tùy thuộc vào dữ liệu đầu vào. Nếu chỉ có 1 bộ số thỏa điều kiện thì chạy lần nào cũng chỉ có 1 bộ đó thôi, đòi bộ khác thì... không có. Có khi một bộ số thỏa điều kiện còn không có thì lấy đâu mỗi lần một bộ.

Bài toán này gần giống với bài toán tìm các số có tổng bằng một cho trước (đã có vài bài trên diễn đàn) nhưng khống chế số lượng phần tử.
Vì yêu cầu mỗi lần chạy ra một bộ kết quả khác nhau (ngẫu nhiên) nên theo tôi bài này phải làm theo hướng như sau:

1. Tìm tất cả các bộ n số thỏa điều kiện (tổng của n số bằng tích của n và trung bình cộng đã cho)
2. Chọn ngẫu nhiên một bộ số trong tập hợp các bộ số tìm được.

Vì phải tìm tất cả các bộ số nên phải dùng thuật toán vét cạn cho đến hết (không có điều kiện thoát khi thỏa ĐK). Nếu tập số có số lượng phần tử lớn thì có lẽ sẽ rất lâu.

Theo tôi thuật toán đề xuất ở bài 1 là chưa hợp lý. Giả sử chỉ có một bộ số thỏa điều kiện thì chỉ cần lấy một số ngoài bộ số thỏa ĐK là đi sai đường ngay.
Ví dụ cho bộ số gồm 1000 số từ 1 đến 1000, tìm bộ 2 số có trung bình cộng bằng 2 (tổng bằng 4). Dễ thấy chỉ có bộ (1, 3) là thỏa điều kiện, nếu số đầu tiên được chọn ngẫu nhiên thì xác suất chọn trúng số trong bộ số thỏa điều kiện là 2/1000. Nếu yêu cầu tìm bộ 1 số có trung bình cộng là 100 thì xác suất là 1/1000.

VetMini · 4/1/17

Bài này thuộc loại khó. Nói cho đúng thì nó tuỳ thuộc vào suy luận thuật toán bao quát hơn Excel/VBA nói riêng hay lập trình nói chung.

Trư thuật toán vét cạn ra, khong có thuật toán nào khác bảo đảm tìm được đáp án 100%. Vì vậy thuật toán chúng ta nêu ra chỉ gồm những cách TRÁNH BỚT lạc đường, và GIẢM THIỂU con số bí lối

Gọi S là tổng cần kiếm của N số. Và Ni, Si là số đã lấy được và tổng của chúng ở giai đoạn i

Thuật toán của tôi sẽ bao gồm những thuật toán sau đây:
1. chọn số ngẫu nhiên trong mảng số. Thuật toán này có nghĩa là đặt các số vào mảng rồi dùng chỉ số để chọn
2. điều chỉnh mảng số. Cái này chia ra 2 phần
2.1. loại các số đã chọn
2.2. loại các số không thể chọn. Chỉ có thể chọn được những số x + (n-ni) <= S - Si
Để thực hiện thuật toán 2.1, tôi thêm thuật toán đánh dấu chỉ số (0 là còn chọn được, 1 là không chọn được)
Để có thể đạt điều 2.2 dễ dàng, tôi thêm thuật toán sắp xếp mảng tăng dần.

Thuật toán phụ, dùng để chọn lại nếu bị trùng. Có 2 cách:
1. random chọn lại, cách này giản dị nhưng có khả năng chạy hoài khong dứt
2. chọn số kế, bên phải, nếu vẫn bị trùng thì chọn bên trái, và cứ vậy.

huuthang_bd · 4/1/17

VetMini đã viết:
2.2. loại các số không thể chọn. Chỉ có thể chọn được những số x + (n-ni) <= S - Si

Mọi chuyện sẽ trở nên rất phức tạp nếu tập hợp có số âm.

VetMini · 4/1/17

huuthang_bd đã viết:
Mọi chuyện sẽ trở nên rất phức tạp nếu tập hợp có số âm.

Theo luật Đại Số (hoặc Giải Tích, tuỳ theo con toán ứng dụng) thì số âm sẽ trở thành số dương nếu ta áp dụng phép dời trục toạ độ

huuthang_bd · 4/1/17

VetMini đã viết:
Theo luật Đại Số (hoặc Giải Tích, tuỳ theo con toán ứng dụng) thì số âm sẽ trở thành số dương nếu ta áp dụng phép dời trục toạ độ

Ờ ha. Trường hợp này số phần tử của tập con là cố định nên có thể sử dụng phép dời trục tọa độ để xử lý số âm vì ta có thể xác định tổng theo trục tọa độ mới.

Xin hỏi anh thêm, nếu không giới hạn số phần tử của tập con thì áp dụng phép dời trục tọa độ trong trường hợp đó như thế nào hoặc có phương pháp nào khác không?

VetMini · 4/1/17

Thực ra thì áp dụng phép dời trục toạ độ cũng hơi phức tạp. Hình như trên mạng cũng có 1 vài hàm tổng quát để làm việc này (ngôn ngữ C)

Trong trường hợp của đề bài này, điểm cốt yếu là ta cần biết trước một đường đi nào đó sẽ tắt nghẽn để khỏi phí công đi sâu thêm. Vì vậy nếu có số âm thì quy luật để biết trước đường sẽ tắt nghẽn là "tổng (N-Ni) số lớn nhất còn lại" sẽ không đủ để bù vào chỗ còn thiếu (S-Si); hoặc "tổng (N-Ni) số nhỏ nhất còn lại" sẽ không đủ để bù vào chỗ dư (Si-S).

Theo tôi thì thuật toán đoán trước sẽ khá quan trọng bởi vì bạn có thể dùng nó cho cả trường hợp vét cạn. Có những đường tổ hợp vét cạn có thể được bỏ qua sớm hơn nếu đoán được, ở thời điểm Ni nó chắc chắn khong dẫn đến kết quả.

doveandrose · 4/1/17

VetMini đã viết:
Thực ra thì áp dụng phép dời trục toạ độ cũng hơi phức tạp. Hình như trên mạng cũng có 1 vài hàm tổng quát để làm việc này (ngôn ngữ C)

Trong trường hợp của đề bài này, điểm cốt yếu là ta cần biết trước một đường đi nào đó sẽ tắt nghẽn để khỏi phí công đi sâu thêm. Vì vậy nếu có số âm thì quy luật để biết trước đường sẽ tắt nghẽn là "tổng (N-Ni) số lớn nhất còn lại" sẽ không đủ để bù vào chỗ còn thiếu (S-Si); hoặc "tổng (N-Ni) số nhỏ nhất còn lại" sẽ không đủ để bù vào chỗ dư (Si-S).

Theo tôi thì thuật toán đoán trước sẽ khá quan trọng bởi vì bạn có thể dùng nó cho cả trường hợp vét cạn. Có những đường tổ hợp vét cạn có thể được bỏ qua sớm hơn nếu đoán được, ở thời điểm Ni nó chắc chắn khong dẫn đến kết quả.

chỗ màu đỏ hình như hơi lạ lạ anh nhỉ ? có nên dùng từ khác điền vào chỗ đó chăng +-+-+-+

ptm0412 · 5/1/17

huuthang_bd đã viết:
Theo tôi thuật toán đề xuất ở bài 1 là chưa hợp lý. Giả sử chỉ có một bộ số thỏa điều kiện thì chỉ cần lấy một số ngoài bộ số thỏa ĐK là đi sai đường ngay.
Ví dụ cho bộ số gồm 1000 số từ 1 đến 1000, tìm bộ 2 số có trung bình cộng bằng 2 (tổng bằng 4). Dễ thấy chỉ có bộ (1, 3) là thỏa điều kiện, nếu số đầu tiên được chọn ngẫu nhiên thì xác suất chọn trúng số trong bộ số thỏa điều kiện là 2/1000. Nếu yêu cầu tìm bộ 1 số có trung bình cộng là 100 thì xác suất là 1/1000.

Đồng ý với Thắng. Tuy nhiên khi tìm số thứ 1 (số thứ lẻ) tôi kiểm tra nó phải nhỏ hơn số trung bình x 2. Trong thí dụ "tìm bộ 2 số có trung bình cộng bằng 2 (tổng bằng 4)" tôi sẽ tìm số thứ nhất với điều kiện nhỏ hơn 4. Số thứ 2 (số thứ chẵn) sẽ đi tìm số = 4 - số thứ nhất

HieuCD · 5/1/17

ptm0412 đã viết:
Đồng ý với Thắng. Tuy nhiên khi tìm số thứ 1 (số thứ lẻ) tôi kiểm tra nó phải nhỏ hơn số trung bình x 2. Trong thí dụ "tìm bộ 2 số có trung bình cộng bằng 2 (tổng bằng 4)" tôi sẽ tìm số thứ nhất với điều kiện nhỏ hơn 4. Số thứ 2 (số thứ chẵn) sẽ đi tìm số = 4 - số thứ nhất

nếu bộ số bắt đầu từ 5 tìm 2 số có trung bình là 7 thì cách xác định điều kiện sẽ khác nhiều

huuthang_bd · 5/1/17

ptm0412 đã viết:
Đồng ý với Thắng. Tuy nhiên khi tìm số thứ 1 (số thứ lẻ) tôi kiểm tra nó phải nhỏ hơn số trung bình x 2. Trong thí dụ "tìm bộ 2 số có trung bình cộng bằng 2 (tổng bằng 4)" tôi sẽ tìm số thứ nhất với điều kiện nhỏ hơn 4. Số thứ 2 (số thứ chẵn) sẽ đi tìm số = 4 - số thứ nhất

Anh xét kiểu này cũng không ổn. Đổi lại yêu cầu là tìm bộ 2 số có TB cộng là 999 thì cũng vậy thôi.

Ba Tê · 5/1/17

Chạy thí thí theo đề và file bài #1, nếu yêu cầu khác nữa thì thua.

PHP:

Public Sub GPE()
Dim Dic As Object, tArr(), sArr(), dArr(), Tong As Long, R As Long
Dim I As Long, J As Long, K As Long, N As Long, Num As Long
Set Dic = CreateObject("Scripting.Dictionary")
tArr = Range("A2", Range("A2").End(xlDown)).Value
R = Range("B1").Value
Tong = Range("C1") * R
ReDim sArr(1 To UBound(tArr), 1 To 1)
For I = 1 To UBound(tArr)
    If Not Dic.Exists(tArr(I, 1)) Then
        K = K + 1: Dic.Add tArr(I, 1), ""
        sArr(K, 1) = tArr(I, 1)
    End If
Next I
For N = 1 To 100000
    Num = 0: Dic.RemoveAll
    ReDim dArr(1 To 50, 1 To 1)
    For I = 1 To 50
    Do
        Randomize
        J = Int((K * Rnd) + 1)
        If Not Dic.Exists(J) Then
            Dic.Add J, ""
            Num = Num + sArr(J, 1)
            If Num > Tong Then Exit Do
            dArr(I, 1) = sArr(J, 1)
            Exit Do
        End If
    Loop
    Next I
    If Tong = Num Then Exit For
Next N
Range("M1:M1000").ClearContents
If Num = Tong Then
    Range("M1").Resize(R) = dArr
    MsgBox "Da tim duoc.", , "GPE"
Else
    MsgBox "Chua tim thay, Thu lai lan nua xem sao.", , "GPE"
End If
Set Dic = Nothing
End Sub

ptm0412 · 5/1/17

huuthang_bd đã viết:
Anh xét kiểu này cũng không ổn. Đổi lại yêu cầu là tìm bộ 2 số có TB cộng là 999 thì cũng vậy thôi.

HieuCD đã viết:
nếu bộ số bắt đầu từ 5 tìm 2 số có trung bình là 7 thì cách xác định điều kiện sẽ khác nhiều

Tôi viết là tìm số thứ nhất với điều kiện nhỏ hơn số trung bình x 2, nếu trung bình là 7 thì tìm số thứ nhất phải nhỏ hơn 14, nếu trung bình 999 thì phải tìm số nhỏ hơn 1998 cơ mà? Nếu lấy ngẫu nhiên 1 số >=14 thì không cần tìm số thứ 2 mà phải tìm ngẫu nhiên lại, ý tôi là vậy.

Ngoài ra trong bài phía trên tôi cũng nói là cần kiểm tra số trung bình trước khi đi tìm kết quả, nếu số trung bình ngoài phạm vi nào đó thì báo "vô nghiệm" luôn, khỏi tìm. (Thí dụ điều kiện là Min bộ số < số trung bình < max bộ số

huuthang_bd · 5/1/17

ptm0412 đã viết:
Tôi viết là tìm số thứ nhất với điều kiện nhỏ hơn số trung bình x 2, nếu trung bình là 7 thì tìm số thứ nhất phải nhỏ hơn 14, nếu trung bình 999 thì phải tìm số nhỏ hơn 1998 cơ mà? Nếu lấy ngẫu nhiên 1 số >=14 thì không cần tìm số thứ 2 mà phải tìm ngẫu nhiên lại, ý tôi là vậy.

Ngoài ra trong bài phía trên tôi cũng nói là cần kiểm tra số trung bình trước khi đi tìm kết quả, nếu số trung bình ngoài phạm vi nào đó thì báo "vô nghiệm" luôn, khỏi tìm. (Thí dụ điều kiện là Min bộ số < số trung bình < max bộ số

Tất cả các số trong bộ số từ 1 đến 1000 đều < 1998. Xác suất để chọn trúng số 998 hoặc 1000 là 2/1000. Ý em là vậy.

VetMini · 6/1/17

Trước đó tôi có đề cập một phương pháp kiểm tra sớm là sắp xếp mảng số, tìm tổng của N số lớn nhất, tổng của N số nhỏ nhất. Và khi bắt đầu tìm thì tiếp tục theo dõi tổng N-Ni số lớn, N-Ni số nhỏ.

Có thể thêm một thuật toán "ăn gian" là khi Ni = N-1 (tức là còn 1 số cuối) thì cứ duyệt chuỗi còn lại mà tìm số đó.

doveandrose · 6/1/17

VetMini đã viết:
Trước đó tôi có đề cập một phương pháp kiểm tra sớm là sắp xếp mảng số, tìm tổng của N số lớn nhất, tổng của N số nhỏ nhất. Và khi bắt đầu tìm thì tiếp tục theo dõi tổng N-Ni số lớn, N-Ni số nhỏ.

Có thể thêm một thuật toán "ăn gian" là khi Ni = N-1 (tức là còn 1 số cuối) thì cứ duyệt chuỗi còn lại mà tìm số đó.

Để em múa minh họa cho anh Vetmini vậy . Để đơn giản ta sẽ dùng mảng đã xếp sẵn , đã loại bỏ trùng lặp .

VetMini đã viết:
đường sẽ tắt nghẽn là "tổng (N-Ni) số lớn nhất còn lại" sẽ không đủ để bù vào chỗ còn thiếu (S-Si)

Ta xây dựng sẵn mảng cố định có n phần tử . Thí dụ n = 50
Như vậy khi ta gom được 48 số , ta sẽ kiểm tra tổng s48 với 2 số lớn nhất trong dãy ban đầu , nếu >= tổng mong muốn thì tiếp tục đi tìm 2 số còn thiếu , ngược lại nghỉ khỏe . Để đỡ phải tính đi tính lại , ta đẩy 2 số lớn nhất đó qua bên phải dấu >= luôn

Mã:

Private Function CreateMaxAb(arr, limit As Long, jackpots As Long)
Dim dArr, r As Long, tmpSum, k As Long
ReDim dArr(1 To limit, 1 To 1) As Long
k = limit
For r = UBound(arr) To UBound(arr) - limit + 1 Step -1
    tmpSum = tmpSum + arr(r, 1)
    dArr(k, 1) = jackpots - tmpSum
    k = k - 1
Next
CreateMaxAb = dArr
End Function

và dùng phương pháp đệ quy

Mã:

Public Sub Solve(arr, ub As Long, limit As Long, i As Long, j As Long, tmpSum As Long, rsArr)
'algorithms by Vetmini
If Not ExitGame Then
    Dim r As Long, nextI As Long
    If i < limit - 1 Then
        nextI = i + 1
        If tmpSum >= MaxAbArr(nextI, 1) Then   '[COLOR=#000000][I]đường sẽ tắt nghẽn là "tổng (N-Ni) số lớn nhất còn lại" sẽ không đủ để bù vào chỗ còn thiếu (S-Si)[/I][/COLOR]
            For r = j + 1 To ub - limit + nextI Step 1
                rsArr(nextI, 1) = arr(r, 1)
                Solve arr, ub, limit, nextI, r, tmpSum + arr(r, 1), rsArr
            Next
        End If
    Else   '[COLOR=#000000][I]Có thể thêm một thuật toán "ăn gian" là khi Ni = N-1 (tức là còn 1 số cuối) thì cứ duyệt chuỗi còn lại mà tìm số đó.[/I][/COLOR]
        For r = j + 1 To ub Step 1
            If tmpSum + arr(r, 1) = jackpots Then
                Dim k As Long
                rsArr(i + 1, 1) = arr(r, 1)


                curCol = curCol + 1
                fnArr(1, curCol) = "=AVERAGE(R[+1]C:R[+" & limit & "]C)"
                For k = 1 To UBound(rsArr) Step 1
                    fnArr(k + 1, curCol) = rsArr(k, 1)
                Next
                If curCol = rsQty Then
                    ExitGame = True
                    MsgBox "good boy"
                End If
                Exit For
            End If
        Next
        
    End If
End If
End Sub

để đơn giản ta chỉ lấy 200 kết quả đầu tiên tìm được .
Việc kiểm tra

VetMini đã viết:
(N-Ni) số nhỏ nhất còn lại vượt quá chỗ dư (Si-S)

em thấy không cần thiết ở bài này , chỉ như trên là đủ .
Hoặc muốn có sự thay đổi rõ rệt giữa các lần chạy ta có thể chọn trước 1 số bất kì , rồi áp dụng cách trên đi tìm 49 số còn lại .

Gió Đông · 6/1/17

Cái này như chủ topic muốn kiểu ma số thì phải?

Lấy ngẫu nhiên n số không trùng, với trung bình cộng bằng 1 số cho trước (2 người xem)

Người dùng đang xem chủ đề này

Bad Excel Member

File đính kèm

Bad Excel Member

hello

Bad Excel Member

Chuyên gia GPE

Ăn cùng góc phố

Chuyên gia GPE

Ăn cùng góc phố

Chuyên gia GPE

Ăn cùng góc phố

hello

Bad Excel Member

Chuyên gia GPE

Chuyên gia GPE

Cạo Rồi Khỏi Gội

File đính kèm

Bad Excel Member

Chuyên gia GPE

Ăn cùng góc phố

hello

File đính kèm

BĂNG TRÔI

Đếm ngược thời gian