西安邮电大学
（计算机学院）
课内实验报告
实验名称：
专业名称：
班级：
学生姓名：
学号（8指导教师：
实验日期：2016年6月1日
一. 实验目的及实验环境
实验目的: 熟悉并掌握贪心算法
实验环境: windows7 vc6.0编译器
二. 实验内容
题目描述:
设n是一个正整数。现在要求将n分解成干互不相同的自然数的和，且使这些自然数的成绩最大。
算法设计:
对于给定的正整数n，编程计算最优分解方案。
三．方案设计
问题分析:
若a+b=n，则|a-b|越小，那么，a*b越大。
贪心策略:
将n分解成从2开始的连续自然数的和，优先的方式下均匀地分给前面各项。如果最后剩下一个数，将此数加到后项中。
例如: 对于8进行分解为2和3则剩下一个3；
然后2和3再分别从3中均匀地获得1最后变成3和4，最后剩下1加给4上。所以，最终分解成3和5，是8的分解为不相同的自然数乘机最大。 程序流程图:
否
是
否 是
四．测试数据及运行结果
1．正常测试数据（3组）及运行结果；
五．总结
1． 实验过程中遇到的问题及解决办法；
问题:逻辑不清晰。
解决办法:画出流程图
2．对设计及调试过程的心得体会。
贪心算法是从问题的某个初始解出发逐步，逼近给定的目标，以尽可能快地求得更好的解。当达到某一步不能继续前进时，算法停止。这时就得到了问题的一个解。但不能保证求得的解是最优的。贪心算法的优点在于时间复杂度低。贪心算法与其他最优化算法的区别在于:它具有不可后撤性，可以有后效性，一般情况下，不能满足最优化原理。贪心算法的特点就决定了它的使用范围，它一般不适用于解决可行性问题。仅适用于较容易得到可行性解得最优性问题。(这里较容易得到可行解得概念: 当前的策略选择后，不会或极少出现无解的情况。交互性题目，贪心算法是一个较好的选择。)
六．附录：源代码（电子版）
/*用贪心算法解题: 设n是一个正整数。
现在要求将n分解为若干互不相同的自然数的和，且使这些自然数的乘积最大*/ #define _CRT_SECURE_NO_WARNINGS
#include
void taixin(int n){
int a[100];//临时数组，保存分解后的数
int k = 1;//a数组的索引
int sum = 1;//最大乘积
int i;//索引
if (n
sum = n;
}
else{
a[1] = 2;
n -= 2;
while (n > a[k]){
k++;
a[k] = a[k - 1] + 1;
n = n - a[k];
}
if (n == a[k]){
a[k]++;
n--;
}//让最后一个先加1，其实算上后面的是加了2 for (i = 0; i
a[k - i]++;
}
for (i = 1; i
sum *= a[i];
}
printf("分解后的数:");
for (i = 1; i
printf("%d ",a[i]);
}
}
printf("\n最大的成绩: %d", sum);
getchar();
}
void main(){
int n;
char str[50];
sprintf(str,"%s","请输入一个正整数:");
printf(str);
scanf("%d",&n);
taixin(n);
getchar();
return 0;
}