产生1百万个不重复的随即数

产生1百万个不重复的随即数

    目前,我们想到的,共有三种方法。

方法1:逐个产生这些随机数,每产生一个,都跟前面的随机数比较,如果重复,就重新产生。

方法2:在上面的所述方法中,不进行比较,只要反过来,按顺序产生这些数,但随机产生它们的位置。如产生100个100以内不重复随机数的代码:

int a[100];

for(i=0; i<=99; ++i) a[i]=i;

for(i=99; i>=1; --i) 

swap(a[i], a[rand()%i]);

首先第二行按顺序用0到99填满整个数组;第三行随机产生从0到m-2个数组下标,把这个下标的元素值跟m-1下标的元素值交换,一直进行到下标为1的元素。因此它只需要遍历一次就能产生全部的随机数。

所以,运用我们这个思想,我们的程序如下所示:

#include "iostream"

#include "string"

#include "stdlib.h"

#include "fstream"

using namespace std;

static const int num=100000;

int main()

{

ofstream out("C:\\Rand.doc");

int *a[10];

for(int x=0;x<10;x++)

{

   a[x] = new int [num];

}

/*

int a[0][num],a[1][num],a[2][num],a[3][num],a[4][num];

int a[5][num],a[6][num],a[7][num],a[8][num],a[9][num];

在栈在没有这么多的空间

*/

for(int j=0;j<10;j++)

for(int i=j*num; i<=(num-1)+j*num; ++i) 

switch(j){

    case 0:a[j][i-j*num]=i;

 break;

    case 1:a[j][i-j*num]=i;

 break;

    case 2:a[j][i-j*num]=i;

 break;

 case 3:a[j][i-j*num]=i;

 break;

 case 4:a[j][i-j*num]=i;

 break;

 case 5:a[j][i-j*num]=i;

 break;

 case 6:a[j][i-j*num]=i;

 break;

 case 7:a[j][i-j*num]=i;

 break;

 case 8:a[j][i-j*num]=i;

 break;

 case 9:a[j][i-j*num]=i;

 break;

         }//switch

//如上程序是产生数据个

//如下程序是将产生的个数据进行随机交换

int m,n;

for(int j=10;j>=0;j--)

for(int i=j*num-1;i>=(j-1)*num+1; i--)

 switch(j){

        case 10:

  m=rand()%i;

  n=m/100000;

     switch(n){//第二个switch

        case 0:

     swap(a[9][i%num],a[0][m%num]); 

     break;

           case 1:

     swap(a[9][i%num],a[1][m%num]);

     break;

     case 2:

     swap(a[9][i%num],a[2][m%num]);

     break;

     case 3:

     swap(a[9][i%num],a[3][m%num]);

     break;

     case 4:

     swap(a[9][i%num],a[4][m%num]);

     break;

     case 5:

     swap(a[9][i%num],a[5][m%num]);

     break;

     case 6:

     swap(a[9][i%num],a[6][m%num]);

     break;

     case 7:

     swap(a[9][i%num],a[7][m%num]);

     break;

     case 8:

     swap(a[9][i%num],a[8][m%num]);

     break;

     case 9:

     swap(a[9][i%num],a[9][m%num]);

     break;

  }//switch

     break;

        case 9:

  m=rand()%i;

  n=m/100000;

     switch(n){//第二个switch

        case 0:

     swap(a[8][i%num],a[0][m%num]); 

     break;

           case 1:

     swap(a[8][i%num],a[1][m%num]);

     break;

     case 2:

     swap(a[8][i%num],a[2][m%num]);

     break;

     case 3:

     swap(a[8][i%num],a[3][m%num]);

     break;

     case 4:

     swap(a[8][i%num],a[4][m%num]);

     break;

     case 5:

     swap(a[8][i%num],a[5][m%num]);

     break;

     case 6:

     swap(a[8][i%num],a[6][m%num]);

     break;

     case 7:

     swap(a[8][i%num],a[7][m%num]);

     break;

     case 8:

     swap(a[8][i%num],a[8][m%num]);

     break;

  }//switch

     break;

  case 8:

  m=rand()%i;

  n=m/100000;

     switch(n){//第二个switch

        case 0:

     swap(a[7][i%num],a[0][m%num]); 

     break;

           case 1:

     swap(a[7][i%num],a[1][m%num]);

     break;

     case 2:

     swap(a[7][i%num],a[2][m%num]);

     break;

     case 3:

     swap(a[7][i%num],a[3][m%num]);

     break;

     case 4:

     swap(a[7][i%num],a[4][m%num]);

     break;

     case 5:

     swap(a[7][i%num],a[5][m%num]);

     break;

     case 6:

     swap(a[7][i%num],a[6][m%num]);

     break;

     case 7:

     swap(a[7][i%num],a[7][m%num]);

     break;

  }//switch

     break;

  case 7:

  m=rand()%i;

  n=m/100000;

     switch(n){//第二个switch

        case 0:

     swap(a[6][i%num],a[0][m%num]); 

     break;

           case 1:

     swap(a[6][i%num],a[1][m%num]);

     break;

     case 2:

     swap(a[6][i%num],a[2][m%num]);

     break;

     case 3:

     swap(a[6][i%num],a[3][m%num]);

     break;

     case 4:

     swap(a[6][i%num],a[4][m%num]);

     break;

     case 5:

     swap(a[6][i%num],a[5][m%num]);

     break;

     case 6:

     swap(a[6][i%num],a[6][m%num]);

     break;

  }//switch

     break;

  case 6:

  m=rand()%i;

  n=m/100000;

     switch(n){//第二个switch

        case 0:

     swap(a[5][i%num],a[0][m%num]); 

     break;

           case 1:

     swap(a[5][i%num],a[1][m%num]);

     break;

     case 2:

     swap(a[5][i%num],a[2][m%num]);

     break;

     case 3:

     swap(a[5][i%num],a[3][m%num]);

     break;

     case 4:

     swap(a[5][i%num],a[4][m%num]);

     break;

     case 5:

     swap(a[5][i%num],a[5][m%num]);

     break;

  }//switch

     break;

  case 5:

  m=rand()%i;

  n=m/100000;

     switch(n){//第二个switch

        case 0:

     swap(a[4][i%num],a[0][m%num]); 

     break;

           case 1:

     swap(a[4][i%num],a[1][m%num]);

     break;

     case 2:

     swap(a[4][i%num],a[2][m%num]);

     break;

     case 3:

     swap(a[4][i%num],a[3][m%num]);

     break;

     case 4:

     swap(a[4][i%num],a[4][m%num]);

     break;

  }//switch

     break;

  case 4:

  m=rand()%i;

  n=m/100000;

     switch(n){//第二个switch

        case 0:

     swap(a[3][i%num],a[0][m%num]); 

     break;

           case 1:

     swap(a[3][i%num],a[1][m%num]);

     break;

     case 2:

     swap(a[3][i%num],a[2][m%num]);

     break;

     case 3:

     swap(a[3][i%num],a[3][m%num]);

     break;

  }//switch

     break;

  case 3:

  m=rand()%i;

  n=m/100000;

     switch(n){//第二个switch

        case 0:

     swap(a[2][i%num],a[0][m%num]); 

     break;

           case 1:

     swap(a[2][i%num],a[1][m%num]);

     break;

     case 2:

     swap(a[2][i%num],a[2][m%num]);

     break;

  }//switch

     break;

  case 2:

  m=rand()%i;

  n=m/100000;

     switch(n){//第二个switch

        case 0:

     swap(a[1][i%num],a[0][m%num]); 

     break;

           case 1:

     swap(a[1][i%num],a[1][m%num]);

     break;

  }//switch

     break;

  case 1:

  m=rand()%i;

  n=m/100000;

     switch(n){//第二个switch

        case 0:

     swap(a[0][i%num],a[0][m%num]); 

     break;

  }//switch

     break;

    }//switch

for(int j=0;j<10;j++)

for(int i=0;i<num;i++)

switch(j){

      case 0:

   out<<a[0][i]<<" ";

   break;

   case 1:

   out<<a[1][i]<<" ";

   break;

   case 2:

   out<<a[2][i]<<" ";

   break;

   case 3:

   out<<a[3][i]<<" ";

   break;

   case 4:

   out<<a[4][i]<<" ";

   break;

   case 5:

   out<<a[5][i]<<" ";

   break;

   case 6:

   out<<a[6][i]<<" ";

   break;

   case 7:

   out<<a[7][i]<<" ";

   break;

   case 8:

   out<<a[8][i]<<" ";

   break;

   case 9:

   out<<a[9][i]<<" ";

   break;

  }//switch

}

