Given n dice each with m faces, numbered from 1 to m, find the number of ways to get sum X. X is the summation of values on each face when all the dice are thrown.
TheNaive approachis to find all the possible combinations of values from n dice and keep on counting the results that sum to X.
This problem can be efficiently solved usingDynamic Programming (DP).
Let the function to find X from n dice is: Sum(m, n, X)
The function can be represented as:
Sum(m, n, X) = Finding Sum (X - 1) from (n - 1) dice plus 1 from nth dice
+ Finding Sum (X - 2) from (n - 1) dice plus 2 from nth dice
+ Finding Sum (X - 3) from (n - 1) dice plus 3 from nth dice
...................................................
...................................................
...................................................
+ Finding Sum (X - m) from (n - 1) dice plus m from nth dice
So we can recursively write Sum(m, n, x) as following
Sum(m, n, X) = Sum(m, n - 1, X - 1) +
Sum(m, n - 1, X - 2) +
.................... +
Sum(m, n - 1, X - m)
Why DP approach?
The above problem exhibits overlapping subproblems. See the below diagram. Also, seethisrecursive implementation. Let there be 3 dice,
each with 6 faces and we need to find the number of ways to get sum 8:
Sum(6, 3, 8) = Sum(6, 2, 7) + Sum(6, 2, 6) + Sum(6, 2, 5) +
Sum(6, 2, 4) + Sum(6, 2, 3) + Sum(6, 2, 2)
To evaluate Sum(6, 3, 8), we need to evaluate Sum(6, 2, 7) which can
recursively written as following:
Sum(6, 2, 7) = Sum(6, 1, 6) + Sum(6, 1, 5) + Sum(6, 1, 4) +
Sum(6, 1, 3) + Sum(6, 1, 2) + Sum(6, 1, 1)
We also need to evaluate Sum(6, 2, 6) which can recursively written
as following:
Sum(6, 2, 6) = Sum(6, 1, 5) + Sum(6, 1, 4) + Sum(6, 1, 3) +
Sum(6, 1, 2) + Sum(6, 1, 1)
..............................................
..............................................
Sum(6, 2, 2) = Sum(6, 1, 1)
Please take a closer look at the above recursion. The sub-problems inREDare solved first time and sub-problems inBLUEare solved again (exhibit overlapping sub-problems). Hence,
storing the results of the solved sub-problems saves time.
For DP:
Time Complexity:O(m * n * x) where m is number of faces, n is number of dice and x is given sum.
We can add following two conditions at the beginning of findWays() to improve performance of program for extreme cases (x is too high or x is too low)
if
(m*n <= x)
return
(m*n == x);
if
(n >= x)
return
(n == x);
|
With above conditions added, time complexity becomes O(1) when x >= m*n or when x <= n.
文中的骰子不一定就是6面的,可以是任意面。
package DP;
public class DiceThrow {
public static void main(String[] args) {
System.out.println(findWaysRec(4, 2, 1));
System.out.println(findWaysRec(2, 2, 3));
System.out.println(findWaysRec(6, 3, 8));
System.out.println(findWaysRec(4, 2, 5));
System.out.println(findWaysRec(4, 3, 5));
System.out.println(findWaysDP(4, 2, 1));
System.out.println(findWaysDP(2, 2, 3));
System.out.println(findWaysDP(6, 3, 8));
System.out.println(findWaysDP(4, 2, 5));
System.out.println(findWaysDP(4, 3, 5));
}
// 返回能使组合之和为sum的方法数
// faces:一个dice的最大面值,所有面值为:[1...faces]
// dices:dices的个数,每个dice都可以选择一个face
public static int findWaysRec(int faces, int dices, int sum){
if(sum < 1){ // 总和过小
return 0;
}
if(dices == 1){ // 只有一个dice,判断总和和最大面值哪个大
return sum<=faces ? 1 : 0;
}
int ways = 0;
for(int i=1; i<=faces; i++){
ways += findWaysRec(faces, dices-1, sum-i);
}
return ways;
}
// The main function that returns number of ways to get sum
// Time Complexity: O(m * n * x) where m is number of faces, n is number of dice and x is given sum.
public static int findWaysDP(int faces, int dices, int sum){
int[][] dp = new int[dices+1][sum+1]; //dp[dices][sum]
for(int sum_=1; sum_<=sum; sum_++){ // 只有1个dice且sum大于
if(sum_ <= faces){
dp[1][sum_] = 1;
}
}
for(int dices_=2; dices_<=dices; dices_++){ // dices
for(int sum_=1; sum_<=sum; sum_++){ // sum
for(int faces_=1; faces_<=faces; faces_++){
if(sum_-faces_ >= 0){ // 防越界
dp[dices_][sum_] += dp[dices_-1][sum_-faces_];
}
}
}
}
return dp[dices][sum];
}
}
http://www.geeksforgeeks.org/dice-throw-problem/
分享到:
相关推荐
vhdl语言小程序dicegame 即骰子游戏,根据已经有的规则完成的程序,编译仿真通过
骰子安装$ npm i @idlework/dice --save用法import Dice from 'dice'export default class Map extends Dice { constructor ( dice , faces ) { super ( dice , faces ) }} 或者import Dice from 'dice'const dice =...
这是一段利用matlab仿真抛骰子问题的蒙特卡洛算法,要求两个骰子的点数之和大于6并且第一个点数大于第二个点数
DICe是机器可移植的(Windows、Linux和Mac),可以有效地部署在高性能计算平台上(DICe使用MPI并行和线程内核并行)。DICe的功能可以通过定制的库接口、DICe类的源代码集成或独立的可执行文件来调用。
用面向对象的方法分析色子游戏系统 每个游戏者掷骰子游戏总数是7为赢,否者为输
本资源包含基于Matlab的使用dice相似系数方法进行图像分割精度验证源码和图片素材。 包含 实例1:计算二值分割图像的dice相似系数 实例2:计算多区域分割图像的dice相似系数 本资源配套CSDN博客“Matlab图像分割---...
DiceGame:骰子游戏
之前在文章:https://blog.csdn.net/Sweety_Lin/article/details/104199580 中写的DICE计算程序,是将Nii的整个volume计算在内,现想提取T2中有lesion的特定层面来计算DICE: import nibabel as nib import scipy....
一个简单的骰子滚动应用程序演示了一个多平台的功能架构,前端用于android和ios。
dice精美高档骰子模型,可用于商业或非商业项目
1.版本:matlab2019a,不会运行可私信 2.领域:基础教程 3.内容:【数据分析】MATLAB计算dice系数.zip 4.适合人群:本科,硕士等教研学习使用
matlab开发-DiceGame。玩一个有趣又容易学的骰子游戏。独自一人,和朋友在一起,或者和不同技能水平的人工智能作比较。
骰子 :game_die:关于简单的骰子掷骰工具,您可以在其中动态添加骰子。安装下载源代码。 要下载所有依赖项,请执行: npm install要启动网络应用程序: npm start用法在顶部的字段中,输入将随机选择的值。 每个值...
-查看可能的骰子形状和选项(大小/字体颜色/底色) -看,如何掷出5个骰子,该骰子将始终落在同一侧 安装 npm install threejs-dice 用法 [removed][removed] [removed] // Setup your threejs scene var scene = ...
实用的仿真系统DICE-51 单片机学习者可以多加关注啊
3D-Dice.zip,GRRD的骰子-一个HTML5 PWA WebGL 3D骰子和Yahtzee游戏,3D建模使用专门的软件来创建物理对象的数字模型。它是3D计算机图形的一个方面,用于视频游戏,3D打印和VR,以及其他应用程序。
骰子一个Scala库,用于统计建模和分析概率分布。 提供Dice类型,该Dice具有丰富的代数,可用于组合模具辊。 虽然这不是主要用于生成带有骰子的随机数,但它确实允许您对分布进行采样以“滚动”骰子。 例子: 3 d 6...
骰子游戏Java Java中的骰子游戏-针对计算机滚动随机骰子,获得最高分。 保持骰子每轮3掷最多的选项,目的是在每轮中收集最高分并达到设定的最高分。 (101个默认高分)
DICE-5210k用户手册20100606
它就像一个普通计算器,支持基本算术(+、-、* 和 /)和括号,以及两个额外的运算符: d (代表“骰子”)和k (代表“保持”)。 “骰子”运算符需要两个操作数,它们可以是任意复杂的表达式。 省略操作数是一个...