n个骰子的点数 java_《剑指Offer》60：n个骰子的点数

忘是亡心i 2022-11-03 01:42 92阅读 0赞

题目

把n个骰子扔在地上，所有骰子朝上一面的点数之和为S。输入n，打印出S的所有可能的值出现的概率。

分析

直接法

假设骰子有face面，有n个骰子，那么总排列数就有faceⁿ个。(例如，有3个6面骰子，那么其总排列数为6³=216个)。所有骰子的和最小值为n(假设骰子最小值为1)，而和最大值为n \* face(例如，有3个6面骰子，那么和最大值为18)， 那么就有 (n \* face - n + 1)个可能和值，那么新建长度为(n \* face - n + 1)的一维数组进行统计不同S出现的次数。

然后骰子分别依次一个一个地投，并将其可能的值累加，最后将相应数组元素自增。

最后，遍历数组，除以总排列数，得出结果。

该算法时间复杂度为O(faceⁿ)，当n越大，运算时间越长。(n从12开始增大，等待时间就开始难以接受)空间复杂度为O(n \* face)。

动态规划

确定问题解的表达式。可将f(n, s)表示n个骰子点数的和为s的排列情况总数

确定状态转移方程。n个骰子点数和为s的种类数只与n-1个骰子的和有关。因为一个普通骰子有六个点数，那么第n个骰子可能出现1到6的点数。所以第n个骰子点数为1的话，f(n,s)=f(n-1,s-1)，当第n个骰子点数为2的话，f(n,s)=f(n-1,s-2)，…，依次类推。在n-1个骰子的基础上，再增加一个骰子出现点数和为s的结果只有这6种情况！那么有：

f(n,s) = f(n-1,s-1) + f(n-1,s-2) + f(n-1,s-3) + f(n-1,s-4) + f(n-1,s-5) + f(n-1,s-6)

上面就是状态转移方程，已知初始阶段的解为：当n=1时, f(1,1)=f(1,2)=f(1,3)=f(1,4)=f(1,5)=f(1,6)=1。

该算法时间复杂度为O(n²)，空间复杂度为O(n²)。

以3个6面骰子为例，所用到dp\[i\]\[j\]数组如下图所示。

i\\j

放码

一、直接法

import java.util.Arrays;

public class SumOfNDices \{

public static int DICE\_MAX\_VALUE = 6;

public double\[\] getProbability(int numOfDice) \{

if(numOfDice < 1) \{

throw new IllegalArgumentException();

int maxSum = DICE\_MAX\_VALUE \* numOfDice;

int\[\] sums = new int\[maxSum - numOfDice + 1\];

Arrays.fill(sums, 0);

setSums(numOfDice, sums);

int total = (int)Math.pow(DICE\_MAX\_VALUE, numOfDice);

return Arrays.stream(sums).mapToDouble((a)->(a \* 1.0 / total)).toArray();

public void setSums(int numOfDice, int\[\] sums) \{

for(int i = 1; i <= DICE\_MAX\_VALUE; i++) \{

setSums(numOfDice, numOfDice - 1, i, sums);

public void setSums(int numOfDice, int leftNumOfDice, int sum, int\[\] sums) \{

if(leftNumOfDice == 0) \{

sums\[sum - numOfDice\]++;

\}else \{

for(int i = 1; i <= DICE\_MAX\_VALUE; i++) \{

setSums(numOfDice, leftNumOfDice - 1, i + sum, sums);

二、动态规划(二维数组)

public double\[\] getProbability2(int numOfDice) \{

if(numOfDice < 1) \{

throw new IllegalArgumentException();

int\[\]\[\] dp = new int\[numOfDice + 1\]\[numOfDice \* DICE\_MAX\_VALUE + 1\];

double\[\] result = new double\[numOfDice \* DICE\_MAX\_VALUE - numOfDice + 1\];

double total = Math.pow(DICE\_MAX\_VALUE, numOfDice);

Arrays.fill(dp\[1\], 1, DICE\_MAX\_VALUE + 1, 1);

for(int i = 1; i <= numOfDice; i++) \{//如1, 2, 3, 4, 5, 6

for(int j = i; j <= DICE\_MAX\_VALUE \* numOfDice; j++) \{//n个6面骰子的和的可能值 ：6, 7, 8, 9, ...

for(int k = 1; k <= DICE\_MAX\_VALUE; k++) \{//f(n, s) = f(n - 1, s - 1) + f(n - 1, s - 2) + f(n - 1, s - 3) + ...

dp\[i\]\[j\] += (j >= k ? dp\[i - 1\]\[j - k\] : 0); // j >= k 预防数组越界

if(i == numOfDice) \{

result\[j - i\] = dp\[i\]\[j\] / total;

return result;

由于每个dp\[i\]\[j\]只于i-1时刻的状态有关，所以可以删去一个维度，简化算法。

三、动态规划(一维数组)

在上述解法的基础上，删去一个维度

第二个循环从后往前遍历，避免覆盖

public double\[\] getProbability3(int numOfDice) \{

if(numOfDice < 1) \{

throw new IllegalArgumentException();

int\[\] dp = new int\[numOfDice \* DICE\_MAX\_VALUE + 1\];

double\[\] result = new double\[numOfDice \* DICE\_MAX\_VALUE - numOfDice + 1\];

double total = Math.pow(DICE\_MAX\_VALUE, numOfDice);

for(int i = 1; i <= DICE\_MAX\_VALUE; i++) \{

dp\[i\] = 1;

result\[i - 1\] = 1.0 / DICE\_MAX\_VALUE;

for(int i = 2; i <= numOfDice; i++) \{

for(int j = DICE\_MAX\_VALUE \* numOfDice; j >= 1; j--) \{

int temp = 0;

for(int k = 1; k <= DICE\_MAX\_VALUE; k++) \{

temp += (j >= k) ? dp\[j - k\] : 0;

dp\[j\] = temp;

if(i == numOfDice && j >= numOfDice) \{

result\[j - i\] = dp\[j\] / total;

return result;

测试

import java.util.Arrays;

import org.junit.Assert;

import org.junit.Test;

public class SumOfNDicesTest \{

@Test

public void test() \{

SumOfNDices sd = new SumOfNDices();

double\[\] result = sd.getProbability(1);

System.out.println(result.length);

System.out.println(Arrays.toString(result));

@Test

public void test2() \{

SumOfNDices sd = new SumOfNDices();

double\[\] result = sd.getProbability(10);

double\[\] result2 = sd.getProbability2(10);

Assert.assertArrayEquals(result, result2, 1E-10);

@Test

public void test3() \{

SumOfNDices sd = new SumOfNDices();

double\[\] result = sd.getProbability(10);

double\[\] result3 = sd.getProbability3(10);

Assert.assertArrayEquals(result, result3, 1E-10);

n个骰子的点数 java_《剑指Offer》60：n个骰子的点数

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关剑指Offer系列（java版，详细解析）60.n个骰子的点数

相关《剑指Offer》60：n个骰子的点数

相关【剑指Offer】60. n个骰子的点数

相关剑指 Offer 60. n个骰子的点数（dp）

相关 n个骰子的点数 java_《剑指Offer》60：n个骰子的点数

相关【剑指offer-Java版】43n个骰子的点数

相关 3个骰子求和

相关求n个骰子各点数和出现的概率-动态规划

相关 n个骰子的点数

相关剑指offer-题43：n个骰子的点数