贪心算法 实验报告

中 南 大 学

《算法设计与分析》实验报告

姓 名：

专 业 班 级：

学 号：

指导教师：

完成日期： 20010.1

一．实验名称

贪心算法实验

二． 实验目的

1. 了解贪心算法思想

2. 掌握贪心法典型问题，如背包问题、作业调度问题等。

三．实验内容

1. 编写一个简单的程序，实现单源最短路径问题

2. 编写一段程序，实现找零

3. 编写程序实现多机调度问题

四．算法思想分析

1.单源最短路径问题

（1）问题描述

已知图G＝（V，E），我们希望找出从某给定的源结点S∈V到V中的每个结点的最短路径。首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。

（2）算法分析

Dijkstra算法：

算法的基本思想是从vs出发，逐步地向外探寻最短路。执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它或者表示从vs 到该点的最短路的权(称为P标号)、或者是从vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T标号，并且把某一个具T标号的改变为具 P标号的点，从而使G中具P标号的顶点数多一个，这样至多经过n-1(n为图G的顶点数)步，就可以求出从vs到各点的最短路。

2.找零问题

（1）问题描述

当前有面值分别为2角5分，1角，5分，1分的硬币，请给出找n分钱的最佳方案（要求找出的硬币数目最少） （2）问题分析计算法实现

根据常识，我们到店里买东西找钱时，老板总是先给我们最大面值的，要是不够再找面值小一点的，直到找满为止。如果老板都给你找分数的或者几角的，那你肯定不干，另外，他也可能没有那么多零碎的钱给你找。其实这就是一个典型的贪心选择问题。

假如要找77分钱，有上面的面值分别为25，10，5，1的硬币数，为了找最少的硬币数，那么他是不是该这样找呢，先看该找多少个25分的， 57／25＝2，好像是2个，要是3个的话，我们还得再给老板一个1分的，这样不行，那么只能给2个25分的，由于还少给27，所以还得给我2个10分的，1个5分的和2个1分。

《算法设计与分析》课程实验报告

专 业： 软件工程

班 级：

学 号：

姓 名：

日期： 2013 年 11 月 11 日 一、 实验题目

贪心算法

二、 实验目的

（1） 掌握贪心算法的基本思想

（2） 掌握贪心算法中贪心选择性质和最优子结构性质的分析与证明

（3） 掌握贪心算法求解问题的方法

三、 实验内容

1. 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。给出文件中各个字符出现的频率，求各个字符的哈夫曼编码方案。

2. 给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。

3. 设G =(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。求G的最小生成树。

四、 实验步骤

1、题目一

(1) 问题分析

哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以|C|个叶结点开始，执行|C|-1次的“合并”运算后产生最终所要求的树T。下面所给出的算法huffmanTree中，编码字符集中的每一字符c的频率是f（c）。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的两棵具有最小频率的树。一旦两棵具有最小频率的树合并后，产生一棵新的树，其频率为合并两棵树的频率之和，并将新树插入优先队列Q。

算法huffmanTree首先用字符集C中每一字符c的频率f（c）初始化优先队列Q。然后不断地从优先队列Q中取出具有最小频率的两棵树x和y，将它们合并为一棵新树z。z的频率是x和y的频率之和。新树z以x为其左儿子，y为其右儿子。经过n-1次的合并后，优先队列中只剩下一棵树，即所要求的树T。

实验3贪心算法（定稿）

第一篇：实验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];

1 贪心算法实验报告 算法

实验贪心法实验报告

西 安 邮 电 大 学 （计算机学院） 课内实验报告 实验名称： 贪心算法 专业名称：班 级： 学生姓名： 学号（8指导教师： 实验日期： 一. 实验目的及实验环境 1.练习掌握最有分解问题的规划设计与实现；

2 2.熟练掌握递归算法的设计及应用，怎样才能使算法的空间复杂度和时间复杂度最低； 基于Linux系统下的ubuntu或其他的编辑器 二. 实验内容 1. 设n是一个正整数，现在要求将n分解为若干互不相同的自然数的和，且使这些自然数的乘积最大 三．方案设计 1.先将这个数分解成以2开始的连续的若干因子，它们的和加起来是n，将此数在后项优先的方式下均匀地分给前面各项。保证正整数所分解出的因子之差的绝对值最小，即 | a – b |最小，可以保证分解乘积越大。 四．测试数据及运行结果 1．正常测试数据（3组）及运行结果； A. 2.非正常测试数据（2组）及运行结果 A.

3 B. 五．总结 1．实验过程中遇到的问题及解决办法； 在实验过程中错误不断地出现，我认真地查阅书籍，研究课本上例题，并且 在同学的帮助下纠正了自己的错误，得出了正确的结果。 2．对设计及调试过程的心得体会。 在程序的运行与调试过程中出现了很多错误，但是通过自己复习课本知识、查询资料等，修改后得出了正确的结果。而且我觉得自己一定要敢于尝试，即使没有结果但是勇于实践就会有意想不到的收获。所以在以后的学习中我觉得我们一定要集中精力、端正自己态度，提高自己的成绩。当然我也认识到了自己的薄弱之处，因此我一定争取做的能让自己满意，做的更好。 六．附录：源代码（电子版） #include #include void open_file(int n) {

4 FILE *fp; if((fp=fopen(“input.txt”,”wt”))==NULL) { printf(“the file write failed.\n”); exit(1); } fprintf(fp,”%2d\n”,n); fclose(fp); } void save_file(int sum) { FILE *fp; if((fp=fopen(“output.txt”,”wt”))==NULL) { printf(“ the file save failed!.\n”); exit(1); } fprintf(fp,”%2d\n”,sum); fclose(fp); if((fp=fopen(“output.txt”,”r”))==NULL) { printf(“save file failed!\n”);