贪心算法设计与应用

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

2、示：对应10个字符的Huffman树的节点个数21。测试数据Inputn=5字符集合 S=a, b, c, d, e, 对应的频率分别为 a: 20 b: 7 c: 10 d: 4 e: 18字符序列L=ebcca二进制位串 B=01100111010010OutputS中各个字符的Huffman编码：（设Huffman树中左孩子的权=右孩子的权） a: 11 b: 010 c: 00 d: 011 e: 10L 的 Huffman 编码：10010000011B对应的字符序列：dcaeeb若输入的B=01111101001，则无解（二）加油问题（Problem Set 1702 ）：问题描述

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

4、w。 若黑点b支配白点w，则黑点b和白点w可匹配(可形成一个匹配对)。在一 个黑点最多只能与一个白点匹配，一个白点最多只能与一个黑点匹配的前提 下，求n个白点和n个黑点的最大匹配对数。具体要求输入的第一行是一个正整数k，表示测试例个数。接下来几行是k个测试例 的数据，每个测试例的数据由三行组成，其中第一行含1个正整数n(n16)； 第二行含 2n 个实数 xbybxb2，yb2, x, ybn，(xb., yb，i=1, 2, n表示n个黑点的坐标；第三行含2n个实数xw , yw ,xw , yw,，xw , yw，122n(xw., yw.)， i=1, 2,，n表示n个白点的坐标。同一行

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

6、Source File，在文件名(N)中 写入“实验五.(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

7、,x1,x2,s1,s2;for(i=n+1;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

8、.weight=s1+s2;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

9、,f=HaffmanTreef.parent)if(HaffmanTreef.lchild=c)cd-start=0;elsecd-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=(structHafNode*

10、)malloc(sizeof(structHafNode)*(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;HaffmanTreei.rchild=0;Haffman

11、Treei.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,string);n=strlen(

12、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(i=0;codei!=0;)(t=2*n-1;while(c

13、odei!=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,HaffmanTreet.ch);i+;if(codei=0)return 0;elseb

14、reak;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，在文件名(N)中 写入“实验五.(2).cpp”，再点击确定.编写程序如下：#include#define MAX 20

15、/*/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;/加满油else(x=c2-c1;/需要的油量减去剩余的油量if(x0)/若剩余的油量够走到符合条件的站点，则不需要 再加油(x=0;pirce二pirce+pirj*x;brea

16、k;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,&ci,&d2i,&ni);lengthi=ci*d2i;for(j=0;jni;j+)(scanf(%f,&Aij);

17、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)；else(printf(第d 次结果：,i+1);printf(最少油费：)；look(Ai,Bi,ni,d2i,ci);printf(n)；printf(n)；点击开始菜单中的程序-Microsoft Visual C+ 6.0点击菜单栏中的文件一新建一文件一C+ Source File，在文件名(N)中 写入“实验五.(3)黑白点问题.cpp”，再点击确定.编写程序如下：

18、#include#define INT_MAX 1000000struct 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,poin

19、t 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)(miny=bj.y;minp=j;if(minflag)(count+;bminp.tag=1;return count;void main()(int k,n

20、,i,count;printf(输入测试数据个数n);scanf(d，&k);while(k0)(printf(输入点的个数n)；scanf(%d,&n);printf(输入黑点的坐标n)；for(i=0;in;i+)( scanf(%f %f”,&bi.x,&bi.y); printf(输入白点的坐标n)；for(i=0;in;i+)(scanf(%f %f,&wi.x,&wi.y); for(i=0;in;i+)( wi.tag=bi.tag=0; bubble_sort(w,n);/对白点的x值从小到大排序 count二match(w,b,n);printf(count=%dn，count);k-;五、实验结果实验五.(1).cpp按照实验要求输入测试例，得到的实验结果是:道狙入字笋串：mem字符串的编码为；10011000011对编码进行译码a 20 b 7c 10 道狙入字笋串：mem字符串的编码为；10011000011对编码进行译码a 20 b 7c 10 d 4e 18编此 Q110011101QQ1Q 字特串为：bcaeed any key to continue。我Ez算法实feDebug实验五(1)哈