产生1-5的随机函数，生成随机数1-7_飞蚂蚁哥哥

http://blog.sina.com.cn/u/2729323945

首页博文目录关于我

个人资料

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：

博客访问：
关注人气：
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

产生1-5的随机函数，生成随机数1-7

(2013-08-20 00:34:32)

标签：

随机函数1-5

生成

随机数1-7

分类：编程算法

需求：已知函数f()生成1-5的随机数，求用f()生成1-7的随机数。

先上代码，再说思路。

#include <iostream>
#include <cstdlib> //rand
#include <vector> //vector<int>
#include <algorithm> //count
#include <cmath> //pow
using namespace std;

//generate 1~5
int rand15()
{
  return 1 + rand() % 5;
}

//generate 0~1
int rand01()
{
  int r = rand15();
  if (r == 3)
  return rand01();
  if (r < 3)
  return 0;
  else
  return 1;
};

//algorithm 1 of generating 1~7
int rand17_1()
{
  int r = 0;
r += rand01();
r += rand01() << 1;
r += rand01() << 2;
  if (r == 0)
  return rand17_1();
  else
  return r;
}

//algorithm 2 of generating 1~7
int rand17_2()
{
  int a;
  while ((a = rand15() * 5 + rand15()) > 26) ;
  return (a - 3) / 3;
}

//algorithm 3 of generating 1~7
int rand17_3()
{
  int sum = 0;
  for (int i = 0; i < 7; i++)
{
sum += (rand15() - 1) * pow(5, i);
}
  return (sum % 7 + 1);
}

int main()
{
  vector < int >ivec;
ivec.resize(100000);

cout << "algorithm 1:" << endl;
  for (int i = 0; i < 100000; ++i)
ivec[i] = rand17_1();
  for (int i = 1; i <= 7; ++i)
cout << i << " counts: " << count(ivec.begin(), ivec.end(), i) << endl;

cout << "algorithm 2:" << endl;
  for (int i = 0; i < 100000; ++i)
ivec[i] = rand17_2();
  for (int i = 1; i <= 7; ++i)
cout << i << " counts: " << count(ivec.begin(), ivec.end(), i) << endl;

cout << "algorithm 3:" << endl;
  for (int i = 0; i < 100000; ++i)
ivec[i] = rand17_2();
  for (int i = 1; i <= 7; ++i)
cout << i << " counts: " << count(ivec.begin(), ivec.end(), i) << endl;

  return 0;
}

算法1的思路

比如产生7的过程如下：

r = 1;

r = 1+2;

r = 3+4;

该算法来自：http://blog.sina.com.cn/s/blog_9ce5a1b50101ae1z.html

算法二的思路

1. 通过 rand5()*5+rand5() 产生 6 7 8 9 10 11 …… 26，27 28 29 30 这25个数，每个数的出现机率相等；

2. 只需要前面 3*7 个数，所以舍弃后面的4个数；

3. 将 6 7 8 转化为 1，9 10 11 转化为 2，……，24 25 26 转化为 7。公式是 (a-3)/3；

该算法来自：http://bbs.chinaunix.net/archiver/tid-1740087.html?page=1

另外，关于该算法的延伸思考：

这种思想是基于，rand()产生[0,N-1]，把rand()视为N进制的一位数产生器，那么可以使用rand()*N+rand()来产生2位的N进制数，以此类推，可以产生3位，4位，5位...的N进制数。这种按构造N进制数的方式生成的随机数，必定能保证随机，而相反，借助其他方式来使用rand()产生随机数(如 rand5() + rand()%3 )都是不能保证概率平均的。

此题中N为5，因此可以使用rand5()*5+rand5()来产生2位的5进制数，范围就是6到30。再去掉27-30，剩余的除3，以此作为rand7()的产生器。

该段思考来自于：http://blog.csdn.net/xwdpepsi/article/details/8092860

算法三的思路

不明思路，看代码去吧。

来自：和算法二同一出处。

三种算法的随机效果PK

http://s15/mw690/a2ae2da9zx6BZclfPj07e&690

100000 / 7 = 14285.7

可见算法3的波动范围最小。

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：再论C/C++的多行字串（带空格、回车）输入

后一篇：Guake Terminal修改宽度，居左显示，去掉边框

新浪BLOG意见反馈留言板　欢迎批评指正