剪绳子后面的数学原理

剪绳子

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;
    }
全部评论
是3的n/3次方,不是n的n/3次方
5 回复 分享
发布于 2020-06-07 11:16
喜欢,你这个很硬核
4 回复 分享
发布于 2020-06-04 10:20
请问f(2)=1和f(3)=2这个是怎么得来的?
2 回复 分享
发布于 2020-06-27 00:34
5*5*5小于2*3*2*3*2*3
2 回复 分享
发布于 2020-07-27 10:08
太强了,点赞👍
2 回复 分享
发布于 2020-09-01 10:37
你好,请问一下switch之后为甚=什么有个return 0;语句,我觉得前面判断条件已经包含了所有的可能情况了,但是不加又通不过
点赞 回复 分享
发布于 2020-05-08 22:22
由算术不等式、调和不等式与平均不等式之间的关系可以知道取等长的时候乘积最大
点赞 回复 分享
发布于 2020-06-17 23:02
太强了
点赞 回复 分享
发布于 2020-06-20 21:07
你这只证明了等分的情况下啊,如果不等分你怎么证明?
点赞 回复 分享
发布于 2020-06-21 16:32
按这个算f(2)=2^(n/2);f(3)=3^(n/3);答主这里好像把求x和求剪绳子的答案弄混了;
点赞 回复 分享
发布于 2020-06-29 23:00
可太秀了
点赞 回复 分享
发布于 2020-06-30 23:22
如果想要打印出每段的长度,应该怎么做?
点赞 回复 分享
发布于 2020-07-02 10:25
楼主拥有很强的数学思维
点赞 回复 分享
发布于 2020-08-01 09:16
我和楼主你刚开始想的一模一样,也是上来求极值,找俩点比一下优先选3,但是总感觉这样不太严谨,首先因为先默认了每一份都一样长,而且结果与n无关,虽然x按整数考虑了,但是算出来的结果n/x也就是绳子的条数不能保证是整数,如果后面用取余来考虑,相当于是和前面的求解割裂了,因为每一份等长已经不成立了,我觉得用归纳法很容易理解,首先项数有限那么一定存在一个最优解,那么最优解里某项如果是1都可以和任一项结合使得乘积增大,所以不能是1,然后反证法或者函数图也很容易证明每一项肯定小于4,所以每项必定是2,3如果优先考虑2,那么情况1最后一定是若干个2和一个1,显然1可以和2结合成3;情况2是若干个2,那么这个绳子只要大于4,也就是从6开始,若干个2肯定不是最大的,因为拿出一个2分给另外两个2,就变成了了三个2和2个3的区别,所以优先考虑2肯定不是最大,所以应该优先考虑3,这样感觉合理一点
点赞 回复 分享
发布于 2020-08-03 23:34
我是通过列举了各种情况,然后猜选3,。然后又处理了一些特殊情况。一开始还可疑惑,不过竟然AC了,看了楼主的推导之后,感觉就明白了
点赞 回复 分享
发布于 2020-08-14 10:26
算法来源于数学啊
点赞 回复 分享
发布于 2020-12-14 16:33
tql
点赞 回复 分享
发布于 2021-03-27 11:12
好家伙,你中学时数学一定很好
点赞 回复 分享
发布于 2021-04-03 17:00
你是真的强哈
点赞 回复 分享
发布于 2021-05-07 18:35
好厉害呀 太棒了了
点赞 回复 分享
发布于 2021-06-18 11:47

相关推荐

斑驳不同:还为啥暴躁 假的不骂你骂谁啊
点赞 评论 收藏
分享
孤寡孤寡的牛牛很热情:为什么我2本9硕投了很多,都是简历或者挂,难道那个恶心人的测评真的得认真做吗
点赞 评论 收藏
分享
评论
180
12
分享
牛客网
牛客企业服务