LintCode2016年8月22日算法比赛----骰子求和

骰子求和

题目描述

扔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]]。

算法分析

该题目刚开始的标记为简单,所以我做完两道简单题目后直接就看了这道题目,结果被卡在这里了。后来实现了完整的算法,结果提交只是通过了一部分的数据测试。看看还剩2分钟就结束了,焦急了,回头再去看题目列表,发现该题的难度级别又被标记为困难了,而之前标记为困难的平面列表,又被标记为简单了。进去一看,果然很简单,5分钟内实现了算法,在Eclipse测试,然后提交,Accepted!。结果比赛也已经结束了,只算是做对了两道题。我了个去!主办方是否要检讨检讨?

不闲扯了,分析算法:

该问题的解题思路应该是采用递归的方法:给定n个骰子,那么可投掷出的数字为n6n。可能有人会疑惑n6n中会不会有某个数字骰子表达不出来,好疑惑,答案是不会,证明如下:

假设有n个相同的单个容量为6的豌豆筒,我们有6n颗豌豆,那么这6n颗豌豆能且正好能放进这n个豌豆筒中,说明n个骰子可以表达出6n;现在从任意筒中取出一颗豌豆,筒中还剩6n-1颗豌豆,说明n颗骰子可以表达出6n-1;如果某个筒中只剩一颗豌豆了,那么我们再次取豌豆的时候就不从里面取了;重复一颗一颗地取豌豆,直到每个筒中只剩下一颗豌豆,这是筒中总共有n颗豌豆,说明n个骰子可以表达n。而从6n到n的过程中,因为我们是一颗一颗豌豆取出的,所以6n-1到n+1这些颗数都曾在筒中出现过。因此n颗骰子能表达6n到n的所有数字。

n个骰子总共可以表达的情况有Math.pow(6,n)种。考虑n个骰子可以表达num的情况数:

如果第一骰子投出1,那么我们只需关心剩下的n-1个骰子能表达的num-1的情况数;如果第一个骰子投出了2,那么我们只需关心剩下的n-1个骰子能表达的num-2的情况数,依此类推;当然要注意,第一个骰子最多投出6。这里就用到了递归的思想。求n个骰子投出num的情况数的时候,需要递归求n-1个骰子投出num-1,num-2,num-3...的情况,而求n-1个骰子投出num-1的情况数的时候,需要递归求n-2个骰子投出num-2,num-3,num-4...的情况;求n-1个骰子投出num-2的情况数的时候,需要递归求n-2个骰子投出num-3,num-4...的情况,这里看到会有重复求解的过程,因此为了优化算法,这里采用动态规划技术,以减少不必要的重复求解过程。使用HashMap<String,Double>来存储已经计算好的情况数。这里String作为键,用以标记“x个骰子投出y”,值Double为情况数。这里Double我本来用的是Integer,结果计算精度出现问题,后来用Long,还是显示有些测试精度存在问题,索性改成Double,就Accepted了。

PS:刚才又试了一下,Double和Long都好使,Integer会出现精度问题


Java算法实现

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
List<Map.Entry<Integer, Double>>list=new ArrayList<Map.Entry<Integer,Double>>(5*n+1);
Double pro=0.0;
double total=Math.pow(6, n);
double conditions=0; //刚开始我用的int,发现计算结果又精度问题,改成long还是有精度问题,最后改成double就没问题了
//但严格来说,情况数应该是整数,是没问题的,计算过程中没有出现溢出的情况,total已经是double了,
//难道 1/1.0 根1.0/1.0不一样?
HashMap<String,Double> hashMap=new HashMap<>();
for(int i=n;i<=6*n;i++){
pro=0.0;
conditions=findCombs(i, n,hashMap);
pro=conditions/total;
list.add(new AbstractMap.SimpleEntry<Integer, Double>(i,pro));
} return list;
} public static double findCombs(int num,int n,HashMap<String, Double>hashMap){
//为了简化计算,假设每个骰子最小值为0,最大值为5,共n个骰子
double total=0;
String key=String.valueOf(num)+","+String.valueOf(n);
if(hashMap.containsKey(key)){
return hashMap.get(key);
} if(num<=0){
if(n>=1)
total=0;
else
total=1;//0 个骰子得到0 是可以的
}
else{
//num >0
if(n<1){
total=0;
}
else if(n==1){
if(num>6){
total=0;
}
else{
total=1;
}
}
else{
int ceil=num<=6?num:6;
for(int i=1;i<=ceil;i++){
total+=findCombs(num-i, n-1,hashMap);
}
}
}
hashMap.put(key, total);
return total;
} }
上一篇:uva 699 the falling leaves——yhx


下一篇:Qt编写自定义控件50-迷你仪表盘