香槟塔分配难题

Question

香槟塔分配难题

algorithm

3

我最近参加了微软的面试，他们问了我下面这个难题，需要我编写算法和相应的测试用例。可惜我无法解决它，这仍然是一个谜团。

问题陈述：

香槟金字塔是由香槟杯制成的金字塔，每个杯子的容量相等，称为n。金字塔从顶层开始，有一个杯子，第二层有两个杯子，然后下面有三个杯子，以此类推，直到无限层。金字塔的第x层有x个香槟杯。

稳定的香槟流从顶层倒下，向下流淌到较低的层。给定某一层i，香槟在杯子中的分布情况是什么。

这个问题很抽象，以上就是我收到的所有输入。

- Azeem

猜想这取决于香槟如何从每个杯子中溢出来... - nneonneo

我向面试官问了同样的问题，但他只告诉我这会按比例溢出到下一层的杯子里。 - Azeem

他所说的比例是什么意思？我认为答案基本上就是帕斯卡三角形（每行除以2^行），这正是我会给出的答案，但是（与许多面试问题一样）它相当模糊。 - nneonneo

正是我的观点。我试图促使他了解“比例”的含义，但他没有再解释了。 :( - Azeem

1

类似于这个问题：[在金字塔结构中查找第i杯中的水量？]（https://dev59.com/PGbWa4cB1Zd3GeqPacy_） - Markus Jarderot

2个回答

1

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

玻璃的容积是有限的。

- Aki Suihkonen

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

我相信答案是正态分布。

看一下这个图表：

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

Let's say you have a flow of X. 1 will flow into 2,3 uniformly, thus each gets 1/2X. Each will flow uniformly to the glasses below it, so 4 gets 1/4X, 6 gets 1/4X and 5 gets 2*1/4X= 1/2X. At next level - the same principle applies.

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