一个有趣的问题

[(ッ)]

三个柱子，每个上面有l <= m <= h个环

每次操作可以在两根不同柱子上各取下一个环；或者在一个柱子上取下一个环

问，最少需要操作多少次才能把3柱清空

一个显然的做法是递归。再有就是如果h >= l + m，结果也是显然的

[YWY]

不知道有没有简单公式，只涉及l, m , h的简单公式。

具体操作上，似乎是从环数最多的两个柱子上各取一个环（如果m和h都大于0），然后就是递归，每一步都是从环数最多的两个柱子上各取一个环（除非只剩一个柱子上有环）。

[kde23]

试解一下。 显然，要想操作次数少，就要尽量多的每次取双环，把取一个环的次数限制到最小。 直观的想法是把最多(h环）柱子上每次一环取一些后，剩下的可以每次两个取完， 这其实就是最优取法， 表述如下（注， 为清晰起见，把l,m,h改为大写表示）:

最小操作数为
H when H>=L+M
(L+M+H)/2 when H<L+M and (L+M+H） is even
(L+M+H+1)/2 when H<L+M and (L+M+H) is odd

证明：
用记号（x,y,z)表示一次在三个柱子分别取x,y,z个环的操作， 0<=x,y,z<=1, 且不同时为1
(1） 当 H>=L+M 时， 注意每次操作在第三个柱子上取的环数不能超过1，故总次数>=H。
另一方面，确实有如下方法用H次取完:
（1，0，1) L次
（0,1,1) M次
（0，0，1） H-L-M次

（2） 当 H<L+M 且 (L+M+H)为偶数时，则如下三个数都是非负整数:
p = （L+M-H)/2
q = (L+H-M)/2
r = (H+M-L)/2
取法
（1，1，0） p次
（1，0，1） q次
（0，1，1） r次
能把三个柱子都取完，且每次都是取两个环，已是最优取法。 次数为
p+q+r = (L+M+H)/2

（3） 当 H<L+M 且 (L+M+H)为奇数时。 由于总数为单数， 任何取法都至少有一次是只取一个。 把第三柱取掉一个环，则剩下的L,M,(H-1)环满足条件（2），用
(L+M+H-1)/2次可以取完。 因此最优取法的次数是
1 + (L+M+H-1)/2 = (L+M+H+1)/2

[YouHi]

我怎么记得谭浩强的Basic教材里就有这道题啊。