关于随机数的几道算法题（随机算术题）

主题：算法，随机数相关

目标：记录几道算法题的解法；刻意练习：无

目标读者：能读懂java的程序员

最近准备回炉重造一下，对计算机相关的内容进行学习和回顾。

基于教是最好的学，以及想要充分的折叠时间，接下来很长一段时间可能都会写纯技术向的内容。

人果然是会变的，这两年一直挣扎着想要摆脱程序员的身份，干点别的。兜兜转转一圈发现当程序员也挺好的。外加，当我没把这个职业做得足够好之前，好像也没啥资格说喜不喜欢的。

废话说了这么多，咱就直接开始吧。（另外，之后的技术向文章都会采用markdown格式来写，公众号貌似不支持这种格式吧，但也没关系，主要是这种格式比较方便迁移。）

今天的主题，关于算法，用java表达。学算法真是爽啊，大脑严重过载，感觉头发保不住了，哈哈哈。

# 随机数

## Math.random()

Math.random()方法的取值范围：(double)[0,1)

Math.random()方法可以保证每一个数都等概率出现。

也就是说对于任意一个x（取值范围内），生成的随机数出现在0~x之间的概率为x。

例：x=0.3，则随机数生成在0~0.3范围内的概率为0.3，即30%。

## 将0~x出现的概率由x改为x2

```java

public static double x2xPower2(){

return Math.max(Math.random(),Math.random());

}

```

即连续取两次随机数，需要两次都落在0~x之间，取最大值时才能取到。

例：

1.x=0.5，第一次取值为0.3，第二次取值为0.4，max=0.4，在0~0.5之间

2.x=0.5，第一次取值为0.3，第二次取值为0.7，max=0.7，不在0~0.5之间

1.x=0.5，第一次取值为0.7，第二次取值为0.8，max=0.8，不在0~0.5之间

所以，只有两次都在0~x之间，返回值才在0~x之间，所以概率由x变为了x\*x，即x2。

同理，如果改成x3，则再多取一次。

## 从1~5的随机到1~7的随机

有一个方法f1()可以生成1~5的随机数，现在需要利用这个方法来生成1~7的随机数。f1()方法只能用，不能改。

思路：

1.先讲f1()转换成等概率返回0~1的方法f2()

2.使用f2(),通过位运算来实现0~2^n的等概率产生方法

3.根据具体情况进行微调

1.如果得到1~2，返回0，如果得到4~5返回1，如果得到3，重新生成。通过二分法，实现0~1生成的等概率。

```java

public static int f2() {

int result;

do {

result = f1();

} while (result == 3);

return result < 3 ? 0 : 1;

}

```

2.2^3=8，所以可以利用3个二进制位来得到0~7的等概率生成，通过左移来实现。

```java

public static int f3() {

//(f2() << 2) + (f2() << 1) + (f2() << 0)

return (f2() << 2) + (f2() << 1) + f2();

}

```

3.1~7的随机生成，可以转化为0~6的随机生成加一。

第三步和第一步同理，生成0~6时返回，生成7时，重新生成。

```java

public static int f4() {

int result;

do {

result = f3();

} while (result == 7);

return result + 1;

}

```

## 从不等概率0和1到等概率

有一个方法f1()随机不等概率地生成0和1，要通过这个方法，生成等概率的0和1。f1()方法只能用，不能改。

思路：

假设生成1的概率为P，则生成0的概率为（1-P）

取两次值，会出现下面4种情况

11->P\*P

10->P\*(1-P)

01->(1-P)\*P

00->(1-P)\*(1-P)

所以，抛弃两次结果一样的情况，因为概率，我们不清楚。

但产生10或者01的概率是相同的。

```java

public static int f2() {

int result;

do {

result = f1();

} while (result == f1());

return result;

}

```

字数：不统计

耗时：1小时

··················END··················