贪心算法设计与应用

实验报告课程算法设计与分析实验实验名称贪心算法设计与应用第1页一、实验目的理解贪心算法的基本原理，掌握贪心算法设计的基本方法及其应用；二、实验内容(一)Huffman编码和译码问题：1．问题描述给定n个字符在文件中的出现频率，利用Huffman树进行Huffman编码和译码。设计一个程序实现：1.输入含n(n=10)个字符的字符集S以及S中各个字符在文件中的出现频率，建立相应的Huffman树，求出S中各个字符的Huffman编码。2.输入一个由S中的字符组成的序列L，求L的Huffman编码。3.输入一个二进制位串B，对B进行Huffman译码，输出对应的字符序列；若不能译码，则输出无解信息。提示：对应10个字符的Huffman树的节点个数211。2．测试数据Inputn=5字符集合S={a,b,c,d,e},对应的频率分别为a:20b:7c:10d:4e:18字符序列L=ebcca二进制位串B=01100111010010OutputS中各个字符的Huffman编码：（设Huffman树中左孩子的权=右孩子的权）a:11b:010c:00d:011e:10L的Huffman编码：10010000011B对应的字符序列：dcaeeb若输入的B=01111101001，则无解(二)加油问题（ProblemSet1702）：1.问题描述一个旅行家想驾驶汽车从城市A到城市B（设出发时油箱是空的）。给定两个城市之间的距离dis、汽车油箱的容量c、每升汽油能行驶的距离d、沿途油站数n、油站i离出发点的距离d[i]以及该站每升汽油的价格p[i],i=1,2,…,n。设d[1]=0d[2]…d[n]。要花最少的油费从城市A到城市B，在每个加油站应加多少油，最少花费为多少？2.具体要求Input输入的第一行是一个正整数k，表示测试例个数。接下来几行是k个测试例的数据，每个测试例的数据由三行组成，其中第一行含4个正整数，依次为A和B两个城市之间的距离d1、汽车油箱的容量c（以升为单位）、每升汽油能行驶的距离d2、沿途油站数n(1=n=200)；第二行含n个实数d1,d2,…,dn，表示各油站离出发点的距离（d1=0）；第三行含n个实数p1,p2,…,pn，表示各油站每升汽油的价格。同一行的数之间用一个空格隔开。Output对于每个测试例输出一行，含一个实数，表示从城市Ａ到城市Ｂ所要花费的最少油费（输出的结果精确到小数点后一位）。若问题无解，则输出“NoSolution”。3.测试数据21500501040300.0800.01200.04.05.04.04.51000401030500.0750.04.55.04.2SampleOutput640.0NoSolution4．设计与实现的提示（1）注意考虑无解的情况（2）对终点站可进行特殊处理5.扩展内容(1)演示时建议采用可视化界面(2)TheExpressMail(ProblemSet1755)(三)黑白点的匹配（ProblemSet1714）：（选作题）4.问题描述设平面上分布着n个白点和n个黑点，每个点用一对坐标（x,y）表示。一个黑点b=（xb,yb）支配一个白点w=(xw,yw)当且仅当xb=xw和yb=yw。若黑点b支配白点w，则黑点b和白点w可匹配（可形成一个匹配对）。在一个黑点最多只能与一个白点匹配，一个白点最多只能与一个黑点匹配的前提下，求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对于每个测试例输出一行，含一个整数，表示n个白点和n个黑点的最大匹配对数。6.测试数据输入：135.03.05.0-1.04.04.02.03.52.02.0-2.0-2.0输出：37.扩展内容(1)建议采用可视化界面三、实验环境硬件：WindowsXP计算机、鼠标、键盘、显示器开发环境：MicrosoftVisualC++6.0四、实验步骤（描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的，发生的现象和中间结果）①、点击开始菜单中的程序-MicrosoftVisualC++6.0点击菜单栏中的文件—新建—文件—C++SourceFile，在文件名(N)中写入“实验五.(1).cpp”,再点击确定.②、编写程序如下：#includestdio.h#includestdlib.h#includestring.h#defineMAX100structHafNode{charch;intweight;intparent,lchild,rchild;}*HaffmanTree;structCoding{charbit[MAX];charch;intweight;}*HaffmanCode;/*------------------------//构造哈弗曼树-----------------------------*/voidHaffman(intn)//构造哈弗曼树{inti,j,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(HaffmanTree[j].parent==0&&HaffmanTree[j].weights1){s2=s1;x2=x1;s1=HaffmanTree[j].weight;x1=j;}elseif(HaffmanTree[j].parent==0&&HaffmanTree[j].weights2){s2=HaffmanTree[j].weight;x2=j;}}HaffmanTree[x1].parent=i;HaffmanTree[x2].parent=i;HaffmanTree[i].weight=s1+s2;HaffmanTree[i].lchild=x1;HaffmanTree[i].rchild=x2;}}/*---------------------------//构造哈弗曼编码------------------------*/voidHaffman_Code(intn){intstart,c,f,i,j,k;char*cd;cd=(char*)malloc(n*sizeof(char));HaffmanCode=(structCoding*)malloc((n+1)*sizeof(structCoding));cd[n-1]='\0';for(i=1;i=n;++i){start=n-1;for(c=i,f=HaffmanTree[i].parent;f!=0;c=f,f=HaffmanTree[f].parent)if(HaffmanTree[f].lchild==c)cd[--start]='0';elsecd[--start]='1';for(j=start,k=0;jn;j++){HaffmanCode[i].bit[k]=cd[j];k++;}HaffmanCode[i].ch=HaffmanTree[i].ch;HaffmanCode[i].weight=HaffmanTree[i].weight;}free(cd);}intCreatHuffman(){inti,n,m;printf(请输入字符集大小n:\n);scanf(%d,&n);m=2*n-1;HaffmanTree=(structHafNode*)malloc(sizeof(structHafNode)*(m+1));for(i=1;i=n;i++){printf(请输入第%d个字符和权值:,i);scanf(%s%d,&HaffmanTree[i].ch,&HaffmanTree[i].weight);HaffmanTree[i].parent=0;HaffmanTree[i].lchild=0;HaffmanTree[i].rchild=0;}for(i=n+1;i=m;i++){HaffmanTree[i].ch='#';HaffmanTree[i].lchild=0;HaffmanTree[i].parent=0;HaffmanTree[i].rchild=0;HaffmanTree[i].weight=0;}Haffman(n);Haffman_Code(n);returnn;}/*-----------------------输出每个字符的哈弗曼编码------------------------------*/voidoutput(intn){printf(\n\n);inti;for(i=1;i=n;i++){printf(%c的哈弗曼编码是：%s\n,HaffmanCode[i].ch,HaffmanCode[i].bit);}}/*------------------------------对字符进行编码---------------------------*/voidChar_Change(intm)//对字符进行编码{intn,i,j;charstring[50],*p;printf(请输入字符串：);scanf(%s,string);n=strlen(string);//n为输入的字符串的长度printf(字符串的编码为:);for(i=1,p=string;i=n;i++,p++){for(j=1;j=m;j++){if(HaffmanCode[j].ch==*p)//输入的字符串逐个与哈弗曼树的字符比对printf(%s,HaffmanCode[j].bit);}}printf(\n);}/*---------------------------对输入的编码进行译码---------------------*/intCode_Change(intn){inti,t;charcode[1000];printf(请输入编码：);scanf(%s,code);printf(编码的字符串为：);for(i=0;code[i]!='\0';){t=2*n-1;while(code[i]!='\0'){if(code[i]-'0'==1){if(HaffmanTree[t].rchild!=0){t=HaffmanTree[t].rchild;}else{printf(Nosolution!\n);return0;}}else{if(HaffmanTree[t].lchild!=0){t=HaffmanTree[t].lchild;}else{printf(Nosolution!\n);return0;}}if(HaffmanTree[t].lchild==0&&HaffmanTree[t].rchild==0){printf(%c,HaffmanTree[t].ch);i++;if(code[i]=='\0')return0;elsebreak;}i++;}}}/*-----------------------主函数-----------------------------*/voidmain(){intn;printf(---------------开始程序------------------\n\n);n=CreatHuffman();output(n);//输出每个字符的编码printf(--------------对字符进行编码--------------\n\n);Char_Change(n);//执行编码操作printf(------------