之所以如此分割成10个文件,主要是考虑到数组太大,可能放不下。如果内存足够大,也可以直接如下:

#include "iostream"

#include "string"

#include "stdlib.h"

#include "fstream"

using namespace std;

static const int num=1000000;

int main()

{

ofstream out("C:\\Rand.doc");

int *a;

for(int x=0;x<10;x++)

{

   a= new int[num];

}

for(int i=0;i<=num-1; ++i) 

   a[i]=i;

for(int i=num-1; i>=1; --i) 

 swap(a[i],a[rand()%i]);

for(int j=0;j<num;j++)

out<<a[j]<<" ";

}

说明:处理如此大的数据,只能在堆上进行。

      还有,取余和除法操作类似,第二个操作数不能为零。

方法3:原理跟上面例子相似,但效率差点:

int a[100]={0};

int i, m;

for(i=1; i<=99; ++i)

{

while(a[m=rand()%100]);

a[m] = i;

}

这段代码也是随机产生位置,但它预先把整个数组初始化为0,然后随机产生其中一个位置,如果该元素值为0,表示这个位置还没有被使用过,就把i赋予它;否则,就重新随机产生另一个位置,直到整个数组被填满。这个方法,越到后面,遇到已使用过的元素的可能性越高,重复次数就越多,这是不及第一个方法的地方,但总的来说,效率还是不错的。

附:系统提供的随机数函数

1、产生一个随机数(从0到32767)

srand((unsigned) time(NULL)); //为了提高不重复的概率,用系统时间

rand(); //产生随机数

2、产生从m到n的随机数(包括m,不包括n)

srand((unsigned) time(NULL)); //为了提高不重复的概率

rand()%(n-m+1)+m;        //使用时将m和n换为具体数

参考:

1、百度搜索,思想来源于百度博客文章,源地址丢失,谢谢原作者

产生1百万个不重复的随即数产生1百万个不重复的随即数 hopegrace 发布了110 篇原创文章 · 获赞 23 · 访问量 7870 私信 关注
上一篇:3982: 猴子选大王


下一篇:第二次实验2