算法：剪绳子，使乘积最大

# 算法：剪绳子，使乘积最大

# 题目描述

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

# 示例：

输入，8。输出则为，18

# 思路

问题类似于定周长求最大面积的问题（例如给定四边形周长，求最大面积），当k[0] == k[1]==,==k[m]时乘积最大，设k[0]=x，那么n=x*m,乘积可以用下式表示

f(x)=(x)^(n/x)

下面是f(x)的导数：

乘积函数在n/m=e的时候，取得最大值,可知，当x∈(0,e)时f(x)单调递增，当x>e时，单调递减，因此，在x=e时取得最大值，e≈2.718,是自然对数。

从函数图像上也可以看出这一点

f(x)的函数图像：

又因为x的取值只能为整数，且f(3)>f(2)，所以，当n＞3时，将n尽可能地分割为3的和时，乘积最大。当n＞3时，有三种情况，即n%3 == 0, n%3 == 1, n%3==2,如下所示

上式中除法向下取整

当n≤3时，只有

当n==2时f(x)=1；
当n==3时f(x)=2;

# 代码

function cutRope(number)
{
    if (number === 2)return 1;
    if (number === 3) return 2;
    if (number % 3 === 0) return Math.pow(3, number/3);
    if (number % 3 === 2) return 2 * Math.pow(3, parseInt(number/3));
    if (number % 3 === 1) return 4 * Math.pow(3, parseInt(number/3) -1);
    
}

# 参考资料：

https://www.nowcoder.com/questionTerminal/57d85990ba5b440ab888fc72b0751bf8?f=discussion

# 数学知识

分母求导：

复合函数求导常见做法：

← sort 基础 →