作业 6 贪心算法
题目 1：自然数加法分解求乘积最大值
（1）算法求解思路
已知，要让几数的乘积最大要使他们的值尽量接近。可知，在使分解后的数
乘积最大的条件下，可以得到如下结果：
1=1,
2=2,
3=2+1=3,
4=2+2=3+1=4；
5=2+3,
6=2+3+1=2+4,
7=2+3+2=3+4,
8=2+3+3=3+4+1=3+5,
9=2+3+4,
10=2+3+4+1=2+3+5
……
由以上结果，归纳总结可知，为使加法分解的结果最大，先令自然数 n 由从 2 开
始依次加 1 的整数组成，最后剩下一个数 temp,temp=n-sum((sum=2+3+4+…)<n),
再把 temp 的值分别加到之前分解的整数上，每个整数加一，从最大的整数开始，
直到把 temp 分配完毕，其结果则使分解得到的值最为接近，最终得到的乘积即
为最大值。
（2）执行过程分析
测试用例 1：10=2+3+5
输入：10
输出：30
在函数中，a[]数组用来存放整数 n 的加法分解结果，j 用来标识分解的个数，
sum 用来标识整数是否分解完毕，temp 用来存放整数分解为递增序列后剩余的值，
max 用来保 存乘 积的 最大 值。 先令 a[]数组依次存放从 2 到 i 的值，要求
(sum=(2+3+…+i)<n),然后令 temp=n-sum。更新 a[]数组，将 a[]数组中的值从
前到后依次加 1，直到 temp 的值分配完毕。最后，遍历 a[]数组，将分解结果相
乘，得到乘积的最大值 max。在测试用例 1 的输入下，其具体执行过程如下表 1-1
所示。
i
j
a[]
sum
temp
i
j
a[]
sum
temp
2
1
{2}
2
/
5
3
{2,3,4,5}
9
1
3
2
{2,3}
5
/
2
3
{2,3,5,5}
9
1
4
3
{2,3,4}
9
/
1
3
{2,3,5,5}
9
0
5
4
{2,3,4,5}
14
/
表 1-1 算法执行过程及其主要变量 1-1
所以，max=a[0]*a[1]*a[2]=30。
在 main 函数中，分别在第一个循环结束处、第二个循环结束处，通过调试
观察 i,j,a[],sum,temp 的值可以得到如图 1-1 到图 1-4 所示的结果，为截取的
部分运行结果截图，分别与表 1-1 中的变量变化过程相对应。程序执行结果如图
1-5 所示。
