贪心算法实验
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
实验报告题目
实验四 贪心算法
开课实验室:数学实验室 指导老师:韩逢庆 时间:2011.12 学院:理学院 专业:信息与计算科学 班级:2009级2班 姓名:古 月 学号:09180230
一、 实验目的
1(加深学生对贪心算法
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
方法的基本思想、基本步骤、基本方法的理解与掌握;
2(提高学生利用课堂所学知识解决实际问题的能力;
3(提高学生综合应用所学知识解决实际问题的能力。 二、 实验内容
题目见P143:4-16,4-23.
三、 实验要求
(1)用分治法求解最少加油次数和最少硬币个数问题;
(2 )再选择自己熟悉的其它方法求解本问题;
(3)上机实现所设计的所有算法;
四、 实验过程设计(算法设计过程)
(1) 最少加油次数
实验题目
一辆汽车加满油以后可以行使n公里，旅途中有若干个加油站，设计一个有效算法，指出应在哪些加油站停靠加油，使沿路加油次数最少。并证明算法能产生一个最优解。
过程设计
贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。比如说最少加油次数的问题。在这个算法中，我采用的贪心算法的策略。首先人机互动的设定加满油以后最长能够行使的距离，然后输入了各个站点之间的距离，在程序的设计中，首先检查了程序的可行性。要是遇到当某两个站点之间的距离大于汽车一次加油以后所能够行使的最大距离时，我们认为此问题是不可行的。这个在实际情况中也是很容易理解的。然后在满足可行性条件下，依次采用贪心算法对问题得以实现。采用s这个来保存现在车里面留下的油，当此时留下的有能够行驶完这一站点到下一站点之间的距离是，在这一站点的时候就不加油。但是若不能行使完这一段路程的时候，就加满油。核心算法如下:
for(i=0,s=0;i
n)
{
sum++;
s=a[i];
}
}
(2) 最少硬币个数问题
实验题目
考虑下面的用最少硬币个数找出n分钱的问题:
当使用2角5分，1角，5分和1分四种硬币面值时，设计一个找n
分钱的贪心算法，并证明算法能产生最优解。
过程设计
贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。比如说找最少硬币个数的问题。在算法的实现过程中，当剩余的钱数大于2角5分时，我们在记录找2角5分硬币的个数的变量里面加一，同时把剩余所找的钱的总数目也减2角5分。不断重复这个过程，直到剩余所需找的钱的数目小于2角5分时，在记录找1角硬币的个数的变量里面加一，同时把剩余所找的钱的总数目也减1角，不断重复这个过程，直到剩余所需找的钱的数目小于1角。5分和1分的硬币实现过程同上述过程一样，一直执行到所剩的钱的数目为0，此时停止计算，得到最优解。
五、 实验结果分析
(1)最少加油次数
当加油后行驶的最大距离小于相邻站点的最小值时，此时，可行，求解结果如下:
当加油后行驶的最大距离大于相邻站点的最小值时，此时，没用可行性，为边沿情况，求解结果如下:
(分析时空复杂性，设计测试用例及测试结果)
On()时间复杂性:该算法的时间复杂度为
O(1) 空间复杂性分析:该算法的空间复杂度为
(2)最少硬币问题
当输入的找零钱数为正常的时候的运行情况如下:
当输入的找零钱数为不正常的时候(为负)的运行情况如下:
(分析时空复杂性，设计测试用例及测试结果)
On()时间复杂性:该算法的时间复杂性为
O(1)空间复杂性分析:该算法的空间复杂性为
六、 实验体会
贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题，相容活动安排问题
等。这样和采用动态规划的算法相比，算法的思想更加的简单，实现起来更加的容易。
但是也要明确贪心算法和动态规划的主要区别。及0-1背包问题可以用动态规划算法求解，但是贪心选择算法却不能用动态规划算法求解。因为贪心算法无法最终将背包装满，部分闲置的背包空间使得每公斤背包空间的价值降低了。
七、 附录:(源代码)
(1) 最少加油次数
具体算法的实现如下:
#include
void main()
{
int n,m,a[100],i,s,sum=0,j;
cout<<"请输入沿途的站点数和每一次加油以后可以行使的路程数"<>n;
cin>>m;
cout<<"沿途的站点数为:"<>a[i];
}
for( i=0;i<=n;i++)
{
cout<<"第"<m)
{
sum=-1;
break;
}
if(sum!=-1)
{
for(i=0,s=0;in)
{
sum++;
s=a[i];
}
}
}
if(sum==-1)
cout<<"没有可行性"< main()
{
double n,m,a,b,c,d,f;
a=b=c=d=0;
cout<<"请输入应找的钱!"<>n;
if(n<=0)
cout<<" 您输入的数据有错!"<=2.5)
{
a++;
m=m-2.5;
}
while(m>=1)
{
b++;
m=m-1;
}
while(m>=0.5)
{
c++;
m=m-0.5;
}
while(m>=0.1)
{
d++;
m=m-0.1;
}
f=a+b+c+d;
cout<<"应找的最少的硬币个数为:"<
本文档为【贪心算法实验报告】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483