廣東工業(yè)大學(xué)算法設(shè)計實驗報告

算法設(shè)計分析實驗報告專業(yè)班級 軟件工程4班學(xué)號3111006218姓名 陳雪桂授課教師（2014年06月）目錄TOC\o"1-5"\h\z\o"CurrentDocument"一、 實驗?zāi)康?3\o"CurrentDocument"二、 實驗環(huán)境 3\o"CurrentDocument"三、 實驗內(nèi)容 3實驗內(nèi)容 3\o"CurrentDocument"實驗一 3\o"CurrentDocument"實驗二 3\o"CurrentDocument"算法設(shè)計思想 4實驗一 .4\o"CurrentDocument"實驗二 4\o"CurrentDocument"程序設(shè)計 4實驗一 4\o"CurrentDocument"實驗二 10\o"CurrentDocument"數(shù)據(jù)輸入和結(jié)果輸出 12實驗一 12\o"CurrentDocument"實驗二 13\o"CurrentDocument"算法復(fù)雜性分析 13實驗二 13\o"CurrentDocument"四、 實驗心得與小結(jié) 13\o"CurrentDocument"五、 指導(dǎo)教師成績評定 13、實驗?zāi)康恼莆账惴◤?fù)雜性概念。理解影響算法時間復(fù)雜性的因素。理解漸進時間復(fù)雜性的概念。掌握分析算法復(fù)雜度的方法。二、實驗環(huán)境MyEclipse三、實驗內(nèi)容（1）實驗內(nèi)容實驗一理解分治法的效率，用分治法完成快包算法，并給出一個運行實例。實驗二通過鍵盤輸入一個高精度的正整數(shù)n（n的有效位數(shù)＜240），去掉其中任意s個數(shù)字后，剩下的數(shù)字按原左右次序?qū)⒔M成一個新的正整數(shù)。編程對給定的n和s，尋找一種方案，使得剩下的數(shù)字組成的新數(shù)最小。【樣例輸入】178543S=4【樣例輸出】13實現(xiàn)該算法，分析算法的效率。并給出一個運行實例：n=“你的學(xué)號”，s=7。算法設(shè)計思想實驗一采用分治法的思想，最最左和最右兩個節(jié)點A、B，分別找到離兩個節(jié)點所在直線兩邊找距離最遠(yuǎn)的兩個點C、D，再遞歸下去直到算法結(jié)束實驗二正整數(shù)序列遍歷，找到第一個a[j]>a[j+1],刪去a[j],重復(fù)s次，也就是刪去s個數(shù)程序設(shè)計實驗/***快包問題**@author陳雪桂**/publicclassQuickPackage{staticList<Dian>pack=newArrayList<Dian>();publicstaticvoidmain(String[]args)List<Dian>list=newArrayList<Dian>();list.add(newDian(2.3,12.2));list.add(newDian(3.6,29.0));list.add(newDian(15.4,2.4));list.add(newDian(18.4,34.2));list.add(newDian(14.2,15.5));list.add(newDian(17.1,37.9));list.add(newDian(23.1,18.2));list.add(newDian(14.2,34.1));list.add(newDian(30.2,45.8));list.add(newDian(38.6,22.4));list.add(newDian(48.6,32.4));list.add(newDian(18.6,22.4));list.add(newDian(78.6,62.4));list.add(newDian(23.3,39.0));list.add(newDian(13.9,43.0));list.add(newDian(133.3,234.0));DianleftDian=list.get(0);DianrightDian=list.get(0);for(Diandian:list){if(dian.getX()<leftDian.getX())leftDian=dian;elseif(dian.getX()>rightDian.getX())rightDian=dian;}pick.add(leftDian);pick.add(rightDian);QuickPackagep=newQuickPackage();Dian[]dians=newDian[list.size()];list.toArray(dians);System.out.println(leftDian.getX()+ ":" +leftDian.getY());System.out.println(rightDian.getX()+ ":" +rightDian.getY());Map<String,Dian[]>map=p.separate(dians,leftDian,rightDian);Dian[]left=map.get("left");Dian[]right=map.get("right");p.package1(left,leftDian,rightDian);p.package1(right,rightDian,leftDian);for(Diandian:pack){System.out.println("X:"+dian.getX()+""+"Y:"+dian.getY());}}//核心函數(shù)publicvoidpackage1(Dian[]dians,Diandian1,Diandian2){if(dians.length==2)return;if(dians.length==3){for(Diandian:dians){if(!dian.equals(dian1)&&!dian.equals(dian2)){pack.add(dian);}}return;}DianmaxDian=this.maxlength(dians,dian1,dian2);pack.add(maxDian);Map<String,Dian[]>map1=this.separate(dians,dian1,maxDian);Dian[]right=map1.get("right");Map<String,Dian[]>map2=this.separate(right,maxDian,dian2);this.package1(map1.get("left"),dian1,maxDian);this.package1(map2.get("left"),maxDian,dian2);/***將點分為在直線左和在直線右邊*@paramdians@paramdianl@paramdian2@return*/publicMap<String,Dian[]>separate(Dian[]dians,Diandianl,Diandian2){List<Dian>left=newArrayList<>();List<Dian>right=newArrayList<>();for(Diandian:dians){doubler=dian1.getX()*dian2.getY()+dian.getX()*dian1.getY()+dian2.getX()*dian.getY()-dian.getX()*dian2.getY()-dian2.getX()*dian1.getY()-dian1.getX()*dian.getY();if(r>1E-8)left.add(dian);elseif(r<1E-8&&r>-1E-8){left.add(dian);right.add(dian);}elseright.add(dian);}Dian[]leftDians=newDian[left.size()];Dian[]rightDians=newDian[right.size()];left.toArray(leftDians);right.toArray(rightDians);left=null;right=null;

