解题笔记（18）――n个骰子的点数 - wuzhekai的专栏 - 博客频道 - CSDN.NET

解题笔记（18）――n个骰子的点数 - wuzhekai的专栏 - 博客频道 - CSDN.NET
问题描述：把n个骰子扔在地上，所有骰子朝上一面的点数之和为S。输入n，打印出S的所有可能的值出现的概率。
         思路：这是一道应用动态规划思想的题目，而动态规划最难的就是要找最优子结构。并采取一种称为备忘录的方法避免重复计算。因为备忘录方法为每个解过的子问题建立了备忘录，以备需要时参看，避免了相同子问题的重复求解。
        本题的最优子结构为：F(k, n) 表示k个骰子点数和为n的种数，k表示骰子个数，n表示k个骰子的点数和
                 /       = F(k-1, n-6) + F(k-1, n-5) + F(k-1, n-4) + F(k-1, n-3) + F(k-1, n-2) + F(k-1, n-1)        对于 k > 0, k <= n <= 6*k
 F(k, n) =     
                 \       = 0              对于 n < k or n > 6*k

         当k=1时, F(1,1)=F(1,2)=F(1,3)=F(1,4)=F(1,5)=F(1,6)=1。

         从上面公式可以看出，k个骰子点数和为n的种数只与k-1个骰子的和有关。这就可以用到备忘录的方法，用一张表格保存已解决的子问题的解，然后自底向上填表。考虑到当前层的计算只与下一层有关，因此只需保存一行。
[剑指offer] 面试题43：n个骰子的点数（Java）

分析: 一般来说骰子只有６面，点数为1~6，故n个骰子的最小和为n，最大和为6*n，则n个骰子的点数之和出现的频数可以用一个数组来保存，大小为6*n-n。

思路1：最直接的方法是求出n个骰子点数的全排列，然后一一计算其和值，统计，最后算出每个和值的概率，这里使用基于递归的方法来求各和值的频数.先把n个骰子分为两堆：第一堆只有一个，另一个有n-1个。单独的那一个有可能出现从1到6的点数。我们需要计算从1到6的每一种点数和剩下的n-1个骰子来计算点数和。接下来把剩下的n-1个骰子还是分成两堆，第一堆只有一个，第二堆有n-2个。我们把上一轮那个单独骰子的点数和这一轮单独骰子的点数相加，再和剩下的n-2个骰子来计算点数和。

    private int gMaxValue = 6;

     

    public void probility(int orignal, int current, int sum, int[] probilities){

        if(current == 1){

            probilities[sum - orignal]++;

        }else{

            for(int i=1; i<= gMaxValue; i++){

                probility(orignal, current - 1, sum + i, probilities);

            }

        }

    }

     

    public void probility(int number, int[] probilities){

        for(int i=1; i<= gMaxValue; i++){

            probility(number,number, i,probilities);

        }

    }

     

    public void printProbability(int number){

        if(number < 1)

            return;

        int maxSum = number * gMaxValue;

         

        int[] probilities = new int[maxSum - number + 1];

        probility(number, probilities);

         

        double total = Math.pow(gMaxValue, number);

         

        for(int i=number; i<= maxSum; i++){

            double ratio = probilities[i - number] / total;

            System.out.println(i + ": " + ratio);

        }

    }

     

    public static void main(String[] args){

        int number = 5;

        new PrintSumProbabilityOfDices().printProbability(number);

    }

http://bylijinnan.iteye.com/blog/1428099

1.     public static void printProbabilityOfDice(int n){  
2.         if(n<1){  
3.             return;  
4.         }  
5.         double total=Math.pow(MAX, n);   
6.         int len=n*MAX-n*1+1;//the sum of n dices is from n*1 to n*MAX  
7.         int[] times=new int[len];  
8.         for(int i=1;i<=MAX;i++){//initial the first dice.  
9.             probabilityOfDice(n,i,n,0,times);//count the times of each possible sum  
10.         }  
11.         for(int i=0;i<len;i++){  
12.             System.out.println((i+n)+","+times[i]+"/"+total);  
13.         }  
14.           
15.     }  
16.     public static void probabilityOfDice(int n,int curDiceValue,int numOfDices,int curSum,int[] times){  
17.         if(numOfDices==1){  
18.             int sum=curSum+curDiceValue;  
19.             times[sum-n]++;//n*1 to n*MAX <---> 0 to len  
20.         }else{  
21.             int sum=curSum+curDiceValue;  
22.             for(int i=1;i<=MAX;i++){  
23.                 probabilityOfDice(n,i,numOfDices-1,sum,times);  
24.             }  
25.         }  
26.     } 

