3

最近、Microsoft にインタビューしたところ、次のパズルを尋ねられました。そのために、アルゴリズムと付随するテスト ケースを作成する必要がありました。私はそれを解読することができませんでしたが、それはまだ私にとってパズルです.

問題文 ：

シャンパン ピラミッドは、シャンパン グラスで作られたピラミッドで、それぞれの容量は n とします。ピラミッドは、最上段のグラス 1 杯、第 2 レベルのグラス 2 杯、その下のグラス 3 杯というように、無限のレベルまで続きます。したがって、ピラミッドのレベル x には x no があります。シャンパン グラスの。

シャンパンの絶え間ない流れが最上階から注がれ、それが下の階に滴り落ちます。特定のレベルでのグラス内のシャンパンの分布は何ですか 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.

無限大では、正規分布に収束するはずです。

任意の有限数-はレベル多項式の 2番目の二項数であるi必要がf(i,n)/ 2^(i-1)あります。コメントで@veredmaraldが示したように、その分布関数は実際にはp = 1/2の二項分布であるため、f(i,n)niflow(i)~Bin(i-1,1/2)

于 2012-10-04T07:01:03.630 に答える
1

シャンパンの流れは二項分布に従い、無限大では正規分布に近づきますが、分布は均一であると思います。

ガラスのサイズには有限の体積があります。

于 2012-10-04T07:30:19.310 に答える