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