六年级杂题
#枚举法
题目
把正整数 20 拆成若干个正整数之和（拆成几个都可以，顺序不计），使得这些正整数的乘积尽可能大。最大的乘积是多少？
解法
- 1.分析：假设最优拆分中某个加数 a ≥ 4，可以把它换成 2 和 a−2，两段之和仍是 a，但乘积变成 2(a−2) = 2a−4；由于 a ≥ 4 时 2a−4 ≥ a，所以乘积不会变小；当 a > 4 时严格变大。于是最优解中每个加数都 ≤ 3。
拆法 20 = 3+3+3+3+3+3+2 = 3⁶ · 2 = 1458 最大 对比 4+4+4+4+4 = 4⁵ = 1024 对比 5+5+5+5 = 5⁴ = 625 对比全是 2（10 个 2） = 2¹⁰ = 1024 “多用 3，余 2 时留 1 个 2”
- 2.另外 1 显然不应该出现（把 1+x 合并成 x+1 不会增加和，但乘积由 1·x = x 变成 x+1 > x）。所以最优解每个加数只能是 2 或 3。✖️× 1458最大乘积
结论
- 3.在 2 和 3 之间，同样大小的和，用 3 得到的乘积更大：3 × 3 = 9 > 2 × 2 × 2 = 8（同为 6）。于是应尽量多用 3，除非剩余不够摆下 3 个 2。
- 4.20 ÷ 3 = 6 余 2，恰好余 2，不需要把 3 换成 2+2+2。
- 5.因此拆法为 6 个 3 加 1 个 2：20 = 3 × 6 + 2。
- 6.最大乘积 = 3⁶ × 2 = 729 × 2 = 1458。
练一练
把正整数 19 拆成若干个正整数之和，使乘积最大。最大乘积是多少？