在金字塔结构中找到杯子里的水量吗？

Question

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

有一个金字塔，一杯在第二层，两杯在第二层，三杯在第三层，等等。看上去像这样

1 2 3 4 5 6

每个杯子都有容量C。你从上面倒L升水。当杯1被填满时，它同样溢出到杯2,3，当它们被填满时，杯4和6只从2和3杯中得到水，而5从两个杯子中得到水，以此类推。现在给C和L .Find杯里的水量？

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。来自r级别上的玻璃流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)

Answer 2

一些想法：(1)重要的是知道哪两个杯子是第一个杯子的输入。(2)重要的是要知道从你的左边给你带来水的最小左边，以及从你的右边给你带来水的水平(3)，所以你需要知道哪一个杯子能给你倒水。如果你开始从0开始编号的话，这就更容易了。杯ith将填充(i-1)*2+1和i*2，这意味着kth杯将接收来自( k%2=1) (k-1)/2和(k+1)/2 ( k%2=0) k/2和k/2+1 (4)的水，你应该检查对于任何L，你将计算L-左和L-Lright的差。当水为正数时，用2^n除以计算出的差，其中n是杯子的水平。

Answer 3

如果你把金字塔建模成一个图表，问题就会转化为广度优先搜索。当您遍历每个节点时，获取其邻居并存储它们的溢出量。如果邻居已被前一个节点检索(在5个节点的情况下将发生此情况，因为节点2和节点3对其具有边缘)，则必须根据其容量和已填充的内容更新溢出(通过节点2；假设节点2在节点3之前被遍历)。