第一篇：用贪心算法求解Prim算法上机实验报告书
算法分析与设计
实验报告
班级：学号：姓名：上机时间：
一、实验目的与要求：
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); } 《算法设计与分析》实验报告 实验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算法有了更深的了解，也使我对算法设计与分析更有兴趣，今后一定要更努力的学习这门课。 篇一：prim算法实验报告 算法实验报告 学院：xxx 班级：xxx 学号：xxx 姓名：xxx prim 篇二：prim最小生成树算法实验报告 算法分析与设计之prim 学院：软件学院 学号：201421031059 姓名：吕吕 一、问题描述 1.prim的定义 prim算法是贪心算法的一个实例，用于找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。(强调的是树，树是没有回路的)。2.实验目的 选择一门编程语言，根据prim算法实现最小生成树，并打印最小生成树权值。 二、算法分析与设计 1.prim算法的实现过程 基本思想：假设g＝(v，e)是连通的，te是g上最小生成树中边的集合。算法从u＝{u0}（u0∈v）、te＝{}开始。重复执行下列操作： 在所有u∈u，v∈v－u的边(u，v)∈e中找一条权值最小的边(u0,v0)并入集合te中，同时v0并入u，直到v＝u为止。 此时，te中必有n-1条边，t=(v，te)为g的最小生成树。prim算法的核心:始终保持te中的边集构成一棵生成树。2.时间复杂度 prim算法适合稠密图，其时间复杂度为o(n^2)，其时间复杂度与边得数目无关，n为顶点数，而看ruskal算法的时间复杂度为o(eloge)跟边的数目有关，适合稀疏图。 三、数据结构的设计 图采用类存储，定义如下： class graph { private: int *verticeslist;int **edge;int numvertices;int numedges;int maxvertices;graph();~graph();bool insertvertex(const int vertex);bool insertedge(int v1,int v2,int cost);int getvertexpos(int vertex);int getvalue(int i);int getweight(int v1,int v2);int numberofvertices();1 public: } void prim();其中，图中结点连接情况及权值使用二重指针表示，即二维数组实现邻接矩阵。 四、代码与运行结果 代码运行结果： 源码： //普雷姆算法 #include int graph::getvalue(int i){ };int graph::getweight(int v1,int v2){ };int graph::numberofvertices(){ };int graph::numberofedges(){ };//插入结点 bool graph::insertvertex(const int vertex){ };//插入边，v1和v2为结点在数组的下标 bool graph::insertedge(int v1,int v2,int cost){ if(v1>-1&&v1 istream& operator>>(istream &in ,graph &g){ };//输出图对象 ostream& operator<<(ostream &out,graph &g){ int i,j,vertices,edges;int start,end,weight;vertices=g.numberofvertices();edges=g.numberofedges();out< in>>vertices>>edges;for(i=1;i<=vertices;i++){ } i=0;while(i 黄冈师范学院 提高型实验报告 实验课题 最小生成树的prim算法 （实验类型：□综合性 ■设计性 □应用性） 实验课程 算法程序设计 实验时间2010年12月24日 学生姓名 周 媛鑫 专业班级 计科 0801 学 号 200826140110 一．实验目的和要求 （1）根据算法设计需要, 掌握连通网的灵活表示方法;（2）掌握最小生成树的prim算法;（3）熟练掌握贪心算法的设计方法;二．实验条件 （1）硬件环境：实验室电脑一台（2）软件环境：wintc 三．实验原理分析 （1）最小生成树的定义： 假设一个单位要在n个办公地点之间建立通信网，则连通n个地点只需要n-1条线路。可以用连通的无向网来表示n个地点以及它们之间可能设置的通信线路，其中网的顶点表示城市，边表示两地间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以表示一个通信网。其中一棵使总的耗费最少，即边的权值之和最小的生成树，称为最小生成树。 （2）构造最小生成树可以用多种算法。其中多数算法利用了最小生成树的下面一种简称为mst的性质：假设n=(v,{e})是一个连通网，u是顶点集v的一个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中u∈u，v∈v-u，则必存在一棵包含边(u.v)的最小生成树。（3）普里姆（prim）算法即是利用mst性质构造最小生成树的算法。算法思想如下： 假设n=(v,{e})和是连通网，te是n上最小生成树中边的集合。算法从u={u0}(u0∈v)，te={}开始，重复执行下述操作：在所有u∈u，v∈v-u的边(u, v)∈e中找一条代价最小的边(u0, v0)并入集合te，同时v0并入u，直到u=v为止。此时te中必有n-1条边，则t=(v,{te})为n的最小生成树。四．实验步骤 （1）数据结构的设计 ： 采用邻接矩阵的存储结构来存储无向带权图更利于实现及操作： 邻接矩阵的抽象数据结构定义： #defineinfinityint_max //最大值 #define max_ertex_num20 //最大顶点数 typedef enum {dg,dn,udg,udn}graphkind;//{有向图,有向网，无向网，无向图} typedef struct arc cell{ vrtype adj;// vrtype 是顶点关系的类型。对无权图用1和0表示相邻否； infotype * info;//该弧相关信息的指针 }arccell，adjmatrix [ max_vertex_num][max_vertex_num]； typedef struct { vertextype vexs [ max_vertex_num];//顶点向量adjmatrixarcs;// 邻接矩阵 intvexnum , arcnum;//图的当前顶点数和弧数 graphkindkind;// 图的种类标志 }mgraph;（2）函数设计 函数名称 函数原型 功能描述 main()int main(void)系统调用主函数 huiru()void huitu()绘制无向图 graphicver()void graphicver(graph *g)输出邻接矩阵 prim()void prim(graph *g)prim算法演示（3）实验源代码 #include 实验报告题目 实验四 贪心算法 开课实验室：数学实验室 指导老师：韩逢庆 时间：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<<“应找的最少的硬币个数为：”< 证明人民币找零问题贪心算法的正确性 问题提出： 根据人们生活常识，我们到商店里买东西需要找零钱时，收银员总是先给我们最大面值的，要是不够再找面值小一点的，直到找完为止。这就是一个典型的贪心选择问题。问题描述： 当前有面值分别为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）均应为最大数量了，所以贪心算法得到的解是最优解，即满足贪心选择性质。 综上所述，人民币找零问题满足贪心算法。第二篇：实验3 贪心算法（定稿）
第三篇：PRIM算法实验报告
第四篇：贪心算法实验报告
第五篇：证明人民币找零问题贪心算法正确性（范文模版）
点击咨询 