广东工业大学算法设计实验报告

算法设计分析实验报告专业班级 软件工程4班学号3111006218姓名 陈雪桂授课教师（2014年06月）目录TOC\o"1-5"\h\z\o"CurrentDocument"一、 实验目的 3\o"CurrentDocument"二、 实验环境 3\o"CurrentDocument"三、 实验内容 3实验内容 3\o"CurrentDocument"实验一 3\o"CurrentDocument"实验二 3\o"CurrentDocument"算法设计思想 4实验一 .4\o"CurrentDocument"实验二 4\o"CurrentDocument"程序设计 4实验一 4\o"CurrentDocument"实验二 10\o"CurrentDocument"数据输入和结果输出 12实验一 12\o"CurrentDocument"实验二 13\o"CurrentDocument"算法复杂性分析 13实验二 13\o"CurrentDocument"四、 实验心得与小结 13\o"CurrentDocument"五、 指导教师成绩评定 13、实验目的掌握算法复杂性概念。理解影响算法时间复杂性的因素。理解渐进时间复杂性的概念。掌握分析算法复杂度的方法。二、实验环境MyEclipse三、实验内容（1）实验内容实验一理解分治法的效率，用分治法完成快包算法，并给出一个运行实例。实验二通过键盘输入一个高精度的正整数n（n的有效位数＜240），去掉其中任意s个数字后，剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s，寻找一种方案，使得剩下的数字组成的新数最小。【样例输入】178543S=4【样例输出】13实现该算法，分析算法的效率。并给出一个运行实例：n=“你的学号”，s=7。算法设计思想实验一采用分治法的思想，最最左和最右两个节点A、B，分别找到离两个节点所在直线两边找距离最远的两个点C、D，再递归下去直到算法结束实验二正整数序列遍历，找到第一个a[j]>a[j+1],删去a[j],重复s次，也就是删去s个数程序设计实验/***快包问题**@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());}}//核心函数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;}}实验二/*** 通过键盘输入一个高精度的正整数n(n的有效位数^240)，去掉其中任*******意s个数字后，剩下的数字按原左右次序将组成一个新的正整数。编程对给定的*******【样例输入】<br/>178543<br/>S=4<br/>【样例输出】<br/>13<br/>*时间效率：O(sn)*空间效率：O(n)**@author陈雪桂**/publicclassDeleteNum{publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.比)；//获取输入的要删样例System.out.println("请输入正整数序列：”)；Stringinput=scanner.nextLine();System.out.println("请输入要删除的位数：”);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]);}}/***对输入正整数序列进行验证**@paramstr*/publicstaticvoidverifyInput(Stringstr){if(str==null||str==""){thrownewRuntimeException("请输入要处理的正整数序列");}for(chars:str.toCharArray()){if(s<'0'||s>'9')thrownewRuntimeException("你输入的正整数序列有误");/****/******处理正整数序列@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;}}}〃复制拷贝char[]result=newchar[input.length-s];intindex=0;for(inti=