香槟金字塔分布之谜

Question

我最近采访了微软，他们问我下面的难题，我必须为它写一个算法和附带的测试用例。我无法破解它，它对我来说仍然是一个谜。

问题陈述：

香槟金字塔是由香槟玻璃杯组成的金字塔，每个玻璃杯的容量相等，表示n。金字塔从顶层的一个玻璃杯，第二层的两个玻璃杯，然后是下面的三个玻璃杯开始，以此类推，直到无限的层次。因此，金字塔的第x层有x。香槟酒杯。

香槟源源不断地从顶层倾倒下来，滴落到较低的楼层。在给定的第I级，香槟在玻璃杯中的分布是什么？

这个问题非常抽象，这些就是我得到的所有输入。

Answer 1

我相信答案是Normal Distribution。

看一下图表：

           |1|
           ---
        |2|   |3|
        ---   ---
     |4|   |5|   |6|
     ---   ---   ---
   |7|  |8|   |9|   |10|
   ---  ---   ---   ----

假设你有一个X流

1将均匀地流到2,3，因此每个都会得到1/2X

每一个都会均匀地流到它下面的眼镜上，所以4得到1/4X，6得到1/4X，5得到2*1/4X= 1/2X

在下一级-同样的原则适用于：

7 gets 1/8X
8 gets 1/8X from 4 and 1/4X from 5, totaling 3/8X,
9 gets same as 8 and 10 same as 8.

在无穷远时，它应该收敛于正态分布。

在任何有限数i -它应该是f(i,n)/ 2^(i-1)，其中f(i,n)是水平i多项式的第n个binomial number。正如@veredmarald在注释中指出的那样，对于p= 1/2，该分布函数实际上是Binomial Distribution，因此可以得到flow(i)~Bin(i-1,1/2)

Answer 2

我相信分布是均匀的，即使香槟的流量遵循二项分布，在无穷大处接近正态分布。

玻璃的大小是有限的。