XX. 我们可以考虑用两个数组来存储骰子点数每一总数出现的次数。在一次循环中，第一个数组中的第n个数字表示骰子和为n出现的次数。那么在下一循环中，我们加上一个新的骰子。那么此时和为n的骰子出现的次数，应该等于上一次循环中骰子点数和为n-1、n-2、n-3、n-4、n-5与n-6的总和。所以我们把另一个数组的第n个数字设为前一个数组对应的第n-1、n-2、n-3、n-4、n-5与n-6之和。

上述代码没有在函数里把一个骰子的最大点数硬编码(hard code)为6，而是用一个变量g_maxValue来表示。这样做的好处时，如果某个厂家生产了最大点数为4或者8的骰子，我们只需要在代码中修改一个地方，扩展起来很方便。如果在面试的时候我们能对面试官提起对程序扩展性的考虑，一定能给面试官留下一个很好的印象。

public void printProbability_2(int number){

    if(number < 1)

        return;

    int maxSum = gMaxValue * number + 1;

    int[][] probilities = new int[2][maxSum];

    int flag = 0;

    for(int i=1; i<=gMaxValue; i++)

        probilities[flag][i] = 1;

     

    for(int i=2; i<= number; i++){

        for(int j = 0;  j<i; j++)

            probilities[1-flag][j] = 0;

        for(int j = i; j<=gMaxValue * i; j++){

            probilities[1-flag][j] = 0;

            for(int k=1; k<=j && k<=gMaxValue; k++)

                probilities[1-flag][j] += probilities[flag][j-k];

        }

        flag = 1 - flag;

    }

    double total = Math.pow(gMaxValue, number);

    for(int i=number; i< maxSum; i++){

        double ratio = probilities[flag][i] / total;

        System.out.println(i + ": " + ratio);

    }

}

XXX: DP
http://bylijinnan.iteye.com/blog/1428099

1.     /* 
2. 有k-1个骰子时，再增加一个骰子，这个骰子的点数只可能为1、2、3、4、5或6。那k个骰子得到点数和为n的情况有： 
3. (k-1,n-1)：第k个骰子投了点数1 
4. (k-1,n-2)：第k个骰子投了点数2 
5. (k-1,n-3)：第k个骰子投了点数3 
6. .... 
7. (k-1,n-6)：第k个骰子投了点数6 
8. 在k-1个骰子的基础上，再增加一个骰子出现点数和为n的结果只有这6种情况！ 
9. 所以：f(k,n)=f(k-1,n-1)+f(k-1,n-2)+f(k-1,n-3)+f(k-1,n-4)+f(k-1,n-5)+f(k-1,n-6) 
10. 初始化：有1个骰子，f(1,1)=f(1,2)=f(1,3)=f(1,4)=f(1,5)=f(1,6)=1。 
11.      */  
12.     public static void printProbabilityOfDice2(int n){  
13.         if(n<1){  
14.             return;  
15.         }  
16.         double total=Math.pow(MAX, n);   
17.         int maxSum=n*MAX;  
18.         double[][] f=new double[n+1][n*MAX+1];  
19.         for(int i=1;i<=MAX;i++){  
20.             f[1][i]=1;  
21.         }  
22.         for(int k=2;k<=n;k++){  
23.             for(int sum=n;sum<=maxSum;sum++){  
24.                 for(int i=1;sum-i>=1&&i<=MAX;i++){  
25.                     f[k][sum]+=f[k-1][sum-i];  
26.                 }  
27.             }  
28.         }  
29.           
30.         for(int sum=n;sum<=maxSum;sum++){  
31.             System.out.println(sum+","+f[n][sum]+"/"+total);  
32.         }  
33.     }

Read full article from 解题笔记（18）――n个骰子的点数 - wuzhekai的专栏 - 博客频道 - CSDN.NET