貪心算法設(shè)計(jì)與應(yīng)用

1、實(shí)驗(yàn)報(bào)告課程算法設(shè)計(jì)與分析實(shí)驗(yàn)實(shí)驗(yàn)名稱貪心算法設(shè)計(jì)與應(yīng)用一第頁(yè)一、實(shí)驗(yàn)?zāi)康睦斫庳澬乃惴ǖ幕驹恚莆肇澬乃惴ㄔO(shè)計(jì)的基本方法及其應(yīng)用；二、實(shí)驗(yàn)內(nèi)容（一）Huffman編碼和譯碼問(wèn)題：1 .問(wèn)題描述給定n個(gè)字符在文件中的出現(xiàn)頻率，利用Huffman樹(shù)進(jìn)行Huffman編碼和譯 碼。設(shè)計(jì)一個(gè)程序?qū)崿F(xiàn)：輸入含n（n=10）個(gè)字符的字符集S以及S中各個(gè)字符在文件中的出現(xiàn)頻 率，建立相應(yīng)的Huffman樹(shù)，求出S中各個(gè)字符的Huffman編碼。輸入一個(gè)由S中的字符組成的序列L，求L的Huffman編碼。輸入一個(gè)二進(jìn)制位串B，對(duì)B進(jìn)行Huffman譯碼，輸出對(duì)應(yīng)的字符序列; 若不能譯碼，則輸出無(wú)解信息。提

2、示：對(duì)應(yīng)10個(gè)字符的Huffman樹(shù)的節(jié)點(diǎn)個(gè)數(shù)21。測(cè)試數(shù)據(jù)Inputn=5字符集合 S=a, b, c, d, e, 對(duì)應(yīng)的頻率分別為 a: 20 b: 7 c: 10 d: 4 e: 18字符序列L=ebcca二進(jìn)制位串 B=01100111010010OutputS中各個(gè)字符的Huffman編碼：（設(shè)Huffman樹(shù)中左孩子的權(quán)=右孩子的權(quán)） a: 11 b: 010 c: 00 d: 011 e: 10L 的 Huffman 編碼：10010000011B對(duì)應(yīng)的字符序列：dcaeeb若輸入的B=01111101001，則無(wú)解（二）加油問(wèn)題（Problem Set 1702 ）：?jiǎn)栴}描述

3、一個(gè)旅行家想駕駛汽車(chē)從城市A到城市B （設(shè)出發(fā)時(shí)油箱是空的）。給定兩個(gè) 城市之間的距離dis、汽車(chē)油箱的容量c、每升汽油能行駛的距離d、沿途油 站數(shù)n、油站i離出發(fā)點(diǎn)的距離di以及該站每升汽油的價(jià)格 pi,i=1,2,n。設(shè)d1=0d2dn。要花最少的油費(fèi)從城市A到城 市B，在每個(gè)加油站應(yīng)加多少油，最少花費(fèi)為多少？具體要求Input輸入的第一行是一個(gè)正整數(shù)k，表示測(cè)試?yán)齻€(gè)數(shù)。接下來(lái)幾行是k個(gè)測(cè)試?yán)?的數(shù)據(jù)，每個(gè)測(cè)試?yán)臄?shù)據(jù)由三行組成，其中第一行含4個(gè)正整數(shù)，依次為 A和B兩個(gè)城市之間的距離d1、汽車(chē)油箱的容量c (以升為單位)、每升汽油 能行駛的距離d2、沿途油站數(shù)n (1=n=xw和yb=y

4、w。 若黑點(diǎn)b支配白點(diǎn)w，則黑點(diǎn)b和白點(diǎn)w可匹配(可形成一個(gè)匹配對(duì))。在一 個(gè)黑點(diǎn)最多只能與一個(gè)白點(diǎn)匹配，一個(gè)白點(diǎn)最多只能與一個(gè)黑點(diǎn)匹配的前提 下，求n個(gè)白點(diǎn)和n個(gè)黑點(diǎn)的最大匹配對(duì)數(shù)。具體要求輸入的第一行是一個(gè)正整數(shù)k，表示測(cè)試?yán)齻€(gè)數(shù)。接下來(lái)幾行是k個(gè)測(cè)試?yán)?的數(shù)據(jù)，每個(gè)測(cè)試?yán)臄?shù)據(jù)由三行組成，其中第一行含1個(gè)正整數(shù)n(n16)； 第二行含 2n 個(gè)實(shí)數(shù) xbybxb2，yb2, x, ybn，(xb., yb，i=1, 2, n表示n個(gè)黑點(diǎn)的坐標(biāo)；第三行含2n個(gè)實(shí)數(shù)xw , yw ,xw , yw,，xw , yw，122n(xw., yw.)， i=1, 2,，n表示n個(gè)白點(diǎn)的坐標(biāo)。同一行

5、的實(shí)數(shù)之間用一個(gè) 空格隔開(kāi)。Output對(duì)于每個(gè)測(cè)試?yán)敵鲆恍?，含一個(gè)整數(shù)，表示n個(gè)白點(diǎn)和n個(gè)黑點(diǎn)的最大匹 配對(duì)數(shù)。測(cè)試數(shù)據(jù)輸入：135.0 3.0 5.0 -1.0 4.0 4.02.0 3.5 2.0 2.0 -2.0 -2.0輸出：3擴(kuò)展內(nèi)容(1)建議采用可視化界面三、實(shí)驗(yàn)環(huán)境硬件：Windows XP計(jì)算機(jī)、鼠標(biāo)、鍵盤(pán)、顯示器開(kāi)發(fā)環(huán)境：Microsoft Visual C+ 6.0四、實(shí)驗(yàn)步驟(描述實(shí)驗(yàn)步驟及中間的結(jié)果或現(xiàn)象。在實(shí)驗(yàn)中做了什么事情，怎么做的，發(fā)生 的現(xiàn)象和中間結(jié)果)點(diǎn)擊開(kāi)始菜單中的程序-Microsoft Visual C+ 6.0點(diǎn)擊菜單欄中的文件一新建一文件一C+

