贪心算法设计与应用

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

2、能译码，则输出无解信息。提示：对应10 个字符的Huffman树的节点个数211。2测试数据Input n=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=，则无解(二) 加油问题（Problem Set 1702）：1. 问题描述一个旅行家想驾驶汽车从城市A到城市B（设出发时油箱是

3、空的）。给定两个城市之间的距离dis、汽车油箱的容量c、每升汽油能行驶的距离d、沿途油站数n、油站i离出发点的距离di以及该站每升汽油的价格pi,i=1,2,n。设d1=0d2dn。要花最少的油费从城市A到城市B，在每个加油站应加多少油，最少花费为多少？2. 具体要求Input输入的第一行是一个正整数k，表示测试例个数。接下来几行是k个测试例的数据，每个测试例的数据由三行组成，其中第一行含4个正整数，依次为A和B两个城市之间的距离d1、汽车油箱的容量c（以升为单位）、每升汽油能行驶的距离d2、沿途油站数n (1=n=xw和yb=yw。若黑点b支配白点w，则黑点b和白点w可匹配（可形成一个匹配对

4、）。在一个黑点最多只能与一个白点匹配，一个白点最多只能与一个黑点匹配的前提下，求n个白点和n个黑点的最大匹配对数。5. 具体要求输入的第一行是一个正整数k，表示测试例个数。接下来几行是k个测试例的数据，每个测试例的数据由三行组成，其中第一行含1个正整数n(n16)；第二行含2n个实数xb1, yb1,xb2, yb2, xbn, ybn， (xbi, ybi)，i=1, 2, , n表示n个黑点的坐标；第三行含2n个实数xw1, yw1,xw2, yw2, xwn, ywn，(xwi, ywi)，i=1, 2, , n表示n个白点的坐标。同一行的实数之间用一个空格隔开。Output对于每个测试

5、例输出一行，含一个整数，表示n个白点和n个黑点的最大匹配对数。6. 测试数据输入：135.0 3.0 5.0 -1.0 4.0 4.02.0 3.5 2.0 2.0 -2.0 -2.0输出：37. 扩展内容(1) 建议采用可视化界面三、实验环境硬件：Windows XP计算机、鼠标、键盘、显示器开发环境：Microsoft Visual C+ 6.0四、实验步骤（描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的，发生的现象和中间结果）、 点击开始菜单中的程序-Microsoft Visual C+ 6.0点击菜单栏中的文件新建文件C+ Source File ，在文件名(N)中写

6、入“实验五.(1).cpp”,再点击确定.、 编写程序如下： #include stdio.h#include stdlib.h#include string.h#define MAX 100struct HafNode char ch; int weight; int parent,lchild,rchild;*HaffmanTree;struct Coding char bitMAX; char ch; int weight;*HaffmanCode;/*-/构造哈弗曼树-*/void Haffman(int n)/构造哈弗曼树 int i,j,x1,x2,s1,s2; for(i=n+1

7、;i=2*n-1;i+) s1=s2=10000; x1=x2=0; for(j=1;j=i-1;j+) if(HaffmanTreej.parent=0&HaffmanTreej.weights1) s2=s1; x2=x1; s1=HaffmanTreej.weight; x1=j; else if(HaffmanTreej.parent=0&HaffmanTreej.weights2) s2=HaffmanTreej.weight; x2=j; HaffmanTreex1.parent=i; HaffmanTreex2.parent=i; HaffmanTreei.weight=s1+s

