贪心算法设计与应用.doc

《贪心算法设计与应用.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告课程算法设计与分析实验实验名称贪心算法设计与应用第1页一、实验目的理解贪心算法的基本原理，掌握贪心算法设计的基本方法及其应用；二、实验内容(一)Huffman编码和译码问题：1．问题描述给定n个字符在文件中的出现频率，利用Huffman树进行Huffman编码和译码。设计一个程序实现：1.输入含n(n<=10)个字符的字符集S以及S中各个字符在文件中的出现频率，建立相应的Huffman树，求出S中各个字符的Huffman编码。2.输入一个由S中的字符组成的序列L，求L的Huffman编码。3.输入一个二进

2、制位串B，对B进行Huffman译码，输出对应的字符序列；若不能译码，则输出无解信息。提示：对应10个字符的Huffman树的节点个数<211。2．测试数据Inputn=5字符集合S={a,b,c,d,e},对应的频率分别为a:20b:7c:10d:4e:18字符序列L=ebcca二进制位串B=010OutputS中各个字符的Huffman编码：（设Huffman树中左孩子的权<=右孩子的权）a:11b:010c:00d:011e:10L的Huffman编码：B对应的字符序列：dcaeeb若输入的B=，则无解(二

3、)加油问题（ProblemSet1702）：1.问题描述一个旅行家想驾驶汽车从城市A到城市B（设出发时油箱是空的）。给定两个城市之间的距离dis、汽车油箱的容量c、每升汽油能行驶的距离d、沿途油站数n、油站i离出发点的距离d[i]以及该站每升汽油的价格p[i],i=1,2,…,n。设d[1]=0

4、其中第一行含4个正整数，依次为A和B两个城市之间的距离d1、汽车油箱的容量c（以升为单位）、每升汽油能行驶的距离d2、沿途油站数n(1<=n<=200)；第二行含n个实数d1,d2,…,dn，表示各油站离出发点的距离（d1=0）；第三行含n个实数p1,p2,…,pn，表示各油站每升汽油的价格。同一行的数之间用一个空格隔开。Output对于每个测试例输出一行，含一个实数，表示从城市Ａ到城市Ｂ所要花费的最少油费（输出的结果精确到小数点后一位）。若问题无解，则输出“NoSolution”。2.测试数据215005010

5、40300.0800.01200.04.05.04.04.51000401030500.0750.04.55.04.2SampleOutput640.0NoSolution4．设计与实现的提示（1）注意考虑无解的情况（2）对终点站可进行特殊处理5.扩展内容(1)演示时建议采用可视化界面(2)TheExpressMail(ProblemSet1755)(三)黑白点的匹配（ProblemSet1714）：（选作题）3.问题描述设平面上分布着n个白点和n个黑点，每个点用一对坐标（x,y）表示。一个黑点b=（xb,yb）

6、支配一个白点w=(xw,yw)当且仅当xb>=xw和yb>=yw。若黑点b支配白点w，则黑点b和白点w可匹配（可形成一个匹配对）。在一个黑点最多只能与一个白点匹配，一个白点最多只能与一个黑点匹配的前提下，求n个白点和n个黑点的最大匹配对数。1.具体要求输入的第一行是一个正整数k，表示测试例个数。接下来几行是k个测试例的数据，每个测试例的数据由三行组成，其中第一行含1个正整数n(n<16)；第二行含2n个实数xb1,yb1,xb2,yb2,…,xbn,ybn，(xbi,ybi)，i=1,2,…,n表示n个黑点的坐标

7、；第三行含2n个实数xw1,yw1,xw2,yw2,…,xwn,ywn，(xwi,ywi)，i=1,2,…,n表示n个白点的坐标。同一行的实数之间用一个空格隔开。Output对于每个测试例输出一行，含一个整数，表示n个白点和n个黑点的最大匹配对数。2.测试数据输入：135.03.05.0-1.04.04.02.03.52.02.0-2.0-2.0输出：33.扩展内容(1)建议采用可视化界面三、实验环境硬件：WindowsXP计算机、鼠标、键盘、显示器开发环境：MicrosoftVisualC++6.0四、实验步骤

8、（描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的，发生的现象和中间结果）①、点击开始菜单中的程序-MicrosoftVisualC++6.0点击菜单栏中的文件—新建—文件—C++SourceFile，在文件名(N)中写入“实验五.(1).cpp”,再点击确定.②、编写程序如下：#include"stdio.h"#include"stdlib.h"#incl