Map<String,Dian[]>map=newTreeMap<String,Dian[]>();map.put("left”,leftDians);map.put("right”,rightDians);returnmap;}/***/****點集合中的點到dian1、dian2直線的距離@paramdians@paramdian1@paramdian2@return*/publicDianmaxlength(Dian[]dians,Diandian1,Diandian2){doubleA=(dian2.getY()-dian1.getY())/(dian2.getX()-dian1.getX());doubleB=-1;doubleC=dian2.getY()-((dian2.getY()-dian1.getY())/(dian2.getX()-dian1.getX()))*dian2.getX();doublemaxlength=0;DianmaxDian=null;for(Diandian:dians){if(lengthToLine(dian,A,B,C)>maxlength){maxlength=lengthToLine(dian,A,B,C);maxDian=dian;}returnmaxDian;}/***點到直線的距離*@paramdian@paramA@paramB@paramC@return*/publicdoublelengthToLine(Diandian,doubleA,doubleB,doubleC){doublei=((A*dian.getX()+B*dian.getY()+C)/Math.sqrt(A*A+B*B));returni>0?i:-i;}}classDian{doublex;doubley;publicDian(){}publicDian(doublex,doubley){this.x=x;this.y=y;}publicdoublegetX(){returnx;}publicvoidsetX(doublex){this.x=x;}publicdoublegetY()

returny;}publicvoidsetY(doubley){this.y=y;}}實驗二/*** 通過鍵盤輸入一個高精度的正整數(shù)n(n的有效位數(shù)^240)，去掉其中任*******意s個數(shù)字后，剩下的數(shù)字按原左右次序?qū)⒔M成一個新的正整數(shù)。編程對給定的*******【樣例輸入】<br/>178543<br/>S=4<br/>【樣例輸出】<br/>13<br/>*時間效率：O(sn)*空間效率：O(n)**@author陳雪桂**/publicclassDeleteNum{publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.比)；//獲取輸入的要刪樣例System.out.println("請輸入正整數(shù)序列：”)；Stringinput=scanner.nextLine();System.out.println("請輸入要刪除的位數(shù)：”);ints=scanner.nextInt();

verifyInput(input);char[]result=handle(input.toCharArray(),s);System.out.print("處理后的序列是:");for(inti=0;i<result.length;i++){System.out.print(result[i]);}}/***對輸入正整數(shù)序列進行驗證**@paramstr*/publicstaticvoidverifyInput(Stringstr){if(str==null||str==""){thrownewRuntimeException("請輸入要處理的正整數(shù)序列");}for(chars:str.toCharArray()){if(s<'0'||s>'9')thrownewRuntimeException("你輸入的正整數(shù)序列有誤");/****/******處理正整數(shù)序列@paraminput@return*/publicstaticchar[]handle(char[]input,ints){for(inti=0;i<s;i++){for(intj=0;j<input.length-1;j++){if(input[j]>input[j+1]){input[j]='#';break;}}}〃復(fù)制拷貝char[]result=newchar[input.length-s];intindex=0;for(inti=