/********************************************\
| 欢迎转载, 但请保留作者姓名和原文链接, 祝您进步并共勉! |
\********************************************/
非“伪”随机数的生成
作者: Jerry Cat
时间: 2006/05/16
链接:
http://www.cppblog.com/jerysun0818/archive/2006/05/16/7232.html
问题的来由 - "随机取m个数(在1到n的范围之内),(m <= n),要求m个数没有重复。有没有
什么好的算法,时间复杂度和空间复杂度都很好"
----------------------------------------------------------------
方案一:
取随机数可以用C++标准的rand,至于M个不重复,你可以用std::set来解决,把取道的随机数
插入到set里面,set的size() == m就可以了, 具体可以这样:
#include <set>
#include <stdlib.h>
int main()
{
std::set<int> s;
while(1)
{
int r = rand() % n;
s.insert(r);
if(s.size() == m)
{
break;
}
}
}
由于set底层实现是红黑树,插入复杂度是对数级的^_^
----------------------------------------------------------------
方案二:
#include <iostream>
#include <cstdlib> //用于rand()和srand()函数
#include <ctime> //设置不同的随机数
using namespace std;
int main (){
srand( time( 0 ) ); //调用不重复的随机数函数
unsigned i;
for ( int n = 0; n++ < 10; )
{
i = rand() ; //对i 赋系统的随机数
cout << " The NO." << n << "is : " << i << endl;
}
return 0;
}
1. C++标准函数库提供一随机数生成器rand,返回0-RAND_MAX之间均匀分布的伪随机整数。 RAND_MAX
必须至少为32767。rand()函数不接受参数,默认以1为种子(即起始值)。
随机数生成器总是以相同的种子开始,所以形成的伪随机数列也相同。失去了随机意义。
2. C++中另一函数srand(),可以指定不同的数(无符号整数变元)为种子。但是如果种子相同,伪
随机数列也相同。--一个办法是让用户输入种子,但是仍然不理想。
3. 比较理想的是用变化的数,比如时间来作为随机数生成器的种子。
在 头文件ctime中时间库包含time函数,它可以返回一个表示时间、日期、月和年的数值使用如
下调用可将该值设为rand的种子
srand(static_cast<unsigned>(time(static_cast<time_t*>(NULL))));
4. 但, srand()并不是说使随机数都不一样,它只是使取随机数的种子随着时间而改变:)
So, 还是方案一好!
posted on 2006-05-16 00:17
Jerry Cat 阅读(2500)
评论(7) 编辑 收藏 引用