今日面试题:第n杯水

有一座金字塔,从上到下,第一层有一个杯子、第二层有两个杯子,依次类推。对杯子进行编号,有如下的形状:

1
2 3
4 5 6

每个杯子的容量为C升,从塔顶倒下L升水,当1号杯子满了之后,会等量溢出到2号和3号杯子。当2号和3号满了,2号溢出到4号和5号,3号溢出到5号和6号,注意5号接受来自两个杯子的水。依次类推。给定C和L,请问,第n杯里有多少水。

重出江湖分析

原题

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

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

分析

这个题目的描述,是将具体的问题一般化了。掌握了,这个问题的分析,就可以对这类问题通吃。一个具体的情况是什么呢?两个色子,每个色子六面,同时抛,求朝上数字和大于某一个值的概率。这个情况比较简单,两个色子同时抛,一共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,与穷举方法一致。

【分析完毕】

本文来自微信:待字闺中,2013-07-30发布,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”。