算法题3：携程实习生笔试：求一个整数的加数的最大乘积（允许加数相同和不同）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法题3：携程实习生笔试：求一个整数的加数的最大乘积（允许加数相同和不同），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4256字，纯文字阅读大概需要7分钟。
内容图文
给出一个整数n，将n分解成至少两个整数之和，使得这些整数的乘积最大化，输出能获得的最大的乘积。
(1) 允许存在相同的加数
(2) 不允许存在相同的加数
1. 允许存在相同的因子
给出一个整数n，将n分解成至少两个整数之和，使得这些整数的乘积最大化，输出能获得的最大的乘积。
输入描述 ： 输入为一个整数
输出描述 ：输出为一个整数
样例
in: 10
out: 36
(10=5+5=2+3+2+3, 36=232*3)
思路：
给你一个数n = a + b，a * b何时最大？
学过基本不等式的都知道，a?b<=(a+b)/2，当 a=b 时取等号。因此，当 a 和 b 尽量靠近时，乘积 a?b 才最大。
那如果n可以分解成多个数字相加，那么这些数字相乘什么时候最大?
答案很明显，当然是因子尽可能相近时，乘积才最大。
所谓相近，就是任意两个数之差的绝对值小于等于1，那么这些数字必然可以分解成x, x, x, …,x + 1, x + 1, …这种形式。
Q:为什么乘积存在极大值？
A:把一个正整数N拆成若干正整数只有有限种拆法，所以存在最大乘积。
推广：如果情况的种类数有限，那么一定存在极值；但是如果无限，也可能存在极值。
在 知乎 https://www.zhihu.com/question/30071017/answer/47584748 中，作者给出了一种清奇的做法，让我醍醐灌顶。摘录要点如下[资料3]：
把一个正整数N拆成若干正整数只有有限种拆法，所以存在最大乘积。 假设N=n1?+…+nk?，并且n1?×…×nk?是最大乘积。
结论：
- 乘积中不存在1或者超过（包含）5的整数。
- 选用尽量多的3，直到剩下2或者4时用2；**
证明：
显然1不会出现在其中;
如果存在nk?≥5，则我们将nk?改为3+nk??3。而3×(nk??3)=3nk??9>nk??1。所以不存在大于等于5的因子;
4=2+2，乘积不变，不妨设没有因子4；
如果有三个以上的2， 那么3×3>2×2×23×3>2×2×2，所以替换成3乘积更大
对于2.证明，可能一开始看不懂，这里详细再说一下：
因为nk?≥5，所以2nk?≥10，所以(3nk??9)?nk?=2nk??9≥10?9=1>0，所以3nk??9≥nk?。
根据这种清奇的思路：最大乘积的分解式中，只可能存在3和2两者元素；尽可能取3，剩下的再取2，用Python 3.6 编程如下：
import sys
# import numpy as np
# 这里用自己编写的 power 函数，当然也可以用numpy.power。
def power(a, b):
if type(b)==int:
n = 1
for i in range(b):
n*=a
return n
if __name__=='__main__':
data = sys.stdin.readline().strip()
number = int(data)
max_product = 0
p = 0
q = 0
if number <=3:
max_product = number
else:
res = number % 3
if res==0: # 如果正好能整除
p = number / 3
if res==1: # 如果余1，那3+1要拆分成2+2
p = number // 3 - 1
q = 2
if res==2: # 如果余2，那么就直接用2
p = number // 3
q = 1
# max_product = np.power(3, p) * np.power(2, q)
max_product = power(3, p) * power(2, q)
max_product = int(max_product)
print('Max product is ', max_product)
2. 不允许存在相同的加数
给出一个整数n(n>=5)，将n分解成至少两个整数之和，使得这些整数的乘积最大化，输出能获得的最大的乘积。
输入描述 ： 输入为一个整数
输出描述 ：输出为一个整数
样例
in: 10
out: 30
(10=2+3+5, 30=235)
思路:这种题目没有巧妙的解法，只能手写前面几种基本情况，找找规律。例如：
#3=1+2
#4=1+3
5=2+3
6=2+4
7=3+4
8=3+5
9=2+3+4
10=2+3+5
11=2+4+5
12=3+4+5
13=3+4+6
由此可见：
（1）加数从2开始逐渐递增，2, 3, 4, … 尽量使得元素是连续的。连续意味着靠近，因此乘积会比较大。这一点与第一种情况是相似的。
（2）当按照2, 3, 4, …展开，如果剩余数值还大于0的话，那么就将其从后往前均匀分配到各个元素。
注意：考虑到一种特殊情况，当多出来的数比前面已有元素的个数大1时（比如8=3+4+1的情况），先给已有元素的最大元素加1（8=3+5），然后再均匀分配到每个元素。
编码如下：
coding: utf-8
Python 3.6
import sys
# import numpy as np
def power(a, b):
if type(b)==int:
n = 1
for i in range(b):
n*=a
return n
if __name__=='__main__':
data = sys.stdin.readline().strip()
number = int(data)
max_product = 1
flag = []
k = 2
if number<2:
print('Wrong! Input number must be larger than 1!')
else:
while(number >=k):
flag.append(k)
number -= k
k += 1
# 说明有剩余的
if number > 0:
# 说明这时候剩余的数正好比已有的元素个数多1，所以要先给最后一个元素加1
if number - 1 == len(flag):
flag[-1] += 1
number -= 1
for i in range(number):
flag[-1 - i] += 1
# 分解完以后，就求乘积
for x in flag:
max_product *= x
print('Max product is %s'%max_product + ' = ', end='')
for x in flag:
print(str(x) + '*', end='')
print('\b')
【参考资料】
[1] 正整数分解使得乘积最大问题
[2] 招商银行信用卡2018春季招聘研发(第一批)编程题 - 题解
[3]【整理自用】清奇思路（三）正解整数分解成不同加数的最大乘积
[4] 知乎：有一个正整数N可以分解成若干个正整数之和，问如何分解能使这些数的乘积最大？求详细解释。
内容总结
以上是互联网集市为您收集整理的算法题3：携程实习生笔试：求一个整数的加数的最大乘积（允许加数相同和不同）全部内容，希望文章能够帮你解决算法题3：携程实习生笔试：求一个整数的加数的最大乘积（允许加数相同和不同）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。