algorithm - 找出液体到达第 n 个杯子所需的时间

Question

这是我从老师那里得到的额外作业。

杯子以树状结构排列，大概是这样的:

  1
 2 3
4 5 6

填满第 1 杯需要 10 秒，然后溢出到第 2 杯和第 3 杯。(假设没有溢出)。由于水流被分开，杯子 2 和 3 然后需要 20 秒才能填满。总的来说，通过将水倒入杯子 1 来注满杯子 3，需要 30 秒。第 5 杯需要 50 秒，依此类推。

这是一个表格，其中包含流体到达下一个杯子所需的行和秒数的正确值。

    1(10)
 2(30) 3(30)
4(70) 5(50) 6(70)

提出的问题是针对边界为 r <= 50 的任意行数解决此问题:给定行 r 和杯子 c，这个杯子需要多长时间才能装满？

我已经为这个问题绞尽脑汁大约 24 小时了，但我离解决它还差得很远。我知道这与 Pascal 的三角形和递归有关。我还想指出，这不是评分作业，而只是老师提出的一个未评分的有趣问题。

编辑:添加了更易于理解的数据结构以及我的笔记。

1:   1
2:  1 2
3: 1 2 3

鉴于这种结构，我已经根据以下公式得出水流分配到其下方杯子的比例与帕斯卡三角形相关

h(r,c)=P(n,c)/2^(n-1)
where P(n,c) returns the number contained in the according row in Pascal's triangle

然后我用它通过以下公式计算秒数:

t(r,c)=(2^(n-1)/P(n,c))*10

前 3 行是这样，但之后就分崩离析了，因为一个杯子上方的 2 个杯子的水流不会同时开始。

我还尝试了一个递归函数来计算它的父函数，它们位于 (r-1,c) 和 (r-1,c-1) 并应用前面的公式，但由于我的原因，它是不正确的上面已经解释过了。

Answer 1

此采访问题的答案在 http://www.careercup.com/question?id=9820788 中给出。和 http://www.careercup.com/question?id=22191662 .

它也在 http://www.geeksforgeeks.org/find-water-in-a-glass/ ，为了完整起见，这里是我在评论中链接的相关 SO 问题:Find the amount of water in ith cup in a pyramid structure? .