8、2; HaffmanTreei.lchild=x1; HaffmanTreei.rchild=x2; /*-/构造哈弗曼编码-*/void Haffman_Code(int n) int start,c,f,i,j,k; char *cd; cd=(char *)malloc(n*sizeof(char); HaffmanCode=(struct Coding *)malloc(n+1)*sizeof(struct Coding); cdn-1=0; for(i=1;i=n;+i) start=n-1; for(c=i,f=HaffmanTreei.parent;f!=0;c=f,f=Haff

9、manTreef.parent) if(HaffmanTreef.lchild=c)cd-start=0; else cd-start=1; for(j=start,k=0;jn;j+) HaffmanCodei.bitk=cdj; k+; HaffmanCodei.ch=HaffmanTreei.ch; HaffmanCodei.weight=HaffmanTreei.weight; free(cd);int CreatHuffman() int i,n,m; printf(请输入字符集大小n:n); scanf(%d,&n); m=2*n-1; HaffmanTree=(struct Ha

10、fNode *)malloc(sizeof(struct HafNode)*(m+1); for(i=1;i=n;i+) printf(请输入第%d个字符和权值: ,i); scanf(%s%d,&HaffmanTreei.ch,&HaffmanTreei.weight); HaffmanTreei.parent=0; HaffmanTreei.lchild=0; HaffmanTreei.rchild=0; for(i=n+1;i=m;i+) HaffmanTreei.ch =#; HaffmanTreei.lchild=0; HaffmanTreei.parent=0; HaffmanTr

11、eei.rchild=0; HaffmanTreei.weight=0; Haffman(n); Haffman_Code(n);return n;/*-输出每个字符的哈弗曼编码-*/void output(int n)printf(nn);int i; for(i=1;i=n;i+) printf(%c的哈弗曼编码是：%sn,HaffmanCodei.ch,HaffmanCodei.bit);/*-对字符进行编码-*/void Char_Change(int m)/对字符进行编码 int n,i,j; char string50,*p; printf(请输入字符串：); scanf(%s,s

12、tring); n=strlen(string);/n为输入的字符串的长度 printf(字符串的编码为: ); for(i=1,p=string;i=n;i+,p+) for(j=1;j=m;j+) if(HaffmanCodej.ch=*p)/输入的字符串逐个与哈弗曼树的字符比对 printf(%s,HaffmanCodej.bit); printf(n);/*-对输入的编码进行译码-*/int Code_Change(int n) int i,t; char code1000; printf(请输入编码： ); scanf(%s,code); printf(编码的字符串为： ); for

13、(i=0;codei!=0;) t=2*n-1; while(codei!=0) if(codei-0=1) if(HaffmanTreet.rchild!=0) t=HaffmanTreet.rchild; else printf(No solution!n); return 0; else if(HaffmanTreet.lchild!=0) t=HaffmanTreet.lchild; else printf(No solution!n); return 0; if(HaffmanTreet.lchild=0&HaffmanTreet.rchild=0) printf(%c,Haffma

14、nTreet.ch); i+; if(codei=0) return 0; else break; i+; /*-主函数-*/void main() int n; printf(-开始程序-nn); n=CreatHuffman(); output(n);/输出每个字符的编码 printf(-对字符进行编码-nn); Char_Change(n);/执行编码操作 printf(-对编码进行译码-nn); Code_Change(n);/执行译码操作 printf(n);、 点击开始菜单中的程序-Microsoft Visual C+ 6.0点击菜单栏中的文件新建文件C+ Source File

15、 ，在文件名(N)中写入“实验五.(2).cpp”,再点击确定.、 编写程序如下： #include#define MAX 20/*-*/void look(float dis,float pir,int n,int d2,int oil)/disi表示第i个站点离起点的距离，piri表示每升油的价格/n表示站点个数，d2表示每升油可走的距离，oil表示邮箱容量int i,j,k;float pirce=0.0,c1=0,x,c2;for(j=0;j=n;j+)for(i=j+1;i=n;i+)if(piri=oil)x=oil-c1;/加满油elsex=c2-c1;/需要的油量减去剩余的油量

16、 if(x0)/若剩余的油量够走到符合条件的站点，则不需要再加油 x=0;pirce=pirce+pirj*x;break;c1=c1+x-(disj+1-disj)/d2);/剩余油量printf(%.1f,pirce);/*-*/void main()int k,i,j,nMAX,cMAX,d1MAX,d2MAX,lengthMAX,flagMAX;float AMAXMAX,BMAXMAX;printf(输入测试例个数: n);scanf(%d,&k);for(i=0;ik;i+)printf(输入第%d个数据：n,i+1);flagi=0;scanf(%d %d %d %d,&d1i,

17、&ci,&d2i,&ni); lengthi=ci*d2i;for(j=0;jni;j+)scanf(%f,&Aij);Aini=d1i*1.0;for(j=0;j0;j-) if(Aij-Aij-1lengthi) flagi=1;if(flagi=1)printf(第%d次结果： ,i+1);printf(NO solution!n);elseprintf(第%d次结果： ,i+1);printf(最少油费： ); look(Ai,Bi,ni,d2i,ci);printf(n);printf(n);、 点击开始菜单中的程序-Microsoft Visual C+ 6.0点击菜单栏中的文件新

18、建文件C+ Source File ，在文件名(N)中写入“实验五.(3)黑白点问题.cpp”,再点击确定.、 编写程序如下：#include#define INT_MAX struct point float x; float y; int tag;w10,b10;void bubble_sort(point w, int n)int j, k, h; point t; for (h=n-1; h0; h=k) /*循环到没有比较范围*/for (j=0, k=0; j wj+1.x) /*大的放在后面，小的放到前面*/t = wj;wj = wj+1;wj+1= t; /*完成交换*/k = j; /*保存最后下沉的位置。这样k后面的都是排序排好了的。*/int match(point w,point b,int n)int i,j,minflag,minp,count; count=0; float miny; for(i=n-1;i=0;i-)/关于wpw.x从大到小做minflag=0;/标记初始化minp=0;/最接近点的下标初始化miny=INT_MAX;/初始化y的无穷大 for(j=n-1;j=0;j-)if(bj.tag)continue;if(bj.x=wi.y)minflag=1;if(minybj.y)min