You are given n dices each with heads numbered from 1 to m. You are to throw the n dices and note down the sum of the numbers on each of the n dices. You'll be give a number x and its a win if the sum obtained is greater than x. The problem is the find out the winning probability given n, m and x. Note 1<=n<=100, 1<=m<=10, m<=x<=n*m.

gistfile1.md

###Google面试题分析：色子问题

####原题

n个色子，每个色子m面，每一面的值分别是1-m。你将n个色子同时抛，落地后将所有朝上面的数字加起来，记为sum。给定一个数字x，如果sum>x，则你赢。给定n，m，x，求你赢的概率。

• 1<=n<=100
• 1<=m<=10
• m<=x<n*x

####分析

这个题目的描述，是将具体的问题一般化了。掌握了，这个问题的分析，就可以对这类问题通吃。一个具体的情况是什么呢？两个色子，每个色子六面，同时抛，求朝上数字和大于某一个值的概率。这个情况比较简单，两个色子同时抛，一共36种情况，注意这里有的和是相同的。此时，最少可以通过穷举的方法，得到答案。但是本题中的意思，显然是无法通过穷举呢？那该如何分析呢？

n个色子，每个色子m面。则一共有m^n中情况（类比上面分析的36种情况）。在这些里面，有多少个和是大于x的呢？假设，f(n,x)表示n个色子，所有朝上的数字和是x的情况数量。对于某一个色子，每一面朝上的概率是1/m。假设这个色子的k面朝上，1<=k<=m，则f(n,x) = sum{f(n - 1, x - k)} 1<=k<=m。递归的终止条件是，当只有一个色子的时候，f(1,k) = 1, 1<=k<=m，其他都是0

则最终的概率为(f(n, x + 1) + … + f(n, m*n)) / m^n。每一个大于x的和的可能情况数量之和除以总的情况数量。

以2个6面色子为例，验证上面的公式。

和	情况数
2	1
3	2
4	3
5	4
6	5
7	6
8	5
9	4
10	3
11	2
12	1

取和大于10的概率，即2/36+1/36 = 3/36 = 1/12。

根据上面的公式，(f(2, 11) + f(2, 12)) / 12

• f(2, 11) = f(1, 10) + f(1, 9) + f(1, 8) + f(1, 7) + f(1, 6) + f(1, 6) = 2
• f(2, 12) = f(1, 11) + f(1, 10) + f(1, 9) + f(1, 8) + f(1, 7) + f(1, 6) = 1

则概率为3/12，与穷举方法一致。

【分析完毕】