廣東工業(yè)大學(xué)算法設(shè)計(jì)實(shí)驗(yàn)報(bào)告

算法設(shè)計(jì)分析實(shí)驗(yàn)報(bào)告專業(yè)班級(jí) 軟件工程4班學(xué)號(hào)3111006218姓名 陳雪桂授課教師（2014年06月）目錄TOC\o"1-5"\h\z\o"CurrentDocument"一、 實(shí)驗(yàn)?zāi)康?3\o"CurrentDocument"二、 實(shí)驗(yàn)環(huán)境 3\o"CurrentDocument"三、 實(shí)驗(yàn)內(nèi)容 3實(shí)驗(yàn)內(nèi)容 3\o"CurrentDocument"實(shí)驗(yàn)一 3\o"CurrentDocument"實(shí)驗(yàn)二 3\o"CurrentDocument"算法設(shè)計(jì)思想 4實(shí)驗(yàn)一 .4\o"CurrentDocument"實(shí)驗(yàn)二 4\o"CurrentDocument"程序設(shè)計(jì) 4實(shí)驗(yàn)一 4\o"CurrentDocument"實(shí)驗(yàn)二 10\o"CurrentDocument"數(shù)據(jù)輸入和結(jié)果輸出 12實(shí)驗(yàn)一 12\o"CurrentDocument"實(shí)驗(yàn)二 13\o"CurrentDocument"算法復(fù)雜性分析 13實(shí)驗(yàn)二 13\o"CurrentDocument"四、 實(shí)驗(yàn)心得與小結(jié) 13\o"CurrentDocument"五、 指導(dǎo)教師成績(jī)?cè)u(píng)定 13、實(shí)驗(yàn)?zāi)康恼莆账惴◤?fù)雜性概念。理解影響算法時(shí)間復(fù)雜性的因素。理解漸進(jìn)時(shí)間復(fù)雜性的概念。掌握分析算法復(fù)雜度的方法。二、實(shí)驗(yàn)環(huán)境MyEclipse三、實(shí)驗(yàn)內(nèi)容（1）實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)一理解分治法的效率，用分治法完成快包算法，并給出一個(gè)運(yùn)行實(shí)例。實(shí)驗(yàn)二通過鍵盤輸入一個(gè)高精度的正整數(shù)n（n的有效位數(shù)＜240），去掉其中任意s個(gè)數(shù)字后，剩下的數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。編程對(duì)給定的n和s，尋找一種方案，使得剩下的數(shù)字組成的新數(shù)最小。【樣例輸入】178543S=4【樣例輸出】13實(shí)現(xiàn)該算法，分析算法的效率。并給出一個(gè)運(yùn)行實(shí)例：n=“你的學(xué)號(hào)”，s=7。算法設(shè)計(jì)思想實(shí)驗(yàn)一采用分治法的思想，最最左和最右兩個(gè)節(jié)點(diǎn)A、B，分別找到離兩個(gè)節(jié)點(diǎn)所在直線兩邊找距離最遠(yuǎn)的兩個(gè)點(diǎn)C、D，再遞歸下去直到算法結(jié)束實(shí)驗(yàn)二正整數(shù)序列遍歷，找到第一個(gè)a[j]>a[j+1],刪去a[j],重復(fù)s次，也就是刪去s個(gè)數(shù)程序設(shè)計(jì)實(shí)驗(yàn)/***快包問題**@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);/***將點(diǎn)分為在直線左和在直線右邊*@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;}/***/****點(diǎn)集合中的點(diǎn)到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;}/***點(diǎn)到直線的距離*@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í)驗(yàn)二/*** 通過鍵盤輸入一個(gè)高精度的正整數(shù)n(n的有效位數(shù)^240)，去掉其中任*******意s個(gè)數(shù)字后，剩下的數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。編程對(duì)給定的*******【樣例輸入】<br/>178543<br/>S=4<br/>【樣例輸出】<br/>13<br/>*時(shí)間效率：O(sn)*空間效率：O(n)**@author陳雪桂**/publicclassDeleteNum{publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.比)；//獲取輸入的要?jiǎng)h樣例System.out.println("請(qǐng)輸入正整數(shù)序列：”)；Stringinput=scanner.nextLine();System.out.println("請(qǐng)輸入要?jiǎng)h除的位數(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]);}}/***對(duì)輸入正整數(shù)序列進(jìn)行驗(yàn)證**@paramstr*/publicstaticvoidverifyInput(Stringstr){if(str==null||str==""){thrownewRuntimeException("請(qǐng)輸入要處理的正整數(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=