武汉轻工大学——计算机算法实验(三).doc

武汉轻工大学 计算机算法实验报告三 姓名： 刘文斌 院系：数学与计算机学院 班级：软件工程13 03班 学号： 1305110050 2015.12.12 实验三、贪心算法实验 实验目的 通过具体的问题掌握贪心算法的基本设计思想。 实验环境 VC6.0 实验内容 问题描述： 1、设n是一个正整数。现在要将n分解为若干互不相同的自然数的和，且使这些自然数的乘积最大。 解题思路：毫无疑问将n分解为更小的数（除1外）相加，这些分解得到数的乘积最大。但是题目要求这些数互不相同，因此，我们只需要从最小的数2开始（贪心策略），以2作为因子，再分解差值n-2；再以3为因子，分解差值…；也就是n:=n-2，n:=n-3，n:=n-4,….. 在分解的过程中注意，保证剩余的差值大于1且不能与前面的因子相同。 2、给定N个正整数组成的一个数列，进行如下的操作：每次擦去其中两个数，设为a和b，然后在数列中加入一个新数a*b+1，如此下去直至只剩下一个数。设计一个算法，求出最后剩下的数的最大可能值。 提示：与哈夫曼编码算法类似。 实验要求 1任选一题完成； 2写出程序并在vc6下编译和调试通过，通过具体的输入来测试程序并给出结果； 3按规定的实验格式写出实验报告。 附一、贪心算法的一般模式伪代码： greedy(A,n) //A表示决策集合 { solution = ?; for(i=1;i=n;i++) { x=select(A); if(feasible(solution, x)) { solution=union(solution, x); A=exclude(A, x); } } return solution; } 附二、贪心算法求解第一题 代码如下： #includestdio.h int greedy(int factors[],int n) { int i,x=2; for(i=0;in;i++) { if(n-xx) { factors[i]=x; n=n-x; x++; } else break; } factors[i++]=n; return i; } void main() { int a[3]; int n,j; int greedy(int factors[],int n); printf(请输入一个数:); scanf(%d,n); printf(%d=,n); int k=greedy(a,n); for(j=0;jk;j++) { printf(%d,a[j]); if(jk-1) printf(+); } } 运行结果： 实验总结： 通过这次实验我已经掌握贪心算法的基本设计思想。