贪心算法计算最优分解方案

《贪心算法计算最优分解方案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、西安邮电大学（计算机学院〉课内实验掇告实验名称：贪心算法计算最优分解方案专业名称：班级：学生姓名：学号（8位L指导教师：实验日期：2016年6月1日一.实验目的及实验环境实验目的：熟悉并掌握贪心算法实验环境:windows7vc6.0编择器二.实验内容题□描述：设n是一个正整数。现在要求将n分解成干互不相同的自然数的和，且使这些自然数的成绩最大。算法设计：对于给定的正整数n,编程计算最优分解方案。三.方案设计问题分析：若a+b=n,贝越小，那么，a*b越大。贪心策略：将n分解成从2开始的连续自然数的和，优先的方

2、式下均匀地分给前而各项。如果最后剩下一个数，将此数加到后项中。例如：对于8进行分解为2和3则剩卜*一个3;然后2和3再分别从3中均匀地获得1最后变成3和4,最后剩下1加给4上。所以，最终分解成3和5,是8的分解为不相同的自然数乘机最人。程序流程图：否是否是结來一.测试数据及运行结果1.正常测试数据(3组)及运行结粜;整324正:2:个霧一的成入后的请八召取二.总结1.实验过程屮遇到的问题及解决办法；问题:逻辑不清晰。解决办法:画出流程图2.对设计及调试过程的心得体会。贪心算法是从问题的某个初始解出发逐步，逼近给

3、定的目标，以尽可能快地求得更好的解。当达到某一步不能继续前进吋，算法停止。这时就得到了问题的一个解。但不能保证求得的解是最优的。贪心算法的优点在于时问复杂度低。贪心算法与其他最优化算法的区别在于:它具冇不町后•撤性，可以冇活效性，一般情况下，不能满足敁优化原理。贪心算法的特点就决定了它的使用范围，它一般不适用于解决nJ•行性问题。仅适用于较容易得到可行性解得最优性问题。(这里较容易得到可行解得概念：当前的策略选择后，不会或极少出现无解的情况。交互性题0，贪心算法足一个较好的选择。)三.附录：源代码(电子版)/*

4、用贪心算法解题：设n是一个正整数。现在耍求将n分解为若干互不相同的U然数的和，且使这些CJ然数的乘积最大*/#define_CRT_SECURE_NO_WARNINGS#includevoidtaixin(intn){inta[100];//临吋数组，保存分解后的数intk=l;//a数组的索引intsum=1;//最大乘不只inti;//索引if(n<5){//如果小于5,那么都是乘积是l*n;sum=n;}else{a[l]=2;n-=2;while(n>a[k]){k++;a[k]=a[

5、k-1]+1;n=n-a[k];}if(n==a[k]){a[k]++;n-；}//让最后一个先加1，其实算上后而的是加了2for(i=0;i

6、整数:")；printf(str);scanf(H%dn,&n);taixin(n);getchar();return0;