专栏首页python3从rand(5)生成rand(7),从r

从rand(5)生成rand(7),从r

 我们先来看这样一个问题, 已知rand5能等概率产生1, 2, 3, 4, 5, 现要用rand5来实现rand7(rand7的意思是要等概率产生1, 2, 3, 4, 5, 6, 7), 该怎么搞呢? 我看了一下网上资料, 很多都是凑出来一个结果, 没有什么过程思路, 我觉得虽然结果正确, 但总感觉所用的技巧性太强。 所以, 在文本中, 我也来凑凑热闹, 看看该如何下手, 并给出程序的实际验证结果。

        我们看看rand5 + rand5 行不行。 rand5 + rand5 的结果是2, 3, 4, 5, 6, 7, 8, 9, 10, 稍微思考一下, 就知道, 这些数肯定不是等概率的, 比如2的概率要低于5的概率。 所以, 不靠谱。 我们再来看看, 既然有了1, 2, 3, 4, 5,  那很容易就有10, 20, 30, 40, 50, 且是等概率的。   假设现在又有另外一个fun函数, 能等概率随机生成0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 那么, 我们不就很轻易地构造了等概率的10, 11, 12, 13, ....., 59么? 没错, 思路就是这样的。

        所以, 我们先要让rand5产生等概率的间距数组(比如上述的10, 20, 30, 40, 50,), 然后让rand5产生连续的待插入数字(比如上述的0, 1, 2, ..., 9,). 现在问题是, 要多大的间距才合适呢? 其实也很简单, 要让0, 1, 2, 3, 4刚好能插入到间距数组中。

        到这里, 就比较俗套了:

        第一步: 用rand5产生等概率的0, 1, 2, 3, 4,准备插入到下一步的等间距数组中, 使得插入后, 刚好合适。

        第二步: 用rand5产生等概率的0, 1, 2, 3, 4,  然后为了被插入, 将其散开成0, 5, 10, 15, 20.

        第三步: 将第一步插入 到第二步中, 于是, 就形成了0, 1, 2, 3, 4, 5, 6, 7, 8, ..., 20, 21, 22, 23, 24.  然后就很容易等概率地生成1, 2, 3, 4, 5, 6, 7了。

#include <iostream>
#include <ctime>
using namespace std;

// 随机生成1-n之间的整数
int myRandom(int n)
{
	return rand() % n + 1;
}

// 随机生成1, 2, 3, 4, 5
int rand5()
{
	return myRandom(5);
}

int main() 
{
	int i = 0;
	int n = 5;
	int a[100] = {0};
	srand(time(NULL));

	// 测试100万次
	for(i = 0; i < 1000000; i++)
	{
		a[rand5() - 1]++;
	}

	// 结果
	for(i = 0; i < n; i++)
	{
		cout << a[i] << endl;
	}

	return 0;
}

结果为:

199771 200063 200057 200602 199507

      我们看到, 每个数字接近 20万次, 还算均匀。 下面, 我们用上面的rand5来生成rand7, 我们已经给出了算法, 所以下面直接给出代码和测试结果:

#include <iostream>
#include <ctime>
using namespace std;

// 随机生成1-n之间的整数
int myRandom(int n)
{
	return rand() % n + 1;
}

// 随机生成1, 2, 3, 4, 5
int rand5()
{
	return myRandom(5);
}

// 仅由rand5来构造rand7
int rand7()
{
	while(1)
	{
		// 构造等概率的0, 1, 2, 3, 4, 5, 6, 6, 7, 8, ..., 20, 21, 22, 23, 24
		int x = (rand5() - 1) * 5 + (rand5() - 1);
		
		if(x >= 21) // 剔除21, 22, 23, 24
		{
			continue; 
		}
		else
		{
			return x % 7 + 1;
		}
	}
}

int main() 
{
	int i = 0;
	int n = 7;
	int a[100] = {0};
	srand(time(NULL));

	// 测试700万次
	for(i = 0; i < 7000000; i++)
	{
		a[rand7() - 1]++;
	}

	// 结果
	for(i = 0; i < n; i++)
	{
		cout << a[i] << endl;
	}

	return 0;
}

结果:

1000030 999648 1000338 1000311 999814 1000323 999536

      还算均匀吧, OK, 本文就到此为止了, 代码很简单, 思路才重要。 有兴趣的朋友可以看看《算法导论》第五章的内容。

原文:http://blog.csdn.net/stpeace/article/details/46672035

其实上面的rand(7)也可以用来生成rand(3),下面是我修改的代码

int rand31()
{
    while (1) {
        int x =(rand5()-1)*5 + (rand5()-1);
        if(x >= 24){
            continue;
        }else{
            return  x%3+1;
        }
    }
}

选取0-23作为区间,大于24时继续

下面是结果

332754

333669

333577

还比较均匀。。。。 

当然了,rand(3)应该有更简洁的方法,试试再说。。。。

相关链接:http://www.cnblogs.com/dwdxdy/archive/2012/07/28/2613135.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C语言 基础题

    第1题 int sum_nth(unsigned int num, unsigned int n); 功  能:求出给定自然数的指定位置的数字(个位为0,十位为...

    py3study
  • [开发]Python实现运维监控服务器硬

          今天通过使用Python开发针对服务器硬件运行状态的监控,简单了解下在虚拟环境中的运维监控的实现,算是给全面研究云计算开一个头。

    py3study
  • python核心数据类型 -- 数字类

    python3.0不再支持字典比较大小,可用sorted(dict.items())替代

    py3study
  • 指针在数组中的数据传递作用

    用户5166556
  • 1062 最简分数 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • Java工具集-支持各种类型快速排序工具

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    cwl_java
  • 递归

    版权声明:本文为博主原创文章,转载请注明博客地址: https://blog.csdn.ne...

    zy010101
  • LeetCode215.数组中的第K个最大元素

    mathor
  • LeetCode 684. 冗余连接(并查集)

    输入一个图,该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间,这条附加的边不属于树中已存...

    Michael阿明
  • 算法复杂度分析

    为什么要进行算法分析? 预测算法所需的资源 计算时间(CPU 消耗) 内存空间(RAM 消耗) 通信时间(带宽消耗) 预测算法的运行时间 在给定输入规模时,所执...

    前朝楚水

扫码关注云+社区

领取腾讯云代金券