6、Source File，在文件名(N)中 寫(xiě)入“實(shí)驗(yàn)五.(1).cpp”，再點(diǎn)擊確定.、編寫(xiě)程序如下：#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;/*/ 構(gòu) 造 哈 弗 曼 樹(shù)*/void Haffman(int n)/構(gòu)造哈弗曼樹(shù)(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;/*/ 構(gòu) 造 哈 弗 曼 編 碼*/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(請(qǐng)輸入字符集大小n:n);scanf(%d,&n);m=2*n-1;HaffmanTree=(structHafNode*

10、)malloc(sizeof(structHafNode)*(m+1);for(i=1;i=n;i+)(printf(請(qǐng)輸入第d個(gè)字符和權(quán)值：，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;/*輸出每個(gè)字符的哈弗曼編碼*/void output(int n)(printf(nn)；int i;for(i=1;i=n;i+)(printf(%c 的 哈 弗 曼 編 碼 是：sn”,HaffmanCodei.ch,HaffmanCodei.bit);/* 對(duì) 字 符 進(jìn) 行 編 碼*/void Char_Change(int m)/對(duì)字符進(jìn)行編碼(int n,i,j;char string50,*p;printf(請(qǐng)輸入字符串：)；scanf(%s,string);n=strlen(

12、string);/n為輸入的字符串的長(zhǎng)度printf(字符串的編碼為：);for(i=1,p=string;i=n;i+,p+)(for(j=1;j=m;j+)(if(HaffmanCodej.ch=*p)/輸入的字符串逐個(gè)與哈弗曼樹(shù)的字符比 對(duì)printf(s,HaffmanCodej.bit);printf(n)；/*對(duì)輸入的編碼進(jìn)行譯碼*/int Code_Change(int n)(int i,t;char code1000;printf(請(qǐng)輸入編碼：)；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+；/*主函數(shù)*/void main()(int n;printf(開(kāi)始程序nn);n=CreatHuffman();output(n);/輸出每個(gè)字符的編碼printf(對(duì)字符進(jìn)行編碼nn);Char_Change(n);/執(zhí)行編碼操作printf(對(duì)編碼進(jìn)行譯碼nn);Code_Change(n);/執(zhí)行譯碼操作printf(n)；點(diǎn)擊開(kāi)始菜單中的程序-Microsoft Visual C+ 6.0點(diǎn)擊菜單欄中的文件一新建一文件一C+ Source File，在文件名(N)中 寫(xiě)入“實(shí)驗(yàn)五.(2).cpp”，再點(diǎn)擊確定.編寫(xiě)程序如下：#include#define MAX 20

15、/*/void look(float dis,float pir,int n,int d2,int oil)/disi表示第 i個(gè)站點(diǎn)離起點(diǎn)的距離，piri表示每升油的價(jià)格(/n表示站點(diǎn)個(gè)數(shù)，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)/若剩余的油量夠走到符合條件的站點(diǎn)，則不需要 再加油(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(輸入測(cè)試?yán)齻€(gè)數(shù)：n);scanf(d，&k);for(i=0;ik;i+)(printf(輸入第d 個(gè)數(shù)據(jù)：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 次結(jié)果：，i+1);printf(NO solution!n)；else(printf(第d 次結(jié)果：,i+1);printf(最少油費(fèi)：)；look(Ai,Bi,ni,d2i,ci);printf(n)；printf(n)；點(diǎn)擊開(kāi)始菜單中的程序-Microsoft Visual C+ 6.0點(diǎn)擊菜單欄中的文件一新建一文件一C+ Source File，在文件名(N)中 寫(xiě)入“實(shí)驗(yàn)五.(3)黑白點(diǎn)問(wèn)題.cpp”，再點(diǎn)擊確定.編寫(xiě)程序如下：

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) /*循環(huán)到?jīng)]有比較范圍*/(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-)/關(guān)于 wpw.x 從大到小做(minflag=0;/標(biāo)記初始化minp=0;/最接近點(diǎn)的下標(biāo)初始化miny=INT_MAX;/初始化y的無(wú)窮大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(輸入測(cè)試數(shù)據(jù)個(gè)數(shù)n);scanf(d，&k);while(k0)(printf(輸入點(diǎn)的個(gè)數(shù)n)；scanf(%d,&n);printf(輸入黑點(diǎn)的坐標(biāo)n)；for(i=0;in;i+)( scanf(%f %f”,&bi.x,&bi.y); printf(輸入白點(diǎn)的坐標(biāo)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);/對(duì)白點(diǎn)的x值從小到大排序 count二match(w,b,n);printf(count=%dn，count);k-;五、實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)五.(1).cpp按照實(shí)驗(yàn)要求輸入測(cè)試?yán)?，得到的?shí)驗(yàn)結(jié)果是:道狙入字筍串：mem字符串的編碼為；10011000011對(duì)編碼進(jìn)行譯碼a 20 b 7c 10 道狙入字筍串：mem字符串的編碼為；10011000011對(duì)編碼進(jìn)行譯碼a 20 b 7c 10 d 4e 18編此 Q110011101QQ1Q 字特串為：bcaeed any key to continue。我Ez算法實(shí)feDebug實(shí)驗(yàn)五(1)哈