粉笔面试——生成随机数(根据rand7()生成rand10())

今天面试并不是太顺利，一连好几个题都摸不着头脑，所以记录一下。

• 已知:

  rand7() 得到0-6

• 求：

  rand10()

  0-9

想法

朴素想法：(X)

• rand7() -> rand10()
• rand7()只能生成0-6
• 所以rand10() = rand7+ rand7%4;
• 不对.因为 rand10() = 2, 可能有多种组合,一个是0和2,还有一个2和0,还有1和1;
• 但是rand10()=9;只有一种组合即6和3;
• 这样概率就不等了.

由大的随机数求小的随机数可以吗?(√)

• 假如由rand10() -> rand7()可以吗?

• 答案是可以的.

• 只需要rand10()生成0-6即可.如果>6就不让输出

• 其实很好解释:

  • rand10生成随机数是等概率的,所以生成0-6之间的数当然也是等概率的.

  int rand7(){
  res = 7  
  while (res > 6)       
  res = rand10();    
  return res;
  }

  数学证明可以看这里

这时的想法是能生成一个[0-N]的数,其中N>=9就行

res = rand7()*7 + rand7()+1

res可以等概率的生成1~49.原因如下:

• rand7()*7 可以生成 0,7,14,21,28,35,42.这7个数都是等概率1/7
• rand7()*7 + rand7()+1正好能生成1~49

所以函数为:

public static int rand10(){
    int res = 49;
    //为什么不是res>10
    while (res>40) {
        res = rand7()*7 + rand7()+1;
    }
    return res%10;
}

为什么不是res>10?

原因有两个:

• 输出结果一致吗?(√)
  • 输出1-40,概率是相同,res%10
  • 输出1-10,概率是相同,res%10
  • 两个res%10结果是一致的
• 概率一样吗?
  • 输出1-10,while一次能输出的概率为 10/49
  • 输出1-40,while一次能输出的概率为40/49
  • 显然能减少循环.

综上,不使用res>10,使用res>40,能减少循环.

java代码如下:

import java.util.Arrays;
import java.util.Random;

/**
 * 已知:
 * rand7()
 * 0-6
 * 求：
 * rand10()
 * 0-9
 */
public class randomNumber {

    public static int rand7(){
        return  new Random().nextInt(7);
    }

    public static int rand10(){
        int res = 49;

        //为什么是40不是10
        //如果是10的话，那么while会循环很多次，因为概率输出的概率为10/49
        //这时会输出1-40,其概率是相同，res%10和输出1-10的res%10效果一致
        //但是能够输出的概率变为40/49，概率大增
        while (res>40) {
            res = rand7()*7 + rand7()+1;
        }
        return res%10;
    }


    public static void main(String[] args) {
        double[] print = new double[10];
        for (int i = 0; i < 1000000; i++) {
            print[rand10()] += 1;
        }

        for (int i = 0; i < print.length; i++) {
            print[i] = print[i] /1000000;
        }

        System.out.println(Arrays.toString(print));
    }
}

输出结果: (概率一致)

[0.097554, 0.122075, 0.097362, 0.097936, 0.097623, 0.097441, 0.097284, 0.097415, 0.097377, 0.097933]