题目：把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
解法一：基于递归求骰子点数，时间效率不够高
要想求出n个骰子的点数和，可以先把n个骰子分为两堆：第一堆只有1个；另一堆有n-1个。单独的那一个有可能出现1 ~ 6的点数。我们需要计算1 ~ 6的每一种点数和剩下的n-1个骰子来计算点数和。
接下来把剩下的n-1个骰子仍然分成两堆：第一堆只有1个；第二堆有n-2个。我们把上一轮那个单独骰子的点数和这一轮单独骰子的点数相加，再和剩下的n-2个骰子来计算点数和。
我们可以定义一个长度为6n-n+1的数组，将和为s的点数出现的次数保存到数组的第s-n个元素里。
基于这种思路，我们可以写出如下代码：
private int mMaxValue = 6;
public void printProbability(int number) {
if (number < 1) {
return;
}
int maxSum = number * mMaxValue;
int[] probabilities = new int[maxSum - number + 1];
for (int i = 1; i <= mMaxValue; i++) {
probability(number, number, i, probabilities);
}
double total = Math.pow(mMaxValue, number);
for (int i = number; i <= maxSum; i++) {
System.out.printf("%d: %f\n", i, probabilities[i - number] / total);
}
}
private void probability(int number, int current, int sum, int[] probabilities) {
if (current == 1) {
probabilities[sum - number]++;
} else {
for (int i = 1; i <= mMaxValue; i++) {
probability(number, current - 1, i + sum, probabilities);
}
}
}
复杂度分析
- 时间复杂度：O(m^n)。
- 空间复杂度：O(mn)。
m为最大点数，n为骰子数。
解法二：基于循环求骰子点数，时间性能好
我们可以考虑用两个数组来存储骰子点数的每个总数出现的次数。
在一轮循环中，第一个数组中的第n个数字表示骰子和为n出现的次数。在下一轮循环中，我们加上一个新的骰子，此时和为n的骰子出现的次数应该等于上一轮循环中骰子点数和为n-1、n-2、n-3、n-4、n-5与n-6的次数的总和，所以我们把另一个数组的第n个数字设为前一个数组对应的第n-1、n-2、n-3、n-4、n-5与n-6个数字之和。
基于这种思路，我们可以写出如下代码：
public void printProbability(int number) {
if (number < 1) {
return;
}
int[][] probabilities = new int[2][mMaxValue * number + 1];
for (int i = 1; i <= mMaxValue; i++) {
probabilities[0][i] = 1;
}
int flag = 0;
for (int k = 2; k <= number; k++) {
for (int i = 0; i < k; i++) {
probabilities[1 - flag][i] = 0;
}
for (int i = k; i <= mMaxValue * k; i++) {
probabilities[1 - flag][i] = 0;
for (int j = 1; j <= i && j <= mMaxValue; j++) {
probabilities[1 - flag][i] += probabilities[flag][i - j];
}
}
flag = 1 - flag;
}
double total = Math.pow(mMaxValue, number);
for (int i = number; i <= mMaxValue * number; i++) {
System.out.printf("%d: %f\n", i, probabilities[flag][i] / total);
}
}
复杂度分析
- 时间复杂度：O(mn)。
- 空间复杂度：O(mn)。
m为最大点数，n为骰子数。
网友评论