骰子求和

1、题目描述

要求：扔 n 个骰子，向上面的数字之和为 S。给定 Given n，请列出所有可能的 S 值及其相应的概率。
样例：
输入

1

输出：

[ [1, 0.17], [2, 0.17], [3, 0.17], [4, 0.17], [5, 0.17], [6, 0.17]]

2、解决代码

(1)解题思路

1个骰子，S的取值区间为1~6;
2个骰子，S的取值区间为2~12;
3个骰子，S的取值区间为3~18...

因此可以创建一个二维数组a[n][n*6]，该数组的每一行代表一种情况：a[1][]代表一个骰子的情况；a[2][]代表两个骰子的情况...
在n-1个骰子的情况下，我们新加上一个骰子，此时和为S的骰子出现的次数应该等于n-1个骰子时和为S-1、S-2、S-3、S-4、S-5与S-6的次数的总和。
n = 1时： f(1,1) = f(1,2) = f(1,3) = f(1,4) = f(1,5) = f(1,6) = 1
而 n = 2时：f(2,2) = f(1,1) = 1
f(2,3) = f(1,2) + f(1,1) = 2
...
f(2,6) = f(1,5) + f(1,4) + f(1,3) + f(1,2) + f(1,1)

f(2,7) = f(1,6) + f(1,5) + f(1,4) + f(1,3) + f(1,2) + f(1,1) = 6

(2)基于以上思想，可以写出以下的代码

import java.text.DecimalFormat;
import java.util.*;

public class Main3 {
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {//注意while处理多个case
            int n = in.nextInt();
            List<Map.Entry<Integer, String>> result = dicesSum(n);
            for (int i = 0; i < result.size(); ++i) {
                Map.Entry<Integer, String> map = result.get(i);
                if (i == 0)
                    System.out.print("[[" + map.getKey() + ", " + map.getValue() + "], ");
                else if (i == result.size() - 1)
                    System.out.println("[" + map.getKey() + ", " + map.getValue() + "]]");
                else {
                    System.out.print("[" + map.getKey() + ", " + map.getValue() + "], ");
                }

            }
        }
    }

    public static List<Map.Entry<Integer, String>> dicesSum(int n) {

        DecimalFormat df = new DecimalFormat("0.00000");
        long[][] dp = new long[n + 1][6 * n + 1];
        dp[1][1] = 1;
        dp[1][2] = 1;
        dp[1][3] = 1;
        dp[1][4] = 1;
        dp[1][5] = 1;
        dp[1][6] = 1;
        //计算2个以上骰子可能出现的和及其对应的次数
        for (int i = 2; i <= n; i++) {
            for (int j = i; j <= i * 6; j++) {
                long x1 = 0, x2 = 0, x3 = 0, x4 = 0, x5 = 0, x6 = 0;
                if (j - 1 > 0) {
                    x1 = dp[i - 1][j - 1];
                }
                if (j - 2 > 0) {
                    x2 = dp[i - 1][j - 2];
                }
                if (j - 3 > 0) {
                    x3 = dp[i - 1][j - 3];
                }
                if (j - 4 > 0) {
                    x4 = dp[i - 1][j - 4];
                }
                if (j - 5 > 0) {
                    x5 = dp[i - 1][j - 5];
                }
                if (j - 6 > 0) {
                    x6 = dp[i - 1][j - 6];
                }
                dp[i][j] = x1 + x2 + x3 + x4 + x5 + x6;
            }
        }
        List<Map.Entry<Integer, String>> result = new ArrayList<>();
        for (int i = n; i <= 6 * n; i++) {
            AbstractMap.SimpleEntry<Integer, String> entry = new AbstractMap.SimpleEntry<>(i, df.format(dp[n][i] / Math.pow(6, n)));
            result.add(entry);
        }
        return result;
    }
}

参考文章：https://blog.csdn.net/aphysia/article/details/77855488