實驗03 貪心算法

實驗03貪心算法[實驗?zāi)康腯掌握貪心算法的基本思想掌握貪心算法中貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)的分析與證明掌握貪心算法求解問題的方法[實驗內(nèi)容]哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。給出文件中各個字符出現(xiàn)的頻率，求各個字符的哈夫曼編碼方案。給定帶權(quán)有向圖G=(V,E)，其中每條邊的權(quán)是非負(fù)實數(shù)。另外，還給定V中的一個頂點，稱為源?，F(xiàn)在要計算從源到所有其他各頂點的最短路長度。這里路的長度是指路上各邊權(quán)之和。設(shè)G=(V,E)是無向連通帶權(quán)圖，即一個網(wǎng)絡(luò)。E中每條邊(v,w)的權(quán)為c[v][w]。如果G的子圖G’是一棵包含G的所有頂點的樹，則稱G’為G的生成樹。生成樹上各邊權(quán)的總和稱為該生成樹的耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹。求G的最小生成樹。[實驗步驟]設(shè)計并實現(xiàn)算法并準(zhǔn)備測試用例,修改并調(diào)試程序,直至正確為止;應(yīng)用設(shè)計的算法和程序求解問題;將程序整理成功能模塊存盤備用.[實驗報告要求]闡述實驗?zāi)康暮蛯嶒瀮?nèi)容;闡述求解問題的算法原理;提交實驗程序的功能模塊;記錄最終測試數(shù)據(jù)和測試結(jié)果。[實驗結(jié)果]1.importjava.util.Scanner;publicclassHuffman{HuffmanCode[]codes;String[]huffstring;StringBufferbuffer=newStringBuffer();publicHuffman(Strings){for(inti=0;i<s.length();i++){if(buffer.indexOf(s.substring(i,i+1))==-1){buffer.append(s.charAt(i));}}System.out.println("字母："+buffer);huffstring=newString[buffer.length()];codes=newHuffmanCode[2*buffer.length()-1];for(inti=0;i<2*buffer.length()-1;i++)codes[i]=newHuffmanCode();for(inti=0;i<buffer.length();i++){codes[i].name=buffer.substring(i,i+1);codes[i].weight=haveNum(buffer.charAt(i),s);}getHuffstring();getCode(2*buffer.length()-2,huffstring,"");for(inti=0;i<huffstring.length;i++){System.out.println(codes[i].name+"code:"+huffstring[i]);}System.out.println("編碼："+getHuffmanCode(s));System.out.println("平均碼長為："+getLength());}publicdoublegetLength(){doublen=0;for(inti=0;i<buffer.length();i++){n+=huffstring[i].length();}returnn/buffer.length();}publicStringgetHuffmanCode(Strings){StringBufferbuf=newStringBuffer();for(inti=0;i<s.length();i++){buf.append(getEachCode(s.substring(i,i+1)));}returnbuf.toString();}publicStringgetEachCode(Stringname){for(inti=0;i<buffer.length();i++){if(name.equals(codes[i].name)){returnhuffstring[i];}}return"";}publicvoidgetCode(intn,String[]thecodes,Stringthebuffer){if(n<thecodes.length){thecodes[n]=thebuffer;return;}getCode(codes[n].lc,thecodes,thebuffer+"0");getCode(codes[n].rc,thecodes,thebuffer+"1");}publicvoidgetHuffstring(){int[]twos={0,0};for(inti=buffer.length();i<2*buffer.length()-1;i++){twos=findLastTwo(0,i);codes[i].lc=twos[0];codes[i].rc=twos[1];codes[i].weight=codes[twos[0]].weight+codes[twos[1]].weight;}}publicint[]findLastTwo(intstart,intend){double[]weights={1.0,1.0};int[]t={-1,-1};for(inti=start;i<end;i++){if(codes[i].pa!=-1)continue;if(weights[0]>codes[i].weight){weights[0]=codes[i].weight;t[1]=t[0];t[0]=i;}elseif(weights[1]>codes[i].weight){weights[1]=codes[i].weight;t[1]=i;}}codes[t[0]].pa=end;codes[t[1]].pa=end;returnt;}publicdoublehaveNum(charc,Strings){doublen=0;for(inti=0;i<s.length();i++){if(c==s.charAt(i))n++;}returnn/s.length();}publicstaticvoidmain(String[]args){System.out.print("輸入編碼字符串：");Scannersr=newScanner(System.in);newHuffman(sr.nextLine());}}publicclassEdgeimplementsComparable{publicinti,j,w;publicEdge(inti,intj,intw){this.i=i;this.j=j;this.w=w;}publicintcompareTo(Objecto){Edgeto=(Edge)o;if(this.w>to.w)return1;elseif(this.w==to.w)return0;elsereturn-1;}publicStringtoString(){return"start="+i+"||end="+j+"||w="+w;}}importjava.util.Scanner;publicclassHuffman{HuffmanCode[]codes;String[]huffstring;StringBufferbuffer=newStringBuffer();publicHuffman(Strings){for(inti=0;i<s.length();i++){if(buffer.indexOf(s.substring(i,i+1))==-1){buffer.append(s.charAt(i));}}System.out.println("字母："+buffer);huffstring=newString[buffer.length()];codes=newHuffmanCode[2*buffer.length()-1];for(inti=0;i<2*buffer.length()-1;i++)codes[i]=newHuffmanCode();for(inti=0;i<buffer.length();i++){codes[i].name=buffer.substring(i,i+1);codes[i].weight=haveNum(buffer.charAt(i),s);}getHuffstring();getCode(2*buffer.length()-2,huffstring,"");for(inti=0;i<huffstring.length;i++){System.out.println(codes[i].name+"code:"+huffstring[i]);}System.out.println("編碼："+getHuffmanCode(s));System.out.println("平均碼長為："+getLength());}publicdoublegetLength(){doublen=0;for(inti=0;i<buffer.length();i++){n+=huffstring[i].length();}returnn/buffer.length();}publicStringgetHuffmanCode(Strings){StringBufferbuf=newStringBuffer();for(inti=0;i<s.length();i++){buf.append(getEachCode(s.substring(i,i+1)));}returnbuf.toString();}publicStringgetEachCode(Stringname){for(inti=0;i<buffer.length();i++){if(name.equals(codes[i].name)){returnhuffstring[i];}}return"";}publicvoidgetCode(intn,String[]thecodes,Stringthebuffer){if(n<thecodes.length){thecodes[n]=thebuffer;return;}getCode(codes[n].lc,thecodes,thebuffer+"0");getCode(codes[n].rc,thecodes,thebuffer+"1");}publicvoidgetHuffstring(){int[]twos={0,0};for(inti=buffer.length();i<2*buffer.length()-1;i++){twos=findLastTwo(0,i);codes[i].lc=twos[0];codes[i].rc=twos[1];codes[i].weight=codes[twos[0]].weight+codes[twos[1]].weight;}}publicint[]findLastTwo(intstart,intend){double[]weights={1.0,1.0};int[]t={-1,-1};for(inti=start;i<end;i++){if(codes[i].pa!=-1)continue;if(weights[0]>codes[i].weight){weights[0]=codes[i].weight;t[1]=t[0];t[0]=i;}elseif(weights[1]>codes[i].weight){weights[1]=codes[i].weight;t[1]=i;}}codes[t[0]].pa=end;codes[t[1]].pa=end;returnt;}publicdoublehaveNum(charc,Strings){doublen=0;for(inti=0;i<s.length();i++){if(c==s.charAt(i))n++;}returnn/s.length();}publicstaticvoidmain(String[]args){System.out.print("輸入編碼字符串：");Scannersr=newScanner(System.in);newHuffman(sr.nextLine());}}publicclassEdgeimplementsComparable{publicinti,j,w;publicEdge(inti,intj,intw){this.i=i;this.j=j;this.w=w;}publicintcompareTo(Objecto){Edgeto=(Edge)o;if(this.w>to.w)return1;elseif(this.w==to.w)return0;elsereturn-1;}publicStringtoString(){return"start="+i+"||end="+j+"||w="+w;}}2.importjava.util.ArrayList;importjava.util.Arrays;importjava.util.HashSet;importjava.util.Set;publicclassMiniSpanTree{publicstaticvoidPRIM(int[][]graph,intstart,intn){int[][]mins=newint[n][2];for(inti=0;i<n;i++){if(i==start){mins[i][0]=-1;mins[i][1]=0;}elseif(graph[start][i]!=-1){mins[i][0]=start;mins[i][1]=graph[start][i];}else{mins[i][0]=-1;mins[i][1]=Integer.MAX_VALUE;}System.out.println("mins["+i+"][0]="+mins[i][0]+"||mins["+i+"][1]="+mins[i][1]);}for(inti=0;i<n-1;i++){intminV=-1,minW=Integer.MAX_VALUE;for(intj=0;j<n;j++){if(mins[j][1]!=0&&minW>mins[j][1]){minW=mins[j][1];minV=j;}}mins[minV][1]=0;System.out.println("最小生成樹的第"+i+"條最小邊=<"+(mins[minV][0]+1)+","+(minV+1)+">，權(quán)重="+minW);for(intj=0;j<n;j++){if(mins[j][1]!=0){System.out.println("MINV="+minV+"||tree[minV][j]="+tree[minV][j]);if(graph[minV][j]!=-1&&graph[minV][j]<mins[j][1]){mins[j][0]=minV;mins[j][1]=graph[minV][j];}}}}}publicstaticvoidKRUSKAL(int[]V,Edge[]E){Arrays.sort(E);ArrayList<HashSet>sets=newArrayList<HashSet>();for(inti=0;i<V.length;i++){HashSetset=newHashSet();set.add(V[i]);sets.add(set);}System.out.println("++++++++++++++++++++++size="+sets.size());for(inti=0;i<E.length;i++){intstart=E[i].i,end=E[i].j;intcounti=-1,countj=-2;for(intj=0;j<sets.size();j++){HashSetset=sets.get(j);if(set.contains(start)){counti=j;}if(set.contains(end)){countj=j;}}if(counti<0||countj<0)System.err.println("沒有在子樹中找到節(jié)點，錯誤");if(counti!=countj){System.out.println("輸出start="+start+"||end="+end+"||w="+E[i].w);HashSetsetj=sets.get(countj);sets.remove(countj);HashSetseti=sets.get(counti);sets.remove(counti);seti.addAll(setj);sets.add(seti);}else{System.out.println("他們在一棵子樹中，不能輸出start="+start+"||end="+end+"||w="+E[i].w);}}}publicstaticvoidmain(String[]args){int[][]tree={{-1,6,1,5,-1,-1},{6,-1,5,-1,3,-1},{1,5,-1,5,6,4},{5,-1,5,-1,-1,2},{-1,3,6,-1,-1,6},{-1,-1,4,2,6,-1}};MiniSpanTree.PRIM(tree,0,6);System.out.println("++++++++++++++++++++++++++++");int[]V={1,2,3,4,5,6};Edge[]E=newEdge[10];E[0]=newEdge(1,2,6);E[1]=newEdge(1,3,1);E[2]=newEdge(1,4,5);E[3]=newEdge(2,3,5);E[4]=newEdge(2,5,3);E[5]=newEdge(3,4,5);E[6]=newEdge(3,5,6);E[7]=newEdge(3,6,4);E[8]=newEdge(4,6,2);E[9]=newEdge(5,6,6);MiniSpanTree.KRUSKAL(V,E);}}3.publicclassDijkstra{staticintM=10000;publicstaticvoidmain(String[]args){int[][]weight1={ {0,3,2000,7,M},{3,0,4,2,M},{M,4,0,5,4},{7,2,5,0,6},{M,M,4,6,0}};int[][]weight2={{0,10,M,30,100},{M,0,50,M,M},{M,M,0,M,10},{M,M,20,0,60},{M,M,M,M,0}};intstart=0;int[]shortPath=Dijsktra(weight2,start);for(inti=0;i<shortPath.length;i++)System.out.println("從"+start+"出發(fā)到"+i+"的最短距離為："+shortPath[i]);}pu