Sinh số ngẫu nhiên khi hàm chuẩn (!) không đáp ứng

ntthcmus · July 4, 2018, 7:41am

void nhapMang(int *a, int n)
{
srand(time(NULL));
for (int i = 0; i < n; i++)
{
a[i] = rand()%1000000 + 1;
}
printf("\n");
}

em muốn ramdom 1 mảng gồm 1 triệu phần tử khác nhau nhưng khi ra kq thì phần từ max là 32767 và trùng lặp rất nhiều trong khi em biết miền giá trị int là hơn 2 triệu phần tử .Vậy thì như thế là tại sao và em phải làm như thế nào (máy e chạy visual 2015 64bit kiểm tra thì sizeof(int) = 4 bytes)

Nguyen_Hieu1 · July 4, 2018, 7:01am

Tại vì hàm rand() có giá trị từ 0 đến RAND_MAX. Bạn có thể kiểm tra giá trị RAND_MAX( trong thư viện ) bằng cách print ra thôi. Còn giải quyết thì mình chẳng có cách gì hay chỉ có cách cùi cùi này thôi

    int sum;
    for (int i = 0; i < n; i++)
    {
    	sum = 0;
    	for(int j = 0; j < 30; j++)
    	{
    		sum += rand();
    	}
    	a[i] = sum;	// Vì sum không vượt quá 32767*30 = 983 010 nên không cần chia lấy dư cho 1000000
    }

rogp10 · July 4, 2018, 7:39am

B1: chơi hẳn một mảng từ 1 đến 1 triệu
B2: tìm bài GoodPracticeRNG lấy code về dùng thay (chứ giờ sao)
B3: dùng Knuth shuffle.
B4: ???
B5: profit!

testuser · July 4, 2018, 1:31pm

Thông minh
mình cũng tìm được sự phức tạp của ví dụ khác
Question
Sign in to vote
0
Sign in to vote
wjhwong wrote:

May I know how to generate 64 bit random number using rand()?

What’s the code?

Here is a simple polynomial-based random number generator that produces 32
bits at a time. You can call it twice and combine the values:

__int64 rand64() {
return ((__int64)(xorshift())<<32)|xorshift();
}
 
//...
 
static unsigned long
x=123456789,
y=362436069,
z=521288629,
w=88675123,
v=886756453;
/* replace defaults with five random seed values in calling program */
 
unsigned long xorshift(void)
{
unsigned long t = x^(x>>7);
x=y; y=z; z=w; w=v;
v=(v^(v<<6))^(t^(t<<13));
return (y+y+1)*v;
}
 
#include <stdio.h>
 
int
main()
{
int i;
for( i = 0; i < 25; i++ )
printf( "%08x\n", xorshift() );
}

–
Tim Roberts, [email protected]
Providenza & Boekelheide, Inc.

Tim Roberts, DDK MVP

tntxtnt · July 4, 2018, 1:32pm

do trong VC++ RAND_MAX là 32767 (15 bit) nên nó ko random số lớn hơn 32767 được, có thể khắc phục bằng cách ghép 2 số lại:

int rand2() //kết quả là 1 số 30 bit ~ max là 1 tỷ
{
    int a = rand();
    int b = rand();
    return (a << 15) | b;
}
...
a[i] = rand2() % 1000000 + 1;

hoặc viết đại 1 cái hàm random khác:

static unsigned __minstd_rand_state = 0; //biến toàn cục

void minstd_srand(unsigned seed)
{
    __minstd_rand_state = seed;
}

unsigned minstd_rand()
{   //https://en.cppreference.com/w/cpp/numeric/random/linear_congruential_engine
    //https://en.wikipedia.org/wiki/Lehmer_random_number_generator#Sample_C99_code
    return __minstd_rand_state = 48271u * __minstd_rand_state % 2147483647u;
}

...

int main()
{
    //gọi srand 1 lần ở đây, ngay sau khi khai báo main
    minstd_srand(time(0));

...

a[i] = minstd_rand() % 1000000 + 1;

hoặc xài xorshift như code ở post phía trên có lẽ chất lượng random tốt hơn 1 tí