正整数拆分乘积最大值的贪心策略证明与算法分析

Abstract

针对正整数拆分后各分项乘积最大化的经典数论与竞赛问题，以 GESP编程竞赛题目为研究背景，采用反证法、均值不等式、方差分析及微积分求导等方法开展严谨推导。首先通过反证法证明最优拆分不含数值 1 的拆分项；再利用均值不等式与方差最小化原理，证明固定项数时拆分只能由两个相邻整数构成；随后将离散整数问题连续化建模，构造单变量函数借助求导求解极值，确定自然常数 e 为最优拆分单元理论值，进而比对整数 2 和 3 的函数取值，得出优先拆分为 3，其次拆分为 2 的贪心规则。最终归纳出正整数按模 3 分类的乘积最大值通用计算公式，并对比动态规划、暴力枚举等解法，表明本文推导的贪心算法时间复杂度更优。研究验证了离散问题连续化求解的数学思维有效性，可为信息学竞赛同类题型提供理论依据与解题范式。

Keywords

• 整数拆分；乘积最大；均值不等式；微积分；贪心策略

References

1. GESP 编程能力等级认证考试大纲 [EB/OL]. 中国计 算机学会，2026.
2. 中国计算机学会 . CCF 全国青少年信息学奥林匹克竞赛 (NOI) 系列活动大纲 [EB/OL]. (2024-08-15)[2026-04-07].