使用函数rand5()来实现函数rand7()


题目描述:给你一个能生成1到5随机数的函数,用它写一个函数生成1到7的随机数。
分析:这题是面试产品经理的时候被出的(产品经理也能碰到算法题也是很醉)。然后当时想的是类似抽签的办法,把1~7分布到一个二维数组里面,然后用rand5()生成下标随机访问不同位置的元素,直到生成1~7之间的数。解决办法的主要思路是构造一个更大的等概率值域空间。查了一下,除了用矩阵之外,还有线性变换和位运算两种解法。感觉线性变换最通用。
1)矩阵法
可以生成一个5*5的矩阵,所以共有25个元素可供随机挑选,由于最接近25的7的倍数是21,所以在矩阵中填充1~7,每个数字出现3次。使用rand5()来随机选取二维数组的下标得到1~7之间的随机整数。代码如下:
    int matrix[5][5];
    memset(matrix, 0m sizeof((matrix)));
    memset(matrix, 0, sizeof(matrix));
    int (*p)[5] = matrix;
    int *q = *p;
    for(int i = 1; i <= 7; i++)
    {
          for(int j = 0; j < 3; j++)
          {
                *q = i;
                q++;
          }
    }

   int rand7()
   {
        int x;
        do
        {
             x = matrix[rand5() - 1][rand5() - 1]; 
        }while(x == 0);
        return x;
   }


2)位运算
把生成的随机数看成二进制串,利用rand5()构造一个随机生成0、1的函数rand01。然后对于每一位调用rand01,将结果拼接得到1~7之间的随机数。代码如下:
// 等概率生成0,1
int rand01()
{
int i = rand5();
while(i > 4) 
{
    i = rand5();
}
return i % 2;
}
// 二进制加法
int bitAdd(int a,int b){
      if(b==0){
         return a;
      }
      int sum,carry;
      sum=a^b;
      carry=(a&b)<<1;
      return Add(sum,carry);
}

// 等概率生成 1~7
int rand7()
{
   int x;
   int high, mid, low;
   do{
       high = rand01() << 2;
       mid = rand01() << 1;
       low = rand01();
       x =  bitAdd(bitAdd(high, mid), low);
   }while(x == 0);
   return x;
}


3)通用解法
由rand5()生成rand7()的线性变换解法分析可以参考快课网,我觉得这篇文章写的很好。
问题的变式为:给你一个随机生成a到b的函数, 用它去实现一个随机生成c到d的函数。
可以先考虑由生成[3,10]的随机函数rand310得到生成[5,7]的随机函数rand57,经过类似的推导可以设计出通用算法如下:
随机函数生成算法:
已知给定随机函数函数Randab可以生成a到b的函数,构造随机函数Randcd。
步骤1:如果a<c且b>d,或者a>d且b>d,进入步骤2;否则,构造Randab2=(b-a+1)*Randab + Randab,表示生成a2=(b-a+1)*a+a到b2=(b-a+1)*b+b之间的数。如果a2,b2仍不满足前述条件,继续构造Randab3=(b-a+1)*Randab2+Randab...,直到ak,bk满足前述条件。这时我们得到Randabk,我们记为RandAB。
步骤2:根据步骤1得到的RandAB,满足A<c且B>d,或者A>d且B>d。我们通过如下代码构造Randcd:
//prerequisition: B>d && (A<c || A>d)
int Randcd(){
    int res = ~(1<<31); // res = INT_MAX
    int delta = d-c+1;
    while( (x < delta*ceil(A*1.0/delta)) || (x>delta*(B/delta) - 1) )
         x = RandAB();
    return x % delta + c;
}

不知道这个通用算法设计的是否正确,请各位大大指教。

P.S.: 不知道为啥添加代码后发布出来换行都不起作用了,正常的代码请戳简书第8题
已邀请:

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~