《【精选资料】贪心算法实验报告.docx》由会员分享，可在线阅读，更多相关《【精选资料】贪心算法实验报告.docx（9页珍藏版）》请在三一文库上搜索。
1、实验报告题目实验四贪心算法开课实验室：数学实验室指导老师：韩逢庆时间：2011.12学院：理学院 姓名：古月专业：信息与计算科学学号：09180230班级:2009级2班一、 实验目的1 .加深学生对贪心算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2. 提高学生利用课堂所学知识解决实际问题的能力；3. 提高学生综合应用所学知识解决实际问题的能力。二、实验内容题目见 P143416,4-23.三、实验要求（1）用分治法求解最少加油次数和最少硬币个数问题；（2 ）再选择自己熟悉的其它方法求解本问题；（3）上机实现所设计的所有算法；四、实验过程设计（算法设计过程）（1）最少加油次数实验题
2、目一辆汽车加满油以后可以行使n公里，旅途中有若干个加油站，设计一个有效算法，指出应在哪些加油站停靠加油，使沿路加油次数最少。 并证明算法能产生一个最优解。过程设计 贪心算法总是作出在当前看来最好的选择。 也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部 最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽 然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。比如说最少加油次数的问题。在这个算法中，我采用 的贪心算法的策略。首先人机互动的设定加满油以后最长能够行使的 距离，然后输入了各个站点之间的距离，在程序的设计中，首先检查 了程序的可行性
3、。要是遇到当某两个站点之间的距离大于汽车一次加 油以后所能够行使的最大距离时，我们认为此问题是不可行的。这个 在实际情况中也是很容易理解的。 然后在满足可行性条件下，依次采 用贪心算法对问题得以实现。采用S这个来保存现在车里面留下的油， 当此时留下的有能够行驶完这一站点到下一站点之间的距离是，在这一站点的时候就不加油。但是若不能行使完这一段路程的时候，就加满油。核心算法如下：for(i=0,s=0;i Vn ;i+)s=s+ai;if(s>n)sum+;s=ai;(2)最少硬币个数问题实验题目考虑下面的用最少硬币个数找出 n分钱的问题：当使用2角5分，1角，5分和1分四种硬币面值时，设计
4、一个找 n 分钱的贪心算法，并证明算法能产生最优解。过程设计贪心算法总是作出在当前看来最好的选择。 也就是说贪心算法并不从 整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。 当然，希望贪心算法得到的最终结果也是整体最优的。 虽然贪心算法 不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优 解。比如说找最少硬币个数的问题。在算法的实现过程中，当剩余的 钱数大于2角5分时，我们在记录找2角5分硬币的个数的变量里面 加一，同时把剩余所找的钱的总数目也减 2角5分。不断重复这个过 程，直到剩余所需找的钱的数目小于 2角5分时，在记录找1角硬币 的个数的变量里面加一，同时把剩余所找
5、的钱的总数目也减 1角，不 断重复这个过程，直到剩余所需找的钱的数目小于 1角。5分和1分 的硬币实现过程同上述过程一样，一直执行到所剩的钱的数目为0，此时停止计算，得到最优解。五、实验结果分析（1）最少加油次数当加油后行驶的最大距离小于相邻站点的最小值时，此时，可行，求 解结果如下：11-GA,M吉设计和分析憾荀更DdIJg4 J&赴心6工H-口 牛冃冃201234567 uxwciw12345166 s禺 - -In 一一 -?7 VTk 王:以I为 6 N之之之之、N之油y IM1站站站站站站站站加C 12345678 P 静矿席4參至至至到到至l. a 由葫莎3占占占占占占占占
6、& S Q - S ? i - 20123456 7e7<L的的的的的的的C -:PJImTmi心日 一日 to当加油后行驶的最大距离大于相邻站点的最小值时，此时，没用可行性，为边沿情况，求解结果如下：设 并 分祈憶 1序gbug4-16"h肘 离 & 7巨 x 勺 o Wo N 和 虜 数 4行到 点以站 站为臺 的醫第 途点：_沿站一输4 入專次 输7途加一；y 2 643 TrXTrXTr 亠曷Iln = = = 一_ 一 o £ foK F “m m m JTTMm 一-CTr-(j到乙 占占占占占 1-i . 1234Si g.nS-.* =
7、b'elp'- y_Nato到到到JSB 6 -4 J占占占止 2 0 12 3 4 第(分析时空复杂性，设计测试用例及测试结果) 时间复杂性：该算法的时间复杂度为 O(n) 空间复杂性分析：该算法的空间复杂度为 0(1)(2)最少硬币问题当输入的找零钱数为正常的时候的运行情况如下:to COntinUe'G.R>设沪口分桁偉程序Cbugg-24心h也也1 1 0 e 緡有有有k 5 JBiB,B n .B 2 15 1 S JS P应PI"5算法设计和分析¾Debug4*24.ee-当输入的找零钱数为不正常的时候(为负)的运行情况如下:0为
8、数fil O wt »J A 0 fse 蹲鬻有有k S- / V- m 反 5 Ifflff'ffFl <5®角八各歳2 1 5 IS wes 什卤其苴其其Pr(分析时空复杂性，设计测试用例及测试结果)时间复杂性：该算法的时间复杂性为 O(n)空间复杂性分析：该算法的空间复杂性为 O(I)六、实验体会贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并 不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选 择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心 算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体 最优解。如单源最短
9、路经问题，最小生成树问题，相容活动安排问题等。这样和采用动态规划的算法相比，算法的思想更加的简单，实现起来更加的容易。但是也要明确贪心算法和动态规划的主要区别。及0-1背包问题可以用动态规划算法求解，但是贪心选择算法却不能用动态规划算法求 解。因为贪心算法无法最终将背包装满，部分闲置的背包空间使得每 公斤背包空间的价值降低了。七、附录：(源代码)(1)最少加油次数具体算法的实现如下：#i nclude<iostream.h>VOid mai n()int n,m,a100,i,s,sum=0,j;cout<<"请输入沿途的站点数和每一次加油以后可以行使的路程数
10、"v<endl;cin>>n;cin>>m;cout<<"沿途的站点数为："<<n<<endl;cout<<"每加满一次油可以行使的路程数为"<<m<<endl;cout<<"请一次输入第零站到第N站之间的距离"v<endl;for(i=0;i<=n ;i+)cin> >ai;for( i=0;i<=n ;i+)cout<<"第"<<i&l
11、t;<"站到第"<<i+1<<"站之间的距离为"<<ai<<endl;for(j=0;j Vn ;j+)if(aj>m)Sum=-1;break;if(sum!=-1)for(i=0,s=0;i Vn ;i+)s=s+ai;if(s>n)sum+;s=ai;if(sum=-1)COutVv"没有可行性"<<endl;elseCOUtVv"沿途的最少加油次数为"v<sum<<endl;(2)最少硬币问题具体算法的实现如下：
12、#i nclude<iostream.h>mai n()double n,m,a,b,c,d,f;a=b=c=d=0;COUtV<"请输入应找的钱!"<<endl; cin>>n;if(n<=0)COUtV<"您输入的数据有错!"v<endl;m=n;while(m>=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;COutV<
13、"应找的最少的硬币个数为："<<f<<endl; cout<v"其中 2 角 5 分的有"v<a<v"个"<<endl; COUtV<"其中 1 角的有"v<b<<"个"<<endl; COUtV<"其中 5 分的有"vvcvv"个"<<endl; COUtV<"其中 1 分的有"v<d<<"个"<<endl;