程序员面试题精选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[5*6+1] ;
		for (int i = 0; i < a1.length; i++) {
			a1[i]=0;
		}
		
		for (int i = 1; i <=6; i++) {
			a1[i]=1;
		}
		                  // {0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0 };
		
	    int[] a2 = new int[5*6+1];// {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0};
		for (int i = 0; i < a2.length; i++) {
			a2[i]=0;
		}
		for (int n = 2; n <= 4; n++) {//第2个到第4个筛子加入
			for (int i = 1 ; i <= (6 * n); i++) {//加入几个筛子，就遍历到加入的最大的数(2个骰子的和最大为12)
				a2[i] = 0;    //记录计算过程
				for (int j = 1; j <= 6; j++) {
					if (i - j >= 1)
					   a2[i] += a1[i - j];   //a2[i]中记录了i-1到i-6的结果和
				}
			}
			for (int i = 0; i < a2.length; i++) {
				a1[i]=a2[i];
			}
			
			
			for (int i = 0; i < a1.length; i++) {
				System.out.print(a1[i] + " ");
			}
			System.out.print("\n");
		}