程序员面试题精选100题(43)-n个骰子的点数
题目：把n个骰子扔在地上，所有骰子朝上一面的点数之和为S。输入n，打印出S的所有可能的值出现的概率。用一个HashMap,把所有计算的和都存进去，如果出现多次，那么对应的value++;那么我们就可以知道每个值到此出现了多少次；可以使用递归来做
Map p = new HashMap();public void getCount(int n,int he){ if(n==0){ if(p.get(he)!=null){ p.put(he,p.get(he)+1); }else{ p.put(he,1); } return; }for(int i=1;i<=6;i++){ get(n-1,he+i);}}
递归往往很多重复计算。。。。
因为第n个位置是n-1,n-6位置的值晋升过来的，而第n位置也会晋升到n+1...n+6
所以可以使用下面的代码
int[] a1 = new int ;for (int i = 0; i < a1.length; i++) {a1=0;}for (int i = 1; i <=6; i++) {a1=1;} // {0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0 }; int[] a2 = new int;// {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0};for (int i = 0; i < a2.length; i++) {a2=0;}for (int n = 2; n <= 4; n++) {//第2个到第4个筛子加入for (int i = 1 ; i <= (6 * n); i++) {//加入几个筛子，就遍历到加入的最大的数(2个骰子的和最大为12)a2 = 0; //记录计算过程for (int j = 1; j <= 6; j++) {if (i - j >= 1) a2 += a1; //a2中记录了i-1到i-6的结果和}}for (int i = 0; i < a2.length; i++) {a1=a2;}for (int i = 0; i < a1.length; i++) {System.out.print(a1 + " ");}System.out.print("\n");}
页:
[1]