算法实验报告.doc

算法设计与分析实验报告重 庆 交 通 大 学学 生 实 验 报 告实验课程名称 算法设计与分析 开课实验室 数学实验室 学院 数学与统计学院 年级13 专业班 信息与计算科学2 学 生 姓 名 辜朕圆 学 号 631322020223 开 课 时 间 2015 至 2016 学年 第 1 学期假设合理优良中差建模求解全面优良中差结果分析完善优良中差文档清晰优良中差综合成绩教师姓名韩逢庆实验报告题目实验一 递归与分治策略开课实验室：数学实验室 指导老师：韩逢庆 时间：2015.9学院：理学院 专业：信息与计算科学 班级：2013级2班姓名： 辜朕圆 学号：631322020223一、 实验目的 1加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握； 2提高学生利用课堂所学知识解决实际问题的能力； 3提高学生综合应用所学知识解决实际问题的能力。二、 实验内容 题目 设a0:n-1是已排好序的数组。请写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。写出三分搜索法的程序。三、 实验要求 （1）用分治法求解问题； （2 ）再选择自己熟悉的其它方法求解本问题； （3）上机实现所设计的所有算法；四、 实验过程设计（算法设计过程）1、已知a0:n-1是一个已排好序的数组，可以采用折半查找（二分查找）算法。如果搜索元素在数组中，则直接返回下表即可；否则比较搜索元素x与通过二分查找所得最终元素的大小，注意边界条件，从而计算出小于x的最大元素的位置i和大于x的最小元素位置j。2、先判定输入的数x是否在数组的范围内，再将n个元素分成大致相同的三部分，取在数组a的左三分之一部分中继续搜索x。如果xasan2，则只需在数组a的右三分之一部分中继续搜索x。上述两种情况不成立时，则在数组中间的三分之一部分中继续搜索x。五、 实验结果分析(1) 例子为数组a1,2,3,4,5,6,7,8,9,n=9,x=9。实验结果为(2) 例子为数组a1,2,3,4,5,x=3,n=5。 实验结果为时间复杂性：最好情况下，最坏情况下二分搜索每次把搜索区域砍掉一半，很明显时间复杂度为O(log n)。（n代表集合中元素的个数）三分搜索法：O（3log3n）空间复杂性分析：O（1）。六、 实验体会 本次试验解决了二分查找和三分查找的问题，加深了对分治法的理解，收获很大，同时我也理解到学习算法是一个渐进的过程，算法可能一开始不是很好理解，但是只要多看几遍，再实践操作，毕竟实践是检验真理的唯一标准，只要动手就能感受自己写出算法的喜悦，从而良性循环越学越好。七、 附录：（源代码）(1)public static int binarySearch(int a,int x,int n)int left=0;int right=n-1;int i,j;while(leftamiddle)left=middle+1;else right=middle-1;i=right;j=left;return 0;(2)public class sanfen public static int sanSearch(int a,int x,int n)int left=0;int right=n-1;while(rightleft)if(xaright)System.out.println(根本不在数组里);break;int san1=(left+right)/3;int san2=2*(left+right)/3;if(x=asan1)System.out.println(找到了);return san1;else if(xasan2)left=san1+1; elseleft=san1;right=fan2; return -1;public static void main(String args)sanfen s=new sanfen();int b=1,2,3,4,5;s.sanSearch(b,3,5);实验二 动态规划一、实验目的1加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2提高学生利用课堂所学知识解决实际问题的能力；3提高学生综合应用所学知识解决实际问题的能力。2、 实验内容(1)设计一个O（）时间的算法，找出由n个数组成的序列的最长单调递增子序列(2)考虑下面的整数线性规划问题：max ,为非负整数，1=i=n 试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。三、实验要求（1）用动态规划思想求解最优问题；（2）再选择自己熟悉的程序设计语言实现所有算法；（3）分析所设计的算法的时间/空间复杂性。四、实验过程设计（算法设计过程）(1)用数组b0:n-1记录以ai,0=in,为结尾元素的最长递增子序列的长度。序列a的最长递增子序列的长度为 据此将计算bi转化为i个规模更小的子问题。(2)转化成一般背包问题即可，具体算法过程与背包问题大同小异五、实验结果分析 (2)时间复杂度为O(nb)六、实验体会学会了用动态规划的想法来解决背包问题，为了给出合适的测试数据也是捣鼓了好久，让我知道算法思想重要，他的测试和实现也很重要，这次课题的限制降低很多让我们有更多的思考空间，提升了想象力。七、附录：（源代码）(1)int pia()int i,j,k;for(i=1,b0;in;j+)for(j=0,k=0;ji;j+)if(aj=ai&kbj)k=bj;bi=k-1;return maxL(n);int maxL(int n)for(int i=0,temp=0;itemp)temp=bi;return temp;(2)import java.util.Scanner;public class beibao static void knapsack(int n,float c,float v,floatw,float x) Sort(n,v,w); int i; for(i=1;i=n;i+) xi=0; for(i=1;ic) break; xi=1; c-=wi; if(i=n) xi=c/wi; static void Sort(int n, float v, float w) int i,j; for(i=0;in-1;i+) for(j=i+1;jn;j+) if(vi/wivj/wj) float temp; temp=vi; vi=vj; vj=temp; temp=wi; wi=wj; wj=temp; public static void main(String args) Scanner scan =new Scanner(System.in); System.out.println(输背包中物品的个数：); int n=scan.nextInt(); System.out.println(输入背包的容量：); float c=scan.nextFloat(); float v=new floatn+1; float w=new floatn+1; float x=new floatn+1; for(int i=1;i=n;i+) System.out.println(输入第+i+的重量); wi=scan.nextFloat(); System.out.println(输入第+i+的价值); vi=scan.nextFloat(); knapsack(n,c,v,w,x); System.out.println(一般背包问题的解为：); for(int i=1;iN，则不可能到达终点； 加油站间的距离相等，即i=aj=LN，则加油次数k=n/N(n%N=0)或k=n/N+1(n%N！=0)； 加油站间的距离不相等，即i！=aj，则加油次数k通过下面的算法求解。5、 实验结果分析(1) 时间复杂度为O()(2) 时间复杂度为O(n)六、实验体会通过这次实验让我感受到独立思考写算法的乐趣，尤其是加油站问题，其中遇到很多困难，但是在和同学们的讨论下，我茅塞顿开，感受到了贪心算法是如何进行他的贪心行为，大大提升了我的编程能力和对贪心算法的理解。7、 附录：（源代码）(1)public class Dijkstra static int MAX_SIZE=6; public static void dijkstra(int v,floata,floatdist,intprev) int n=dist.length-1; if(vn)return; boolean s=new booleann+1; for(int i=1;i=n;i+) disti=avi; si=false; if(disti=Float.MAX_VALUE) previ=0; else previ=v; distv=0;sv=true; for(int i=1;in;i+) float temp=Float.MAX_VALUE; int u=v; for(int j=1;j=n;j+) if(!sj)&(distjtemp) u=j; temp=distj; su=true; for(int j=1;j=n;j+) if(!sj)&(aujFloat.MAX_VALUE) float newdist=distu+auj; if(newdistdistj) distj=newdist; prevj=u; public static void main(String args) float a=new floatMAX_SIZEMAX_SIZE;floatdist=new floatMAX_SIZE;int prev=new intMAX_SIZE; for(int i=0;i6;i+) for(int j=0;j6;j+) aij=Float.MAX_VALUE; a12=10; a14=30;a15=100; a23=50; a35=10; a43=20; a45=60; int v=1;/假设从顶点1处出发 dijkstra(v,a,dist,prev); System.out.println(从1出发到2、3、4、5的最短路径依次是:); for(int j=2;j6;j+) System.out.println(distj); int z=prev5,y=prevz,x=prevy; System.out.println(从1到5最短路径经过的点为：); System.out.print(x+ +y+ +z+ +5); (2)public class qiyou public static void greedy(int v,int n,int N)/定义每个加油站的距离存进数组v，定义加满油可以开n公里/定义要跑N公里 int s=v.length;int k=0; /初始化经过加油站的数量kint load=0;/初始化走过的长度if(Nn)System.out.println(不需要加油);for(int i=0;in) System.out.println(还没到加油站就没油了！);for(int i=0;in) k+; load=vi-1;/load大于n所以加油点必在i-1 n=n+load; System.out.println(最少加+k+次油);public static void main(String args)qiyou s=new qiyou();s.greedy(v, n, N);/改这个就能测试实验四 回溯法一、实验目的1掌握能用回溯法求解的问题应满足的条件；2加深对回溯法算法设计方法的理解与应用；3锻炼学生对程序跟踪调试能力；4通过本次实验的练习培养学生应用所学知识解决实际问题的能力。二、实验内容1、对于一个n位正整数a，去掉其中任意k(k=n)个数字后，剩下的数字按原次序排列可以组成一个新的正整数。设计一个删数算法，使得剩下的数字组成的正整数最小2、n皇后问题三、实验要求。（1）用回溯法算法设计方法求解问题；（2）上机实现所设计的算法；（3）分析所设计的算法的时间/空间复杂性。四、实验过程设计（算法设计过程）1、一个n位数，删去k位后，也就是剩下一个 n-k位 数，那么这个数要最小，我们就要保证我们我们得出的数是所有删除后得到的数的最小值。问题转换一下，用回溯法的思想如果最后就剩下一位，结果就是这些数字的最小值，最后剩下两位在这个区间（从左往右数第一位，从右往左数第二位），且是其中的最小值，而次最高位在这个区间（刚才最高位+1，从右往左数第一位即是最后一位）；2、n皇后问题中用完全n叉树表示解空间，约束place减去不满足行列和斜线约束的子树。递归方法backtrack（1）实现对整个解空间的回溯搜索。Backtrack（i）搜索解空间中第i层子树，sum记录当前已找到的可行方案数。五、实验结果分析(1)例如输入1 7 4 0 9 4 8 8 2 4 5 5 长度为12，删完剩下5. 时间复杂度:0（k*(n-k)）（2）当a=8即8皇后问题时结果为： sum=98 时间复杂度为o(n!)六、实验体会在这个实验中给我印象最深的是n皇后问题，只有n大于三才能进行，并且还有递归和非递归两种形态，而且多个函数的关联最让我着迷，应用backtrack来进行回溯算法，用place来进行判断，环环相扣，使人深陷其中，通过这次实验让我提升了自己的动手能力和对回溯算法的理解能力，最重要的还是老师教的好。七、附录：（源代码）(1)#includeusing namespace std ;const int K = 5 ;const int size = 12 ;void GetMinBit( int * data,int length,int start,int end,int &bit ) if( data != NULL | length 1 ) if( 0 = start & start = end & end length ) int min = *(data+start) ; bit = start; for( int i=start ; i = end ; i+ ) if( *(data+i) min ) min = *(data+i); bit = i; else coutstart start end end length lengthendl ; system(pause) ; else coutlength length data dataendl; system(pause) ; int GetMinData(int * data,int length,int k ) if( data != NULL | length 1 ) if( 0 = k & k length ) int result = 0 ; int bit = -1 ; int end = k ; while( endlength ) GetMinBit( data,length,bit+1,end,bit ); result = result*10 + *(data+bit); end+ ; return result ; else coutk k length lengthendl; system(pause) ; else coutlength length data dataendl; system(pause) ; int main() int * data = new intsize; for(int i= 0 ;isize ; i+ ) *(data+i)=r