(贪心算法实验报告.docVIP

实验报告题目 实验四 贪心算法 开课实验室：数学实验室 指导老师： 时间：20.12 学院：理学院 专业：信息与计算科学 班级：200级班 姓名： 学号：for(i=0,s=0;in;i++) { s=s+a[i]; if(sn) { sum++; s=a[i]; } } 最少硬币个数问题 实验题目 考虑下面的用最少硬币个数找出n分钱的问题： 当使用2角5分，1角，5分和1分四种硬币面值时，设计一个找n分钱的贪心算法，并证明算法能产生最优解。 过程设计 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。比如说找最少硬币个数的问题。在算法的实现过程中，当剩余的钱数大于2角5分时，我们在记录找2角5分硬币的个数的变量里面加一，同时把剩余所找的钱的总数目也减2角5分。不断重复这个过程，直到剩余所需找的钱的数目小于2角5分时，在记录找1角硬币的个数的变量里面加一，同时把剩余所找的钱的总数目也减1角，不断重复这个过程，直到剩余所需找的钱的数目小于1角。5分和1分的硬币实现过程同上述过程一样，一直执行到所剩的钱的数目为0，此时停止计算，得到最优解。 实验结果分析 （1）最少加油次数 当加油后行驶的最大距离小于相邻站点的最小值时，此时，可行，求解结果如下： 当加油后行驶的最大距离大于相邻站点的最小值时，此时，没用可行性，为边沿情况，求解结果如下： （分析时空复杂性，设计测试用例及测试结果） 时间复杂性：该算法的时间复杂度为 空间复杂性分析：该算法的空间复杂度为 （2）最少硬币问题 当输入的找零钱数为正常的时候的运行情况如下： 当输入的找零钱数为不正常的时候（为负）的运行情况如下： （分析时空复杂性，设计测试用例及测试结果） 时间复杂性：该算法的时间复杂性为 空间复杂性分析：该算法的空间复杂性为 实验体会 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题，相容活动安排问题等。这样和采用动态规划的算法相比，算法的思想更加的简单，实现起来更加的容易。 但是也要明确贪心算法和动态规划的主要区别。及0-1背包问题可以用动态规划算法求解，但是贪心选择算法却不能用动态规划算法求解。因为贪心算法无法最终将背包装满，部分闲置的背包空间使得每公斤背包空间的价值降低了。 附录：（源代码） 最少加油次数 具体算法的实现如下： #includeiostream.h void main() { int n,m,a[100],i,s,sum=0,j; cout请输入沿途的站点数和每一次加油以后可以行使的路程数endl; cinn; cinm; cout沿途的站点数为：nendl; cout每加满一次油可以行使的路程数为mendl; cout请一次输入第零站到第N站之间的距离endl; for(i=0;i=n;i++) { cina[i]; } for( i=0;i=n;i++) { cout第i站到第i+1站之间的距离为a[i]endl; } for(j=0;jn;j++) if(a[j]m) { sum=-1; break; } if(sum!=-1) { for(i=0,s=0;in;i++) { s=s+a[i]; if(sn) { sum++; s=a[i]; } } } if(sum==-1) cout没有可行性endl; else cout沿途的最少加油次数为sumendl; } （2）最少硬币问题 具体算法的实现如下： #includeiostream.h main() { double n,m,a,b,c,d,f; a=b=c=d=0; cout请输入应找的钱!endl; cinn; if(n=0) cout 您输入的数据有错!endl; m=n; while(m=2.5) { a++; m=m-2.5; } while(m=1) { b++; m=m-1; } while(m=0.5) { c++;