数学之于编程

电玩女神 2022-11-11 14:56 104阅读 0赞

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

####  解题思路： ####

*  设将长度为 nnn 的绳子切为 aaa 段：

n=n1+n2+...+nan = n\_1 + n\_2 + ... + n\_a n=n1\+n2\+...\+na

*  本题等价于求解：

max⁡(n1×n2×...×na)\\max(n\_1 \\times n\_2 \\times ... \\times n\_a) max(n1×n2×...×na)

> 以下数学推导总体分为两步：① 当所有绳段长度相等时，乘积最大。② 最优的绳段长度为 333 。

#####  数学推导： #####

*  以下公式为“算术几何均值不等式” ，等号当且仅当 n1=n2=...=nan\_1 = n\_2 = ... = n\_an1=n2=...=na 时成立。

n1+n2+...+naa≥n1n2...naa\\frac\{n\_1 + n\_2 + ... + n\_a\}\{a\} \\geq \\sqrt\[a\]\{n\_1 n\_2 ... n\_a\} an1\+n2\+...\+na≥an1n2...na

> **推论一：** 将绳子 **以相等的长度等分为多段** ，得到的乘积最大。

*  设将绳子按照 xxx 长度等分为 aaa 段，即 n=axn = axn=ax ，则乘积为 xax^axa 。观察以下公式，由于 nnn 为常数，因此当 x1xx^\{\\frac\{1\}\{x\}\}xx1 取最大值时， 乘积达到最大值。

xa=xnx=(x1x)nx^a = x^\{\\frac\{n\}\{x\}\} = (x^\{\\frac\{1\}\{x\}\})^n xa=xxn=(xx1)n

*  根据分析，可将问题转化为求 y=x1xy = x^\{\\frac\{1\}\{x\}\}y=xx1 的极大值，因此对 xxx 求导数。

ln⁡y=1xln⁡x取对数1yy˙=1x2−1x2ln⁡x对 x 求导=1−ln⁡xx2y˙=1−ln⁡xx2x1x整理得\\begin\{aligned\} \\ln y & = \\frac\{1\}\{x\} \\ln x & \\text\{取对数\} \\\\ \\frac\{1\}\{y\} \\dot \{y\} & = \\frac\{1\}\{x^2\} - \\frac\{1\}\{x^2\} \\ln x & \\text\{对 $x$ 求导\} \\\\ & = \\frac\{1 - \\ln x\}\{x^2\} \\\\ \\dot \{y\} & = \\frac\{1 - \\ln x\}\{x^2\} x^\{\\frac\{1\}\{x\}\} & \\text\{整理得\} \\end\{aligned\} lnyy1y˙y˙=x1lnx=x21−x21lnx=x21−lnx=x21−lnxxx1取对数对x求导整理得

*  令 y˙=0\\dot \{y\} = 0y˙=0 ，则 1−ln⁡x=01 - \\ln x = 01−lnx=0 ，易得驻点为 x0=e≈2.7x\_0 = e \\approx 2.7x0=e≈2.7 ；根据以下公式，可知 x0x\_0x0 为极大值点。

