Trang 2 trên tổng số 2 Đầu tiênĐầu tiên 12
Từ 11 tới 13 trên tổng số 13 kết quả

Đề tài: Làm thế nào để tạo được số ngẫu nhiên có n chữ số ???

  1. #11
    Ngày gia nhập
    01 2013
    Bài viết
    1,477

    Mặc định Làm thế nào để tạo được số ngẫu nhiên có n chữ số ???

    Chọn một số trong (x0, x0+eps] thì (double) rand() / RAND_MAX * eps + x0 sẽ cho phân bố đều hơn khi delta lớn.

  2. #12
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    469

    Giải pháp của mình (mà đúng hơn, code của mình, còn phương pháp là mình sưu tầm từ đâu đó) (link đã dẫn), cho ví dụ bằng số ở #9 trên, là lấy r/2 với r phân bố đều trong khoảng [0,200). Với rand() phân bố đều trong khoảng [0,256), những giá trị rand() >= 200 sẽ bị vứt bỏ, nghĩa là 200/256 ~ 80% giá trị của rand() có thể lấy dùng làm r.

    Dĩ nhiên khi đã có r đạt yêu cầu thì công thức r%100 hoàn toàn cũng có thể dùng được. Nhưng do các hàm rand() kém chất lượng thường cung cấp các bit cao tốt hơn (ngẫu nhiên hơn) các bit thấp, dùng công thức r/2 có thể sẽ tốt hơn.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  3. #13
    Ngày gia nhập
    07 2011
    Bài viết
    429

    Trích dẫn Nguyên bản được gửi bởi prog10 Xem bài viết
    Chọn một số trong (x0, x0+eps] thì (double) rand() / RAND_MAX * eps + x0 sẽ cho phân bố đều hơn khi delta lớn.
    cast thành double là sai lầm lớn đó. Ví dụ như trong VC++ RAND_MAX chỉ là 32767 thì ta có thể xét với mọi giá trị thuộc [0, 32767]

    C++ Code:
    1. #include <iostream>
    2. #include <iomanip>
    3. #include <cstdlib>
    4.  
    5. const int SIZE = 10;
    6.  
    7. int main()
    8. {
    9.     int count[SIZE] = {};
    10.     for (int i = 0; i <= RAND_MAX; ++i)
    11.     {
    12.         double x = static_cast<double>(i) / (RAND_MAX + 1);
    13.         count[static_cast<int>(x * SIZE)]++;
    14.     }
    15.     for (int i = 0; i < SIZE; ++i)
    16.         std::cout << i << ": " << count[i] << "\n";
    17. }
    kết quả thu được là
    0: 3277
    1: 3277
    2: 3277
    3: 3277
    4: 3276
    5: 3277
    6: 3277
    7: 3277
    8: 3277
    9: 3276

    có vấn đề ngay: từ chỗ uniform mỗi số xuất hiện 1 lần trong đoạn 0-32767, bây giờ ta thu được kết quả ko đều trong đoạn 0-9: số 4 và số 9 xuất hiện ít hơn 1 lần. Ít hơn 1/3277 có thể bỏ qua, nhưng nếu ta tăng SIZE thành 10000 thì bây giờ ta thu được kết quả khủng khiếp hơn trong đoạn 0-9999:
    0: 4
    1: 3
    2: 3
    3: 4
    4: 3
    5: 3
    6: 3
    7: 4
    8: 3
    9: 3
    ...
    sai số 33%. Quá khủng khiếp. Ko thể cast thành double rồi nhân lên lại được.


    Trích dẫn Nguyên bản được gửi bởi Ada Xem bài viết
    Giải pháp của mình (mà đúng hơn, code của mình, còn phương pháp là mình sưu tầm từ đâu đó) (link đã dẫn), cho ví dụ bằng số ở #9 trên, là lấy r/2 với r phân bố đều trong khoảng [0,200). Với rand() phân bố đều trong khoảng [0,256), những giá trị rand() >= 200 sẽ bị vứt bỏ, nghĩa là 200/256 ~ 80% giá trị của rand() có thể lấy dùng làm r.

    Dĩ nhiên khi đã có r đạt yêu cầu thì công thức r%100 hoàn toàn cũng có thể dùng được. Nhưng do các hàm rand() kém chất lượng thường cung cấp các bit cao tốt hơn (ngẫu nhiên hơn) các bit thấp, dùng công thức r/2 có thể sẽ tốt hơn.
    cách này đúng nè, nhưng chạy lâu vì bỏ qua nghĩa là phải rand() lại, có thể rand() lại vô tận (trong lý thuyết), nhưng nói chung là chậm
    .
    .
    .
    .
    .
    .
    .
    .
    ví dụ bạn A viết 1 hàm sinh số ngẫu nhiên rd10k() trong đoạn 0-9999 (10000 số) để quyết định drop rate của boss, 15% drop rate nghĩa là rd10k() < 1500, 16.67% drop rate nghĩa là rd10k() < 1667. Đây là code:
    C Code:
    1. #include <stdio.h>
    2. #include <stdlib.h>
    3. #include <time.h>
    4.  
    5. int rd10k() { return rand() % 10000; }
    6.  
    7. int main()
    8. {
    9.     srand(time(0));
    10.     int N = 1000000;
    11.     int chance = 1500; // 15% chance
    12.     int success = 0;
    13.     for (int i = 0; i < N; ++i) success += rd10k() < chance;
    14.     printf("%.2f%%\n", success * 100.0f / N);
    15.     return 0;
    16. }

    compile với gcc và clang, ngon lành, kết quả thử 1 triệu lần chạy là 15.03%. Ngon lành.

    vác code này qua compile với VC, bùm, nó biến thành 18.34%. Tăng N lên 10 triệu cũng vậy. Tại sao??

    như Ada đã nói ở trên thì là do RAND_MAX ko chia hết cho 10000, nên kết quả rand() % 10000 ko đều, sẽ có số xuất hiện nhiều hơn số khác. Do RAND_MAX trong gcc hay clang là 2^31 - 1 nên nếu viết code lướt hết hơn 2 tỷ số này chia lấy dư cho 10000 thì mỗi số xuất hiện cỡ 214748 lần, nhưng với các số từ 0-3647 xuất hiện 214749 lần. Sai số là 1/214748, ko nhiều, nên chạy code compile bằng gcc hay clang cho kết quả "đúng" là 15%.

    nhưng ở VC thì khác. RAND_MAX là 32767. Vì sao VC lại chọn RAND_MAX nhỏ như vậy? Vì (lại) như Ada đã nói, các hàm random thường sinh "các bit cao tốt hơn (ngẫu nhiên hơn) các bit thấp", nên VC bỏ 16 bit thấp giữ lại 16 bit cao, nên RAND_MAX mới nhỏ như vậy. Và vấn đề khi chia % 10000 xảy ra ở đây: 0-2767 số đầu tiên xuất hiện 4 lần, 2768-9999 xuất hiện chỉ có 3 lần. Sai số khủng khiếp 33% dẫn tới code trên ko cho kết quả 15% mà cho kết quả 18.XX%. Nhưng tại sao là ~18%? Random 1 triệu lần, chia cho 32767 ~ 30.5 lần nghĩa là những số nhỏ hơn 2767 xuất hiện ~4 * 30.5 = 122 lần, 122 nhân 1500 = 183000, chia 1 triệu cho ra ~18.3%.

    cách fix (nhớ đọc đâu đó trên stackoverflow, chôm về chỉnh sửa tí):
    C Code:
    1. #include <stdio.h>
    2. #include <stdlib.h>
    3. #include <time.h>
    4.  
    5. int randint(int a, int b) //uniform int in range [a, b]
    6. {
    7.     int range = b - a + 1;
    8.     int buckets = RAND_MAX / range;    // 0........|........|........|....RAND_MAX
    9.     int limit = buckets * range;       //                            ^ limit
    10.     int x;
    11.     do x = rand(); while (x >= limit); // [0........|........|........]|....RAND_MAX
    12.     return x / buckets + a;
    13. }
    14.  
    15. int rd10k() { return randint(0, 9999); }
    16.  
    17. int main()
    18. {
    19.     srand(time(0));
    20.     int N = 1000000;
    21.     int chance = 1500; // 15% chance
    22.     int success = 0;
    23.     for (int i = 0; i < N; ++i) success += rd10k() < chance;
    24.     printf("%.2f%%\n", success * 100.0f / N);
    25.     return 0;
    26. }

    cũng như Ada nói thì nó lấy x / buckets chứ ko lấy % range vì bit cao chất lượng tốt hơn bit thấp.

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn