c++ - 求 {E1,..En} (E1+E2+..En​​=N, N is given) 具有以下性质 E1* E2*..En 是最大值

Question

给定数字 N，编写一个程序计算具有以下属性的数字 E1、E2、...En:

1) N = E1 + E2 + ... + En;
2) E1 * E2 * ... En为最大值。
3) E1..En, 是整数。没有负值:)

你会怎么做？我有一个基于 divide et impera 的解决方案但我想检查是否是最优的。

Example: N=10

5,5        S=10,P=25
3,2,3,2    S=10,P=36

Answer 1

不需要算法，数学直觉可以自己搞定:

第 1 步:证明数字大于 3 的结果集至多与只有 3 和 2 的结果集一样好

给定结果集中的任意数字 x，人们可能会考虑将其分成两个数字是否更好。

总和应该仍然是x。

• 当 x 为偶数时，t 的最大值 (x - t) 达到 t = x/2 ，除了特殊情况x = 2，然后它大于x，并且对于特殊情况 x = 4，等于 x(见注释 1)。
• 当 x 为奇数时，t 的最大值 (x - t) 达到 t = (x ± 1)/2.

这说明了什么？只是你的最终集合中应该只有 3 和 2，否则它是次优的(或等同于最优集合)。

第 2 步:你应该有尽可能多的 3

现在，因为 3² > 2³，只要余数不为 1，你应该有尽可能多的 3。

结论:对于每个 N >= 3:

• 如果N = 0 mod 3，则结果集只有3
• 如果 N = 1 mod 3，则结果集有一对 2(或一对 4)，其余为 3
• 如果N = 2 mod 3，则结果集有一个2，其余为3

请更正此帖。我编写结构良好的数学证明的时代已经很远了......

注 1:(2,4) 是唯一一对不同的整数，使得 x^y = y^x。你可以证明:

x^y = y^x
y ln(x) = x ln(y)
ln(x)/x = ln(y) / y

并且函数 ln(t)/t 在其全局最大值之后严格递减，达到 2 和 3 之间，因此如果您想要两个不同的整数，例如 ln(x)/x = ln(y)/y，其中之一必须小于或等于 2。由此您可以推断只有 (2,4) 有效