第一篇：实验3 贪心算法（定稿）
《算法设计与分析》实验报告
实验3贪心算法
姓名 学号班级 实验日期实验地点
一、实验目的
1、掌握贪心算法的设计思想。
2、理解最小生成树的相关概念。
二、实验环境
1、硬件环境 CPU：酷睿i5 内存：4GB 硬盘：1T
2、软件环境
操作系统：Windows10 编程环境：jdk 编程语言：Java
三、实验内容：在Prim算法与Kruskal算法中任选一种求解最小生成树问题。
1、你选择的是：Prim算法
2、数据结构
（1）图的数据结构——图结构是研究数据元素之间的多对多的关系。在这种结构中，任意两个元素之间可能存在关系，即结点之间的关系可以是任意的，图中任意元素之间都可能相关。
图形结构——多个对多个，如
（2）树的数据结构——树结构是研究数据元素之间的一对多的关系。在这种结构中，每个元素对下(层)可以有0个或多个元素相联系，对上(层)只有唯一的一个元素相关，数据元素之间有明显的层次关系。树形结构——一个对多个，如
3、算法伪代码 Prim(G,E,W)输入：连通图G 输出：G的最小生成树T 1.S←{1};T=∅ 2.While V-S ≠∅ do
3.从V-S中选择j使得j到S中顶点的边e的权最小；T←T∪{e} 4.S←S∪{j}
3、算法分析 时间复杂度：O(n)空间复杂度：O(n^2)
4、关键代码（含注释）
package Prim;
import java.util.*;publicclass Main { staticintMAXCOST=Integer.MAX_VALUE;
staticint Prim(intgraph[][], intn){ /* lowcost[i]记录以i为终点的边的最小权值，当lowcost[i]=0时表示终点i加入生成树 */
intlowcost[]=newint[n+1];
/* mst[i]记录对应lowcost[i]的起点，当mst[i]=0时表示起点i加入生成树 */ intmst[]=newint[n+1];
intmin, minid, sum = 0;
/* 默认选择1号节点加入生成树，从2号节点开始初始化 */ for(inti = 2;i<= n;i++){
/* 标记1号节点加入生成树 */ mst[1] = 0;
/* n个节点至少需要n-1条边构成最小生成树 */ for(inti = 2;i<= n;i++){
/* 找满足条件的最小权值边的节点minid */ for(intj = 2;j<= n;j++){
/* 输出生成树边的信息:起点，终点，权值 */
System.out.printf(“%c1, minid + 'A''A' + 1;intj = chy-'A' + 1;graph[i][j] = cost;graph[j][i] = cost;for(intj = 1;j<= n;j++){ } graph[i][j] = MAXCOST;} } System.out.println(”Total:"+cost);} }
5、实验结果（1）输入
（2）输出
最小生成树的权值为： 生成过程：
(a)
(b)
(d)
(e)
(c)
四、实验总结（心得体会、需要注意的问题等）
这次实验，使我受益匪浅。这次实验我选择了Prim算法来求出树的最小生成树，在编写代码的过程中，我对Prim算法有了更深的了解，也使我对算法设计与分析更有兴趣，今后一定要更努力的学习这门课。
第二篇：贪心算法实验报告
实验报告题目 实验四 贪心算法
开课实验室：数学实验室
指导老师：韩逢庆
时间：2011.12 学院：理学院
专业：信息与计算科学
班级：2009级2班 姓名：古 月
学号：09180230
一、实验目的 1．加深学生对贪心算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；
2．提高学生利用课堂所学知识解决实际问题的能力；
3．提高学生综合应用所学知识解决实际问题的能力。
二、实验内容
题目见P143:4-16,4-23.三、实验要求
（1）用分治法求解最少加油次数和最少硬币个数问题；
（2）再选择自己熟悉的其它方法求解本问题；
（3）上机实现所设计的所有算法；
四、实验过程设计（算法设计过程）（1）最少加油次数 实验题目
一辆汽车加满油以后可以行使n公里，旅途中有若干个加油站，设计一个有效算法，指出应在哪些加油站停靠加油，使沿路加油次数最少。并证明算法能产生一个最优解。过程设计
贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。比如说最少加油次数的问题。在这个算法中，我采用的贪心算法的策略。首先人机互动的设定加满油以后最长能够行使的距离，然后输入了各个站点之间的距离，在程序的设计中，首先检查了程序的可行性。要是遇到当某两个站点之间的距离大于汽车一次加油以后所能够行使的最大距离时，我们认为此问题是不可行的。这个在实际情况中也是很容易理解的。然后在满足可行性条件下，依次采用贪心算法对问题得以实现。采用s这个来保存现在车里面留下的油，当此时留下的有能够行驶完这一站点到下一站点之间的距离是，在这一站点的时候就不加油。但是若不能行使完这一段路程的时候，就加满油。核心算法如下：
for(i=0,s=0;i { s=s+a[i]; if(s>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）最少加油次数 当加油后行驶的最大距离小于相邻站点的最小值时，此时，可行，求解结果如下： 当加油后行驶的最大距离大于相邻站点的最小值时，此时，没用可行性，为边沿情况，求解结果如下： （分析时空复杂性，设计测试用例及测试结果）时间复杂性：该算法的时间复杂度为O(n)空间复杂性分析：该算法的空间复杂度为O(1)（2）最少硬币问题 当输入的找零钱数为正常的时候的运行情况如下： 当输入的找零钱数为不正常的时候（为负）的运行情况如下： （分析时空复杂性，设计测试用例及测试结果）时间复杂性：该算法的时间复杂性为O(n)空间复杂性分析：该算法的空间复杂性为O(1) 六、实验体会 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题，相容活动安排问题等。这样和采用动态规划的算法相比，算法的思想更加的简单，实现起来更加的容易。 但是也要明确贪心算法和动态规划的主要区别。及0-1背包问题可以用动态规划算法求解，但是贪心选择算法却不能用动态规划算法求解。因为贪心算法无法最终将背包装满，部分闲置的背包空间使得每公斤背包空间的价值降低了。 七、附录：（源代码）（1）最少加油次数 具体算法的实现如下： #include cin>>a[i];} for(i=0;i<=n;i++){ cout<<“第”< if(a[j]>m) { sum=-1; break; } if(sum!=-1){ } for(i=0,s=0;i s=s+a[i]; if(s>n) { sum++; s=a[i]; } } } if(sum==-1)cout<<“没有可行性”< #include cout<<“ 您输入的数据有错!”< 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<<“应找的最少的硬币个数为：”< 算法分析与设计 实验报告 班级：学号：姓名：上机时间： 一、实验目的与要求： 1、熟悉贪心算法的基本原理和适用范围； 2、使用贪心算法编程，求解最小生成树问题。 二、实验题目： 用贪心算法求解Prim算法 三、实验内容： 任选一种贪心算法（prim或Kruskal），求解最小生成树。对算法进行 描述和复杂性分析。编程实现。 四、问题描述： 设G=(V,E)是连通带权图，V={1,2,…,n}。构造G的最小生成树的Prim 算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如 下的贪心选择：选取满足条件i∈s，j∈V-S，且c[i][j]最小的边，将顶 点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。 五、问题分析与算法设计 六、实验结果及分析 七、实验总结 八、程序代码 #include #include #include #include #include #define maxint 20 #define inf 700 int AllSelected(int n,int s[]) { int i; for(i = 1;i <= n;i++) { if(s[i] == 0) return 0; } return 1; } void Prim(int n,int **c) { int lowcost[maxint]; int closest[maxint]; bools[maxint];s[1]=true; for(int i=2;i<=n;i++) { lowcost[i]=c[1][i]; closest[i]=1; s[i]=false; } for(i=1;i<=n;i++) { int min=inf; int j=1; for(int k=2;k<=n;k++) { if((lowcost[k] { min=lowcost[k]; j=k; } s[j]=true; for(int k=2;k<=n;k++) if((c[j][k] { lowcost[k]=c[j][k];closest[k]=j; } } } } void main() { int n,i,j; int **k; printf(“请输入顶点个数:”); scanf(“%d”,&n); k=(int **)malloc(sizeof(int *)*(n + 1)); for(i = 1;i <= n;i++) k[i] =(int *)malloc(sizeof(int)*(n+1)); printf(“输入顶点间的权值(自己到自己为0，没有路的为大于其他任何值的数):n”);for(i=1;i<=n;i++) for(j=i;j<=n;j++) { printf(“k[%d][%d]=k[%d][%d]=”,i,j,j,i); scanf(“%d”,&k[i][j]); k[j][i]=k[i][j]; } printf(“n”); printf(“顶点t”); for(i=1;i<=n;i++) { printf(“%dt”,i); } printf(“n”); for(i=1;i<=n;i++) { printf(“%dt”,i); for(j=1;j<=n;j++) { printf(“%dt”,k[i][j]); } printf(“n”); } printf(“n”); Prim(n,k); } 一次，有黑、红、白三只老鼠帮助土地神逃过了灭顶之灾。为了表示感激之情，土地神答应给这三只老鼠一个特殊的奖赏：你能将土挖多深，那多么深的土层就属于你的领地。 土地神警告它们，不要过于贪心，如果挖得过深，你们将难以返回地面而葬身地下。 这种奖赏令三只老鼠高兴万分，于是它们都使尽了全身的力气去挖洞，至于挖多深的洞才是安全的，它们并不清楚，它们只能凭感觉。在它们看来，挖洞是自己的特长，它们可以用一半的力气挖到很深的地方，再用剩下一半的力气安全地返回地面。 黑老鼠挖洞的速度很快。没过多久，它已经挖到了很深的地方。它十分兴奋，一想到它所挖的深度就是它的领地，它的力量就源源不断地涌出来。不知过了多久，它觉得自己的力气已经用去了一半，它决定休息一会儿，然后返回地面。对它来说，这么深的土层已经足够用了。 不一会儿，它的体力恢复了许多。它想，再挖一会儿也不会有什么危险，这样返回去太可惜了。于是，它又挖了许久。当它觉得有些累了的时候，开始提醒自己：不要再向下面挖了，如果不能返回地面，一切就都完了。于是，它想沿着原来挖的路线向地面方向返回。 但此时，它又犹豫了，也许现在红老鼠和白老鼠正全力向地下挖土呢，如果自己这样返回去，可能是挖得最浅的一只老鼠，那么获得的领地也是最少的，也就最没有面子了。 想到这，它决定冒险再向下挖一阵子。又挖了许久后，黑老鼠觉得身体很疲乏，有些吃不消了。它明白，现在已经很危险了。不过，它又咬了咬牙，心想：反正已经冒险了，索性就再冒一步险，将土层挖得更深一些。 尽管它时时感觉到危险，但是，黑老鼠总是能找到各种理由激励自己向更深的土层挖下去。 不知过了多久，它失去了知觉，累死了。 红老鼠的经历与黑老鼠大致相同。它也累死了。 只有白老鼠活了下来。 土地神觉得十分伤感的同时，也感到一丝安慰。原来，这个世界上到底还是有不贪心的老鼠呀！它决定大力宣传白老鼠的事迹，告诉大家不贪心才是正确的生活态度。 事后，土地神问白老鼠的想法。 白老鼠冷冷地回答道：“难道你没有发现我的两只爪子是残废的吗？” 贪心是人的一大弱点，如果控制不了自己的贪欲，那真是一件十分危险的事情。 证明人民币找零问题贪心算法的正确性 问题提出： 根据人们生活常识，我们到商店里买东西需要找零钱时，收银员总是先给我们最大面值的，要是不够再找面值小一点的，直到找完为止。这就是一个典型的贪心选择问题。问题描述： 当前有面值分别为100 元、50 元、20 元、10 元、5元、1元, 5角, 2角、1角的人民币。证明人民币在找零时（1-99元）符合贪心算法，即证明此问题满足贪心算法的两个基本要素：即最优子结构性质和贪心选择性质。 问题证明： 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。在人民币找零问题中，其最优子结构性质表现为： 设c[i]是各面额人民币使用的数量，S[i]是商品价格为n时的最优解，数量为K。现在设某面值的人民币数量减一：S[j]=S[j]-1，则新的S[i]为n-c[j]的最优解，纸币数K-1.否则，设T[i]是n-c[j]的最优解，纸币数为m，即m 设纸币面额100,50,20,10,5,2,1元的数量依次为A,B,C,D,E,F,G，则根据贪心算法思想得到的解应依次保证max（A），max（B），max（C），max（D），max（E），max（F），max（G）。假设存在更优的算法，使得所用的纸币数更少，即数量至少小于或等于A+B+C+D+E+F+G-1。那么在纸币总数减少的情况下保证总额不变只能增大相对大面额纸币的数量并减少小面额纸币数量。而由贪心算法知max（A）已经是最大的了，以此类推，max（B），max（C），max（D），max（E），max（F）均应为最大数量了，所以贪心算法得到的解是最优解，即满足贪心选择性质。 综上所述，人民币找零问题满足贪心算法。第三篇：用贪心算法求解Prim算法上机实验报告书
第四篇：贪心实验美文摘抄
第五篇：证明人民币找零问题贪心算法正确性（范文模版）
点击咨询 