注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

罗维的博客

{ 关注机器学习、计算广告、自然语言处理、大规模数据处理等 }

 
 
 
 
 

日志

 
 

随机数的生成  

2010-03-16 23:35:47|  分类: 算法设计 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

问题描述:

        现要求产生 0~n-1 范围内的 m 个随机整数的有序列表,且不允许重复,m <= n。

        考虑到 n 的值可能很大,而通常 C/C++ 提供的随机数产生器所能返回的随机数在 [0,RAND_MAX],其中,RAND_MAX 为 0x7FFF。也就是说只有 15 位的随机性。因此,我们需要要有自己的随机数产生器,以便能够返回更多位数的随机数,通常为 30 位。下面的函数可以满足我们的要求:

int bigrand()
{
return (RAND_MAX * rand() + rand());
}

注意,这里也可以采用将第一个 rand() 的返回值左移 15 位,然后加上第二个 rand() 的返回值的方法来提速。

        下面,我们就可以用这个随机数产生器来解决上面的问题了。看到这里,你是不是想到了什么解决方法呢。下面的方法来自算法大师 Donald Knuth。

void genknuth(int m, int n)
{
srand((unsigned int)time(NULL));

for(int i = 0; i < n; i++)
{
   if((rand() % (n - i)) < m)
   {
    cout<<i<<"\n";
    m--;
   }
}
}

其中的 srand 语句是我为了在每次运行时能够得到不同的随机数序列而加的。

         不知道这个方法有没有出乎你的意料,算上 for 循环才 4 句话。不过,就是这 4 句话,已经很完美地解决了上面提出的问题,有序、互异、m 个数。

        这个方法通过顺序扫描 0~n-1 范围内的每个数保证产生的随机数有序和互异。

        那产生 m 个数怎么保证呢?又没有类似循环的语句来控制产生的随机数的个数。

        要记住,程序语句只是我们实现某种功能的一种表现形式,这也就是说,我们要实现某种功能,可以由很多种表现形式。下面就来分析一下这个方法是如何保证能够产生 m 个随机数的。

         想必大家都已经看到产生的随机数都是在 if 语句中输出的,那也就是说 if 语句控制了产生的随机数的个数。因此,要说明能够产生 m 个随机数,只要说明 if 语句能够执行且仅能执行 m 次。

         首先,在 for 循环没有推出的情况下,if 语句最多能够执行 m 次,因为 if 语句的每次执行都会使 m 的值减 1,当 m=0 时,if 语句就不会再执行了。因为 (rand() % (n - i)) 是一个非负数。

         其次,我们分析 if 语句最少能够执行多少次。如果 if 语句开始一直得不到执行,那么 (n-i) 便会一直减小,直到与 m 相等。这时 (rand() % (n - i)) 一定小于 (n-i),也就是 m,从而使得 if 语句得到一次执行。而此时 for 循环已经执行了 (n-m+1) 次,离推出循环只剩下 (m-1) 次,要使得 if 语句能够执行 m 次,那么接下来的 (m-1) 次循环 if 语句必须都得能够执行。事实是什么样的呢?第一次 if 语句开始执行时,(n-i)=m,执行完时,(n-i) 和 m 都减少 1,从而仍然有 (n-i)=m 成立。这个过程一直持续到 m=0。刚好是 m-1 次。

         因此,我们可以相信 if 语句确实能够执行且只能执行 m 个。

        Donald Knuth 实在是太厉害了!

        顺便说一句,据说在大学期间,有关程序设计之类的比赛,只要有他参加,第一名非他莫属。

  评论这张
 
阅读(544)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017