3

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

问题陈述 ：

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

源源不断的香槟从顶层倾泻而下，滴落到较低的楼层。在给定级别 i 的玻璃杯中香槟的分布是什么？

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

4

2 回答 2

10

我相信答案是正态分布。

看一下图表：

           |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)第nth 个二项式数。i正如@veredmarald 在评论中指出的那样，该分布函数实际上是p = 1/2 的二项分布，因此为您提供flow(i)~Bin(i-1,1/2)

于 2012-10-04T07:01:03.630 回答
1

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

玻璃尺寸具有有限的体积。

于 2012-10-04T07:30:19.310 回答