账号密码登录
微信安全登录
微信扫描二维码登录

登录后绑定QQ、微信即可实现信息互通

手机验证码登录
找回密码返回
邮箱找回 手机找回
注册账号返回
其他登录方式
分享
  • 收藏
    X
    扔 n 个骰子,向上面的数字之和为 S。
    37
    0

    问题描述

    扔 n 个骰子,向上面的数字之和为 S。给定 Given n,请列出所有可能的 S 值及其相应的概率。

    样例

    给定 n = 1,返回 [ [1, 0.17], [2, 0.17], [3, 0.17], [4, 0.17], [5, 0.17], [6, 0.17]]。
    public class Solution {
        /**
         * @param n an integer
         * @return a list of Map.Entry<sum, probability>
         */
        public List<Map.Entry<Integer, Double>> dicesSum(int n) {
            // Write your code here
            // Ps. new AbstractMap.SimpleEntry<Integer, Double>(sum, pro)
            // to create the pair
        }
    }
    0
    打赏
    收藏
    点击回答
        全部回答
    • 0
    • 简以时光 普通会员 1楼

      这是一个组合优化问题,可以通过动态规划的方法来解决。

      设 S = a1 + a2 + ... + an,其中 a1, a2, ..., an 分别是投掷出的 1, 2, ..., n 的数字。我们可以得到一个表格,其中每一行表示投掷出的数字,每一列表示投掷出的数字和。

      表格的左边一列是投掷出的数字,右边一列是投掷出的数字和。我们可以通过将当前行的和与所有行的和相加,然后与目标和进行比较,来确定哪些数字组合可以得到和为 S。

      以下是一个 Python 的示例代码:

      python def can_combine_dice(n, S): dp = [[False] * n for _ in range(S + 1)] dp[0][0] = True for i in range(1, n + 1): for j in range(S + 1): if dp[i - 1][j]: dp[i][j] = dp[i - 1][j] or dp[i - 1][j - a1] or dp[i - 1][j - a2] or ... or dp[i - 1][j - an] else: dp[i][j] = dp[i - 1][j] return dp[n][S]

      在这个代码中,dp[i][j] 表示投掷出数字 i 的情况是否可以得到和为 S。如果可以得到和为 S,那么 dp[i][j] 的值为 True,否则为 False

      注意,这个代码只能判断投掷出数字之和是否等于目标和,不能判断投掷出每个数字的可能性。

    更多回答
    扫一扫访问手机版
    • 回到顶部
    • 回到顶部