一个有趣的题目

发表于 | 更新于: | 分类于

题目

一栋楼里面有4台电梯，1000名员工。每台电梯同时能分配到250±10%名员工的概率是多少？（电梯负载无上限，人员选择电梯的概率都是一样的）

首先不考虑10%的范围

穷举：

1.首先先考虑2台电梯，4个人的情况吧
四个人只有三种组合：

（0，4）,（1，3）（2，2）

此时概率为了1/3

2.首先先考虑2台电梯，6个人的情况吧

（0，6）,（1，5）（2，4）, (3,3)

此时的概率为了1/4

3.从以上两个例子可以看出，其实就是求一定数量的人的组合，可以用多少种组合

可以拿4台电梯（4,8个人员穷举一下）

4个人的时候,共有5种， 此时概率为了1/5:

(0,0,0,4),(0,0,1,3),(0,0,2,2),(0,1,1,2),

(1,1,1,1)

8个人的时候,共有12种， 此时概率为了1/12:

(0,0,0,8),(0,0,1,7),(0,0,2,6),(0,0,3,5),(0,0,4,4)

(0,1,1,6),(0,1,2,5),(0,1,3,4)

(1,1,1,5),(1,1,2,4),(1,1,3,3)

(2,2,2,2)

可以看出概率是越来越低的，同时不用区分每个人选择哪个电梯,因为组合是无序的，即(0,0,0,8)与(0,0,8,0)是一样的

同时可以看出，数量达到1000的时候 是不可能 穷举的

编程（穷举）

代码一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package cc.unine.java;
import org.junit.Test;
public class TestResult {
	@Test
	public void test() {
		int sum = 1000; // 员工数量
		int num = 4; // 电梯数量
		int average = sum / num; // 每台电梯平均分配数量：1000/4=250
		int count = 0;
		for (int i = 0; i <= sum; i++) {//第一个坑
			for (int j = i; j <= sum; j++) {第二个坑
				for (int k = j; k <= sum; k++) {第三个坑
					for (int l = k; l <= sum; l++) {第四个坑
						if (i + j + k + l == sum) {
							count++;
						}
					}
				}
			}
		}
		System.out.println("count = " + count);
	}
}

很显示，这个效率不高。

image

为了尽量减少重复，可以考虑i<=j,j<=k,k<=l

所以4i <= i + j + k + l <= sum <= average * 4,即i<=average

j <= sum / (num-1)

k <= sum / (num-2)

l <= sum / (num-3)

同时i + j + k + l >sum时跳出循环

然后得优化代码

代码二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package cc.unine.java;
import org.junit.Test;
public class TestResult {
	@Test
	public void test() {
		int sum = 1000; // 员工数量
		int num = 4; // 电梯数量
		int average = sum / num; // 每台电梯平均分配数量：1000/4=250
		int count = 0;
		long startTime = System.currentTimeMillis();
		for (int i = 0; i <= average; i++) {//
			for (int j = i; j <= sum / (num-1); j++) {
				for (int k = j; k <= sum / (num-2); k++) {
					for (int l = k; l <= sum / (num-3); l++) {
						if (i + j + k + l == sum) {
							count++;
						}else if(i + j + k + l > sum) {
							break;
						}
					}
				}
			}
		}
		long endTime = System.currentTimeMillis();
		System.out.println("count = " + count);
		System.out.println("cost time:" + (endTime - startTime) / 1000 + "s");
	}
}

运行结果如下，效率提高了不少：

image

代码3-指定范围的概率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package cc.unine.java;
import org.junit.Test;
public class TestResult {
	@Test
	public void test() {
		int sum = 1000; // 员工数量
		int num = 4; // 电梯数量
		int average = sum / num; // 每台电梯平均分配数量：1000/4=250
		double offset = 0.1 * average; // 误差范围10%
		int count = 0;// 总共排列的组合数量
		int needCount = 0;// 指定范围的组合数量
		long startTime = System.currentTimeMillis();
		for (int i = 0; i <= average; i++) {//
			for (int j = i; j <= sum / (num - 1); j++) {
				for (int k = j; k <= sum / (num - 2); k++) {
					for (int l = k; l <= sum / (num - 3); l++) {
						if (i + j + k + l == sum) {
							count++;
							if (isInSpecifiedRange(i, average, offset) && isInSpecifiedRange(j, average, offset)
									&& isInSpecifiedRange(k, average, offset)
									&& isInSpecifiedRange(l, average, offset)) {
								needCount++;
							}
						} else if (i + j + k + l > sum) {
							break;
						}
					}
				}
			}
		}
		long endTime = System.currentTimeMillis();
		System.out.println("count = " + count);
		System.out.println("needCount = " + needCount);
		System.out.println("percent = " + (needCount * 1.0f / count * 100 + "%"));
		System.out.println("cost time:" + (endTime - startTime) / 1000 + "s");
	}
	// 在平均数的offset的范围内
	private boolean isInSpecifiedRange(int i, int average, double offset) {
		if (i < average + offset && i > average - offset) {
			return true;
		}
		return false;
	}
}

可以看出，概率约5.1%左右:

image

人员改为2000的时候的结果如下：

image

完