<分区>
我最近面试了 Microsoft，他们问了我以下难题，我必须为此编写算法和随附的测试用例。我无法破解它，它对我来说仍然是一个谜。
问题陈述:
香槟金字塔是由香槟酒杯制成的金字塔，每个香槟酒杯的容量都相等，比如 n。 金字塔从顶层的一个玻璃杯开始，第二层是两个玻璃杯，然后是下面的三个，依此类推直到无限层。因此，金字塔的层 x 具有 x 编号。香槟酒杯。
源源不断的香槟从顶层倾泻而下，滴落到下层。在给定水平 i 下，香槟在玻璃杯中的分布是多少。
问题非常抽象，这些都是我得到的所有输入。
标签 algorithm
<分区>
我最近面试了 Microsoft，他们问了我以下难题，我必须为此编写算法和随附的测试用例。我无法破解它，它对我来说仍然是一个谜。
问题陈述:
香槟金字塔是由香槟酒杯制成的金字塔，每个香槟酒杯的容量都相等，比如 n。 金字塔从顶层的一个玻璃杯开始，第二层是两个玻璃杯，然后是下面的三个，依此类推直到无限层。因此，金字塔的层 x 具有 x 编号。香槟酒杯。
源源不断的香槟从顶层倾泻而下，滴落到下层。在给定水平 i 下，香槟在玻璃杯中的分布是多少。
问题非常抽象，这些都是我得到的所有输入。
最佳答案
答案是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) 是第 n 个 binomial number对于级别 i 多项式。正如@veredmarald 在评论中指出的那样，该分布函数实际上是 Binomial Distribution对于 p = 1/2，因此给你 flow(i)~Bin(i-1,1/2)
关于algorithm - 香槟金字塔分布拼图，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12721730/