y˙\{>0,x∈\[−∞,e)<0,x∈(e,∞\]\\dot \{y\} \\begin\{cases\} > 0 & , x \\in \[- \\infty, e) \\\\ < 0 & , x \\in (e, \\infty\] \\\\ \\end\{cases\} y˙\{ >0<0,x∈\[−∞,e),x∈(e,∞\]

*  由于切分长度 xxx 必须为整数，最接近 eee 的整数为 222 或 333 。如下式所示，代入 x=2x = 2x=2 和 x=3x = 3x=3 ，得出 x=3x = 3x=3 时，乘积达到最大。

y(3)=31/3≈1.44y(2)=21/2≈1.41y(3) = 3^\{1/3\} \\approx 1.44 \\\\ y(2) = 2^\{1/2\} \\approx 1.41 y(3)=31/3≈1.44y(2)=21/2≈1.41

*  口算对比方法：给两数字同时取 666 次方，再对比。

\[y(3)\]6=(31/3)6=9\[y(2)\]6=(21/2)6=8\[y(3)\]^6 = (3^\{1/3\})^6 = 9 \\\\ \[y(2)\]^6 = (2^\{1/2\})^6 = 8 \[y(3)\]6=(31/3)6=9\[y(2)\]6=(21/2)6=8

> **推论二：** 尽可能将绳子以长度 333 等分为多段时，乘积最大。

#####  切分规则： #####

1.  **最优：** 333 。把绳子尽可能切为多个长度为 333 的片段，留下的最后一段绳子的长度可能为 0,1,20,1,20,1,2 三种情况。
2.  **次优：** 222 。若最后一段绳子长度为 222 ；则保留，不再拆为 1+11+11\+1 。
3.  **最差：** 111 。若最后一段绳子长度为 111 ；则应把一份 3+13 + 13\+1 替换为 2+22 + 22\+2，因为 2×2>3×12 \\times 2 > 3 \\times 12×2>3×1。

#####  算法流程： #####

1.  当 n≤3n \\leq 3n≤3 时，按照规则应不切分，但由于题目要求必须剪成 m>1m>1m>1 段，因此必须剪出一段长度为 111 的绳子，即返回 n−1n - 1n−1 。
2.  当 n>3n>3n>3 时，求 nnn 除以 333 的 整数部分 aaa 和 余数部分 bbb （即 n=3a+bn = 3a + bn=3a\+b ），并分为以下三种情况：
    
     *  当 b=0b = 0b=0 时，直接返回 3a3^a3a；
     *  当 b=1b = 1b=1 时，要将一个 1+31 + 31\+3 转换为 2+22+22\+2，因此返回 3a−1×43^\{a-1\} \\times 43a−1×4；
     *  当 b=2b = 2b=2 时，返回 3a×23^a \\times 23a×2。

![Picture1.png][]

#####  复杂度分析： #####

*  **时间复杂度 O(1)O(1)O(1) ：** 仅有求整、求余、次方运算。
    
     *  [求整和求余运算][Link 1]：资料提到不超过机器数的整数可以看作是 O(1)O(1)O(1) ；
     *  [幂运算][Link 2]：查阅资料，提到浮点取幂为 O(1)O(1)O(1) 。
 *  **空间复杂度 O(1)O(1)O(1) ：** 变量 `a` 和 `b` 使用常数大小额外空间。

####  代码： ####

> Python 中常见有三种幂计算函数： **`*`** 和 **`pow()`** 的时间复杂度均为 O(log⁡a)O(\\log a)O(loga) ；而 **`math.pow()`** 始终调用 C 库的 `pow()` 函数，其执行浮点取幂，时间复杂度为 O(1)O(1)O(1) 。

*  python
 *  java

class Solution:
 def cuttingRope(self, n: int) -> int:
 if n <= 3: return n - 1
 a, b = n // 3, n % 3
 if b == 0: return int(math.pow(3, a))
 if b == 1: return int(math.pow(3, a - 1) * 4)
 return int(math.pow(3, a) * 2)

class Solution {
 public int cuttingRope(int n) {
 if(n <= 3) return n - 1;
 int a = n / 3, b = n % 3;
 if(b == 0) return (int)Math.pow(3, a);
 if(b == 1) return (int)Math.pow(3, a - 1) * 4;
 return (int)Math.pow(3, a) * 2;
 }
 }

> 数学推导需要一定的知识基础。下面分享一种基于贪心思想的思路，个人认为适合于时间有限情况下的快速解题。

#####  贪心思路： #####

> 设一绳子长度为 nnn ( n>1n>1n>1 )，则其必可被切分为两段 n=n1+n2n=n\_1+n\_2n=n1\+n2 。 
> 根据经验推测，切分的两数字乘积往往原数字更大，即往往有 n1×n2>n1+n2=nn\_1 \\times n\_2 > n\_1 + n\_2 = nn1×n2>n1\+n2=n 。
> 
> * **例如绳子长度为 666 ：** 6=3+3<3×3=96 = 3 + 3 < 3 \\times 3 = 96=3\+3<3×3=9 ；
> * **也有少数反例，例如 222 ：** 2=1+1>1×1=12 = 1 + 1 > 1 \\times 1 = 12=1\+1>1×1=1 。

*  **推论一：** 合理的切分方案可以带来更大的乘积。

> 设一绳子长度为 nnn ( n>1n>1n>1 )，**切分为两段** n=n1+n2n=n\_1+n\_2n=n1\+n2 ，**切分为三段** n=n1+n2+n3n=n\_1+n\_2+n\_3n=n1\+n2\+n3 。 
> 根据经验推测，**三段** 的乘积往往更大，即往往有 n1n2n3>n1n2n\_1 n\_2 n\_3 > n\_1 n\_2n1n2n3>n1n2 。
> 
> * **例如绳子长度为 999 ：** 两段 9=4+59=4+59=4\+5 和 三段 9=3+3+39=3+3+39=3\+3\+3，则有 4×5<3×3×34 \\times 5 < 3 \\times 3 \\times 34×5<3×3×3 。
> * **也有少数反例，例如 666 ：** 两段 6=3+36=3+36=3\+3 和 三段 6=2+2+26=2+2+26=2\+2\+2，则有 3×3>2×2×23 \\times 3 > 2 \\times 2 \\times 23×3>2×2×2 。

*  **推论二：** 若切分方案合理，绳子段切分的越多，乘积越大。

> 总体上看，貌似长绳子切分为越多段乘积越大，但其实到某个长度分界点后，乘积到达最大值，就不应再切分了。  
> **问题转化：** 是否有**优先级最高的长度** xxx 存在？若有，则应该尽可能把绳子以 xxx 长度切为多段，以获取最大乘积。

*  **推论三：** 为使乘积最大，只有长度为 222 和 333 的绳子不应再切分，且 333 比 222 更优 *（详情见下表）* 。

<table> 
 <thead> 
 <tr> 
 <th>绳子切分方案</th> 
 <th>乘积</th> 
 <th>结论</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>2=1+12 = 1 + 12=1+1</td> 
 <td>1×1=11 \times 1 = 11×1=1</td> 
 <td>222 不应切分</td> 
 </tr> 
 <tr> 
 <td>3=1+23=1+23=1+2</td> 
 <td>1×2=21 \times 2 = 21×2=2</td> 
 <td>333 不应切分</td> 
 </tr> 
 <tr> 
 <td>4=2+2=1+34=2+2=1+34=2+2=1+3</td> 
 <td>2×2=4&gt;1×3=32 \times 2 = 4 &gt; 1 \times 3 = 32×2=4&gt;1×3=3</td> 
 <td>444 和 222 等价，且 2+22+22+2 比 1+31+31+3 更优</td> 
 </tr> 
 <tr> 
 <td>5=2+3=1+45=2+3=1+45=2+3=1+4</td> 
 <td>2×3=6&gt;1×4=42 \times 3 = 6 &gt; 1 \times 4 = 42×3=6&gt;1×4=4</td> 
 <td>555 应切分为 2+32+32+3</td> 
 </tr> 
 <tr> 
 <td>6=3+3=2+2+26=3+3=2+2+26=3+3=2+2+2</td> 
 <td>3×3=9&gt;2×2×2=83 \times 3 = 9 &gt; 2 \times 2 \times 2 = 83×3=9&gt;2×2×2=8</td> 
 <td>666 应切分为 3+33+33+3 ，进而推出 333 比 222 更优</td> 
 </tr> 
 <tr> 
 <td>&gt;7&gt;7&gt;7</td> 
 <td>...</td> 
 <td>长绳（长度&gt;7）可转化为多个短绳（长度1~6），因此肯定应切分</td> 
 </tr> 
 </tbody> 
</table>

[Picture1.png]: /images/20221022/3315ff91a8f14f4bafaf9129c23d8578.png
[Link 1]: https://stackoverflow.com/questions/35189851/time-complexity-of-modulo-operator-in-python
[Link 2]: https://stackoverflow.com/questions/32418731/java-math-powa-b-time-complexity