中南大学算法实验报告

算法分析与设计实验报告学院：信息科学与工程学院 专业班级：物联网工程120X班 指导老师：李敏学号： 姓名： 目录一、HYPERLINK实验一：递归与分治二、HYPERLINK实验二：回溯三、HYPERLINK实验四：动态规划

一、HYPERLINK实验一：递归与分治一、实验目的理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。掌握分治算法的思想，对给定的问题能设计出分治算法予以解决。二、试验内容和步骤二分查找在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L，输出为x在L中的位置或者x不在L中的信息。三、具体实现分别使用了分治和递归来实现递归。四、实验代码packagealgorithm_check1_task1;importjava.util.Scanner;/*二分查找*/publicclassBinarySearch{ publicstaticvoidmain(String[]args){ int[]a=newint[5]; Scannersc=newScanner(System.in); System.out.println("请依次输入有序数组中的五个元素："); for(inti=0;i<a.length;i++){ a[i]=sc.nextInt(); } System.out.println("请输入需要查找的元素"); intfind=sc.nextInt(); divideSearchds=newdivideSearch(a,find);//分治法 recursionSearchrs=newrecursionSearch(a,find,0,a.length-1);//递归查找 }}packagealgorithm_check1_task1;publicclassdivideSearch{ divideSearch(inta[],intfind){ intfirst=0; intlast=a.length-1; intoutput=0; while(first<=last){ intmiddle=(int)((first+last)/2); if(find==a[middle]){ System.out.println("我是分治：找到啦哈哈哈"); output=1; break; }elseif(find>a[middle]){ first=middle+1; }elseif(find<a[middle]){ last=middle-1; } } if(output!=1){ System.out.println("我是分治:很遗憾，没有找到"); } }}packagealgorithm_check1_task1;publicclassrecursionSearch{ intoutput=0; recursionSearch(inta[],intfind,intfirst,intlast){ recursionsearch(a,find,first,last); if(output!=1){ System.out.println("我是递归：很抱歉，没有找到"); } } publicvoidrecursionsearch(inta[],intfind,intfirst,intlast){ intmiddle=(int)((first+last)/2); if(find==a[middle]){ System.out.println("我是递归：找到啦~！！"); output=1; }elseif(find>a[middle]&&last>first){ recursionsearch(a,find,middle+1,last); }elseif(find<a[middle]&&last>first){ recursionsearch(a,find,first,middle-1); } }}

二、HYPERLINK实验二：回溯一、实验目的：熟练掌握回溯算法二、实验内容：回溯算法的几种形式三、具体实现：0-1背包问题的回溯算法四、实验代码packagealgorithm_check2_task1;importjava.util.Scanner;/*回溯算法*/publicclassBackSearch{ intc; intnum; intmax=0; intw[]; intv[]; int[]a;//存放各物品的选取情况 Scannersc=newScanner(System.in); BackSearch(intc,intnum,intw[],intv[]){ this.c=c; this.num=num; this.w=w; this.v=v; a=newint[num]; search(0); System.out.println("最大的价值是："+max); } publicvoidsearch(intm){ if(m>=num) checkmax(); elseif(0<=m&&m<num){ a[m]=0; search(m+1); a[m]=1; search(m+1); } } publicvoidcheckmax(){ intweight=0; intvalue=0; for(inti=0;i<num;i++){ if(a[i]==1){ weight=weight+w[i]; value=value+v[i]; } } if(weight<=c&&value>max){ this.max=value; } }}packagealgorithm_check2_task1;importjava.util.Scanner;/*0-1背包问题的回溯算法*/publicclassPackage{ publicstaticvoidmain(String[]args){ Scannersc=newScanner(System.in); System.out.println("请输入背包能够承受的最大重量"); intc=sc.nextInt(); System.out.println("请输入物品的数目"); intnum=sc.nextInt(); intw[]=newint[num]; intv[]=newint[num]; for(inti=0;i<num;i++){ System.out.println("请输入第"+(i+1)+"件的物品的重量"); w[i]=sc.nextInt(); System.out.println("请输入第"+(i+1)+"件物品的价值"); v[i]=sc.nextInt(); } BackSearchbs=newBackSearch(c,num,w,v); }}

三、HYPERLINK实验四：动态规划一、实验目的：理解动态规划的基本思想，理解动态规划算法的两个基本要素最优子结构性质和子问题的重叠性质。熟练掌握典型的动态规划问题。掌握动态规划思想分析问题的一般方法，对较简单的问题能正确分析，设计出动态规划算法，并能快速编程实现。二、实验内容：编程实现讲过的例题：最长公共子序列问题、矩阵连乘问题、凸多边形最优三角剖分问题、电路布线问题等。本实验中的问题，设计出算法并编程实现。三、具体实现：最长公共子序列的动态规划四、实验代码packagealgorithm_check3;importjava.util.Scanner;//动态规划实现最小公共字符串问题publicclassSubString{ publicstaticvoidmain(String[]arg){ Scannersc=newScanner(System.in); System.out.println("请输入字符串A"); Stringa=sc.next(); System.out.println("请输入字符串B"); Stringb=sc.next();; comSubstring(a,b); } privatestaticvoidcomSubstring(Stringstr1,Stringstr2){ char[]a=str1.toCharArray(); char[]b=str2.toCharArray(); inta_length=a.length; intb_length=b.length; int[][]lcs=newint[a_length+1][b_length+1]; //初始化数组 for(inti=0;i<=b_length;i++){ for(intj=0;j<=a_length;j++){ lcs[j][i]=0; } } for(inti=1;i<=a_length;i++){ for(intj=1;j<=b_length;j++){ if(a[i-1]==b[j-1]){//当两个字符相等时，等于左上角的数字加1 lcs[i][j]=lcs[i-1][j-1]+1; } if(a[i-1]!=b[j-1]){ //当两个字符不等时，取上一个格子和左边一个格子里面的最大数 lcs[i][j]=lcs[i][j-1]>lcs[i-1][j]?lcs[i][j-1] :lcs[i-1][j]; } } } //回溯算法从二维矩阵中获取最长公共子序列 intmax_length=lcs[a_length][b_length]; char[]comStr=newchar[max_length]; inti=a_length,j=b_length; while(max_length>0){ if(lcs[i][j]!=lcs[i-1][j-1]){ if(lcs[i-1][j]==lcs[i][j-1]