转载

别人家的面试题：自然数拆分求最大乘积

原文： https://www.h5jun.com/post/integer-break.html

今天是部门活动，去了石林峡，爬山累成狗。不过，在这么好的天气里，外出走走实在是一件有益身心健康的事情。爬山回来之后，身体虽疲惫，思路竟格外敏捷，正好将这篇文章一气呵成。

别人家的面试题：自然数拆分求最大乘积

自然数拆分（ Integer Break ）

给定一个自然数 n (n ≥ 2），将它拆分成 不少于 两个自然数之和，对这些拆分后的自然数求积，要求算出最大的乘积。

例如：

n = 2，得到 1（2 = 1 + 1）
n = 10，得到 36（10 = 3 + 3 + 4）

解题思路

这道题，咋一看之下，比前两期的题目似乎要难一些。因为对于一个较大的自然数，存在很多种拆分方法，怎么找到乘积最大的拆分方法呢？

简单一点考虑？遍历出一个自然数 n 的所有拆分方法，然后找出乘积最大的那个？这么做当然可行，但看起来这似乎不像是什么好办法。有没有突破点呢？同样按照惯例，大家先思考30秒钟再往下看——

寻找规律

你是不是心里猜到了什么？是不是 “那样” 的方法能得到最大乘积？先别着急，我们来找一些数寻找一下规律，下面列出从 2 到 10 的所有结果：

2 = 1 + 1 -> 1
3 = 2 + 1 -> 2
4 = 2 + 2 -> 4
5 = 3 + 2 -> 6
6 = 3 + 3 -> 9
7 = 3 + 2 + 2 -> 12
8 = 3 + 3 + 2 -> 18
9 = 3 + 3 + 3 -> 27
10 = 3 + 3 + 2 + 2 -> 36

从上面是不是发现了什么规律？我想这对我们来说应该不难——

月影猜想：

对任意自然数 n （n > 3）要拆解得到最大乘积，该拆解方案只包含 2、3 两个数字（这里附加一个规则，假定我们总是把“4”拆成“2+2”，因为不影响乘积大小）。
并且这个拆解方案中 2 出现的次数少于 3 次。

证明猜想

让我们从数学上证明 “月影猜想” ，这并不难，第一步让我们先复习一下自然数的一些小的基本性质。

定理：任意两个不小于 2 的自然数 a、b，有 a + b ≤ a * b。

上面这个定理不难证明：假设 2 ≤ a ≤ b，那么有 a + b ≤ b + b ≤ 2 * b ≤ a * b

因此，从上面的定理得到——

推论：对于任意自然数 n， n ≥ 4，必然存在一个自然数拆分，将 n 拆分成两个自然数 a 和 b，使得 a * b ≥ n。

根据上面的推论我们可以证明猜想的“1.”即最大乘积的拆解方案中只包含 2、3 两个数字。

接着，我们可以通过 反证法 证明如果拆解方案包含的 2 不少于 3 次，就不是乘积最大的拆解方案：

假设自然数 n 的乘积最大拆解方案是： n = 3 + …… + 2 + 2 + 2 它的乘积是 m = 3 * …… * 2 * 2 * 2 = (3 * ……) * 8 ，那么我们用 3 + 3 替换掉最后的 2 + 2 + 2 ，它的乘积 m' = 3 * …… * 3 * 3 = (3 * ……) *9 ，显然 m' > m，因此 m' 是比 m 乘积更大的拆解方案，所以 m 不是乘积最大的拆解方案，于是我们证明了猜想的“2.”即拆解方案中 2 出现的次数少于 3 次，也是正确的。

以上证明了 “月影猜想” 的正确性，于是我们可以进一步推导出 n 拆解后最大乘积的 通项公式 ：

f(2) = 1
f(3) = 2
f(3k) = 3 ^k (k ≥ 2)
f(3k+1) = 2 * 2 * 3 ^k-1 (k ≥ 1)
f(3k+2) = 2 * 3 ^k (k ≥ 1)

所以，我们得到了这个问题的简单解法，它的时间和空间复杂度是 O(1)：

/**  * @param {number} n  * @return {number}  */ var integerBreak = function(n) {   if(n < 3) return 1;   if(n === 3) return 2;   var k =  Math.floor(n / 3);   var r = n % 3;   if(r === 0) return Math.pow(3, k);   else if(r === 1) return 4 * Math.pow(3, k - 1);   else return 2 * Math.pow(3, k); };

以上就是月影的解题思路，注意中间的数学证明和推导过程。我们当然可以只通过找规律来建立通项公式，忽略推导内容，一样可以把这道题解出来。然而月影一直以来认为：只有经过数学证明的模型才是完美的，才经得起考验，而这些证明并不困难，不需要多么高深的数学知识。不管是做前端还是其他软件开发领域， 数学，对我们都是非常重要的 。

以上是 leetcode 算法面试系列的第三期，在下一期里，我们讨论另外一道考验算法效率的题目。这道题看似非常简单——给一个数值数组 NumArray，能够快速求出 sumRange(i, j)，即从第 i 个元素到第 j 个元素中间的所有元素之和。似乎没有什么值得思考的，然而如果 数组非常大 ， sumRange 被执行次数非常多，我们又如何来做优化呢？大家可以想一想，期待我们的下一期。

对于本期和下一期的问题，有任何想法，欢迎留言讨论~~

原文 http://www.75team.com/post/integer-break.html

正文到此结束