第n杯水

gistfile1.md

###第n杯水分析###

####原题 有一座金字塔，从上到下，第一层有一个杯子、第二层有两个杯子，依次类推。对杯子进行编号，有如下的形状：

		1
	2		3
4		5		6

每个杯子的容量为C升，从塔顶倒下L升水，当1号杯子满了之后，会等量溢出到2号和3号杯子。当2号和3号满了，2号溢出到4号和5号，3号溢出到5号和6号，注意5号接受来自两个杯子的水。依次类推。给定C和L，请问，第n杯里有多少水。

####分析 这个类型的题目，关键点就是明了水倒下来的过程。我们这里做简单的分析， 假设L>C, 如果L<=C,则除了1号杯子，其他的都是0。

• 1号倒满，剩下L-C升，然后分两半进入2号和3号:(L-C)/2
• 2号和3号如果还能够倒满，则2号溢出((L-C)/2-C)L，3号溢出同样多
• 4号为((L-C)/2-C)L/2, 5号为((L-C)/2-C)L，6号为((L-C)/2-C)L/2

假设f(n)表示，当水进入n号杯中，还没有溢出到下面杯子时的水量。根据上面的分析：f(4)=(f(2)-C)/2。含义是2中的水，留下可以容纳的容量C，分为两份，一份进入4号杯，一份进入5号杯。5号杯接受来自2号和3号溢出的水，则,f(5) = (f(2) + f(3))-C。进行递归：

• f(2)=(f(1)-C)/2
• f(3)=(f(1)-C)/2
• f(1)=L

分析完毕，递归过程如上。在具体的实现中，我们采用自顶向下的方法，定义数组A，A[i]表示f(i)。

金字塔深度	0	1	1	2	2	2
杯号	1	2	3	4	5	6
A索引	0	1	2	3	4	5

观察上面的表格，我们会发现，一个规律，i号杯深度为h，则i号中溢出的水，将平分进入：

• i + h + 1
• i + h + 2

比如，文章开始的图中，3号杯进入5号和六号，3号杯的h为1，则

• 5 = 3 + 1 + 1
• 6 = 3 + 2 + 2

利用这个技巧，可以在数组中存储树形的金字塔，并且可以很方便的找到孩子节点。

计算出所有的A[i]之后，要得到最后的答案，还有一部之遥。即：

• A[i] >= C ? C : A[i]

【分析完毕】