找到金字塔结构中第i个杯子里的水量？

Question

这个问题是在论坛上提出的.有什么建议？

有一个金字塔,1级杯子,2级2级,3级3级等等.它看起来像这样

  1
 2 3
4 5 6

每个杯子都有容量C.你从顶部倒入L升水.当杯子1被填满时,它同样地溢出到2,3杯,当它们被填满时,杯子4和6仅从2和3获得水,但是5从两个杯子获得水,依此类推.现在给出C和L.找到第二杯中的水量？

Answer 1

每个玻璃都有一个进入的流动,玻璃中的一定量的水,以及一些流出的流动(溢出).

如果每个玻璃杯可以包含1个单位的水,并且您倒入15个单位的水,则会得到以下结果(括号中的溢出量):

Incoming flow = 15, capacity = 1

Level 1:               1(14)
Level 2:           1(6)     1(6)
Level 3:       1(2)     1(5)     1(2)
Level 4:    1(1)   1(2.5)  1(2.5)    1(1)
Level 5:   1  1(0.75)  1(1.5)  1(0.75)   1
Level 6:  0 0.375 1(0.125) 1(0.125) 0.375 0
Level 7: 0 0  0.0625   0.125    0.0625   0 0

在进入流到第一电平是L的进入流从玻璃c上水平r是Fin(c, r),并且可以写为:

Fin(0, r) = 0
Fin(r+1, r) = 0
Fin(1, 1) = L
Fin(c, r) = Fout(c - 1, r - 1)/2 + Fout(c, r - 1)/2

所述的水的量在该玻璃是:

A(c, r) = Min(C, Fin(c, r))

而传出的流量是:

Fout(c, r) = Max(0, Fin(c, r) - C)

我没有看到任何明显的评估公式,A(c, r)而不是递归地进行评估.

要从索引到行和玻璃位置,您可以执行以下操作:

index = r*(r-1)/2 + c

r = floor((1 + sqrt(8*index - 7))/2)
c = index - r*(r-1)/2

(indexes start with 1)