算法趣题:证明所有乘积的总和和分拆的方式无关


有 n 枚硬币堆在一起。把它们任意分成两堆,并计算出这两堆的硬币数的乘积。然后,任意选择其中的一堆硬币,把它继续分成两个更小的堆,并计算出这两堆的硬币数的乘积。不断这样做下去,直到最后每堆都只剩一枚硬币为止。求证:把途中产生的所有乘积全部加在一起,结果是一个定值,它不随分法的改变而改变。
各抒己见。

趣味 算法

izanami 12 years, 6 months ago

这个问题有一个异常帅的秒杀方法。每次把一堆硬币分成两堆后,计算两堆硬币数量的乘积,实际上相当于是在计算有多少对硬币在这一步被分开了。最后所有乘积的总和,也就是在整个过程中被分开的硬币对的总数。然而, n 枚硬币之间共有 C(n, 2) = n(n - 1) / 2 个硬币对,所有的硬币对最终都被分开了,因而问题的答案就是 n(n - 1) / 2 ,这不随分法的变化而变化。

其实,借助几何构造,这个问题也有一个非常直观的秒杀方法

请输入图片描述

如图,初始时线段的总长为 n ,那么我们就作一个边长为 n 的等腰直角三角形。如果把线段分成了 x 和 y 两段,由此产生的乘积 xy 就对应于左图的等腰直角三角形中阴影矩形的面积。继续细分两个子线段,也就相当于递归地处理两个剩余的空白三角形。当所有子线段都被分到无穷短时,矩形面积的总和将会无穷接近于整个等腰直角三角形的总面积,也就是 n x n/2 。

死神的影子 answered 12 years, 6 months ago

Your Answer