最大乘积——练手

千年沉寂

一个正整数一般可以分为几个互不相同的自然数的和，如3=1+2，4=1+3，5＝1+4=2+3，6=1+5＝2+4，…。
现在的任务是将指定的正整数n分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大。
给定一正整数n(3<=n<10000),求解决方案和最大乘积。
如: n=10
解决方案： 2, 3, 5
最大乘积：30

千年沉寂

Python代码：

def Biggest(n):     result = []     for i in xrange(2, int(n / 2) + 2):         other = n - i         if other >= 0:             result.append(i)             n = n - i         else:             break     i = 0     while n > 0:         i -= 1         result[i % len(result)] += 1         n -= 1     s=reduce((lambda x,y: x * y), result)     return result,s print Biggest(10)

n=10的结果：

([2, 3, 5], 30)

[ 本帖最后由 千年沉寂 于 2009-4-19 20:12 编辑 ]

wzcsoft

恩

[ 本帖最后由 wzcsoft 于 2009-4-19 23:37 编辑 ]

guotie

算法高手。。。。

末手

初来乍到.来学习的.

teebye

应该是动态规划的思维来做
可惜方程式不会写

千年沉寂

应该算是贪心算法。。
这涉及到数学上的一些东西 哈哈
eg.
x+y=n
当x==y时 x*y取得最大值
假设n=12，那么6*6>5*7>4*8...