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

1、西安邮电大学（计算机学院）课内实验报告实验名称：贪心算法计算最优分解方案专业名称：班级：学生姓名：学号（8位）：指导教师：实验日期：2016年6月1日一.实验目的及实验环境实验目的：熟悉并掌握贪心算法实验环境：windows7 vc6.0 编译器实验内容题目描述:设n是一个正整数。现在要求将n分解成干互不相同的自然数的和，且使这 些自然数的成绩最大。算法设计：对于给定的正整数n，编程计算最优分解方案问题分析:若a+b=n,则|a-b|越小，那么,a*b越大。贪心策略:将n分解成从2开始的连续自然数的和，优先的方式下均匀地分给前面各 项。如果最后剩下一个数，将此数加到后项中。例如：对于8进行分解

2、为2和3则剩下一个3;然后2和3再分别从3中均匀地获得1最后变成3和4,最后剩下1加给4 上。所以，最终分解成3和5,是8的分解为不相同的自然数乘机最大。程序流程图:开始输入 n,k=l,sum=lk+;ak = ak -1 + 1； n = n - ak;否是结束四测试数据及运行结果1 正常测试数据（3组）及运行结果;输入sum /for (i = 0; i < n; j+) ak - i+; for (i = 1; i <- k; i+) sum *= aFJ；五总结1 实验过程中遇到的问题及解决办法；问题: 逻辑不清晰。解决办法 : 画出流程图2对设计及调试过程的心得体会。贪

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

4、设 n 是一个正整数。现在要求将 n 分解为若干互不相同的自然数的和，且使这些自然数的乘积最 大*/#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>void taixin(int n)int a100;/ 临时数组，保存分解后的数int k = 1;/a 数组的索引int sum = 1;/ 最大乘积int i;/ 索引if (n < 5)/如果小于 5，那么都是乘积是1*n ；sum = n;elsea1 = 2;n -= 2;while (n > ak)k+;ak = ak - 1 + 1;n = n - ak;if

5、(n = ak)ak+;n-;/ 让最后一个先加 1，其实算上后面的是加了 2for (i = 0; i < n; i+)ak - i+;for (i = 1; i <= k; i+)sum *= ai;printf(" 分解后的数 :");for (i = 1; i <=k; i+)printf("%d ",ai);printf("n最大的成绩 : %d", sum);getchar();void main()int n;char str50;sprintf(str,"%s"," 请输入一个正整数 :