神刀安全网

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

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

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

自然数拆分( 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

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

月影猜想:

  1. 对任意自然数 n (n > 3)要拆解得到最大乘积,该拆解方案只包含 2、3 两个数字(这里附加一个规则,假定我们总是把“4”拆成“2+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 被执行次数非常多,我们又如何来做优化呢?大家可以想一想,期待我们的下一期。

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

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 别人家的面试题:自然数拆分求最大乘积

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址