剪绳子后面的数学原理
剪绳子
http://www.nowcoder.com/questionTerminal/57d85990ba5b440ab888fc72b0751bf8
先来一个一般性问题:
周长一定为n,这时候长length与宽width在什么情况下,达到面积s最大
s = length * width
设length = x
则:width = n/2 - x
所以 s = x * (n/2 - x)
= -x^2 + n*x/2
求导s' = -2x + n/2
s' = 0 --> 得 x = n/4
(0,n/4)区间,s'>0,S单调递增
(n/4, n)区间,s'<0,S单调递减
n/4为极大值点
所以在长度x=n/4的时候,S的面积最大
width = n/2 - x
= n/2 - n/4
= n/4
所以width = length 的时候 s最大
通过一般性问题得出当定长的时候,截出的子段长度相等的时候,乘积最大
(通用性待数学求证)
基本不等式的定理可知:算术平均数 > 几何平均数
回到本题
绳子长度为n,分成m分,那先设每分长度为x, 份数m=n/x
那么结果就是 n/x个 x 相乘 f(x)=x^(n/x)
求导:如下图
更正一下2和3的取值
f(2) = 2^(n/2),f(3) = 3^(n/3)
所以问题就回到了n/3的个数上面
当n能被3整除的时候,乘积=3^(n/3)
当n除3余1的时候,这时候发现多了一个1,这个1是不是很鸡肋,但是把前面的一个3拿出来,把这个一个1和前面一个3 分解为2和2,就变大了,所以乘积为 3^(n/3 - 1) * 4
当n除3余2的时候,乘积为3^(n/3) * 2
public int cutRope(int target) { if(target<=0) return 0; if(target==1 || target == 2) return 1; if(target==3) return 2; int m = target % 3; switch(m){ case 0 : return (int) Math.pow(3, target / 3); case 1 : return (int) Math.pow(3, target / 3 - 1) * 4; case 2 : return (int) Math.pow(3, target / 3) * 2; } return 0; }