前言
今天参加了携程的笔试,编程题第一题一开始想错了方向,花费了很多时间(虽然第二题就是给时间也不一定做得出来,(⊙﹏⊙)b)。
下面记录一下这个小插曲。
正文
题目要求
将指定的正整数n分解成若干个互不相同的自然数的和,且使这些自然数的乘积最大
人家给了个输入输出的例子,如下:
输入15
输出 144
言下之意就是在自然数之和为15的这些数字中,乘积最大的一对是
2 3 4 6
思路
为了使得这些自然数之和的乘积最大,那么这些数字应该尽可能的接近。
下面举几个小例子:
n=10
2+3+4 = 9
// 剩下的那个1补到4上面
2+3+5
这个时候最大的乘积变成了30
n = 18
2+3+4+5 = 14
//按照刚才的思路, 剩下的4 添加到5上面
2+3+4+9
此时最大的乘积结果为216
那么这时的结果是最大的吗?
答案是否定的,因为刚才是从下标为2开始的。如果下标从3,从4开始呢,我们来看下效果。
3+4+5+6 -->> 最大结果为:360
4+5+6+7>18则进行去尾加和
4+5+9 -->> 最大结果为: 180
剩下的其实就不用考虑了。
核心
经过刚才的铺垫,这下不难理解了。最笨的方法就是不断的递增下标,然后记录每一个下标对应的最大值。存储起来,然后找到这些最大值中最大的那个,就是我们要求的结果了。
代码如下:
def mutl(ls):
result = 1
for item in ls:
result *= item
return result
def compute(n, step):
path = []
cursum = 0
for index in range(step, n):
if cursum > n:
last = path.pop()
path.append(path.pop() + n - (cursum - last))
break
path.append(index)
cursum += index
return mutl(path)
def my(n):
total = []
maxvalue = 0
for step in range(int(n/2)):
item = compute(n, step)
total.append(item)
maxvalue = max(total)
return maxvalue
n = 15
result= my(n)
print(result)
运行结果:
144
测试
再来多测几组数据。
- n=10
30
- n=18
360
这下,可以啦。需要注意的是:
递增下标到n的一半的位置就可以了,否则结果会不正确,这是因为计算每次的step的时候会把第一个给算进去,所以导致结果偏大。
总结
就携程的笔试题而言,前面部分的问答题和选择题还算是中规中矩,比较偏重于理论和实践。
编程题就真的是考验算法的了。大部分的笔试题都是动态规划类型的。我本人比较偏重于开发方向,所以参加这种笔试题真的是有点力不从心。
不管怎么说,算法是很有必要的。多学点,肯定没错,说不一定以后就用得到了。
我, 还有很长的路要走啊。