学号姓名实验二递归与分治策略

《学号姓名实验二递归与分治策略》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法分析与设计实验报告学号姓名班级上课地点教师上课时间实验二递归与分治策略1.实验目的1」理解递归算法的思想，并学会应用递归思想解决问题。1.2掌握分治法的基本思想，并学会应用分治思想解决问题。2.实验环境2.1Eclipse2.2WindowXP3.实验内容（以下三题选做两题，也可以全做）3」全排列问题：输入n个字符，要求输出这n个字符的所有排列情况。要求利用递归与分治思想设计与实现。3.2二分搜索问题：输入n个按升序排列的元素和待查找的元素x,输出是否存在这一特定元素xo要求利用递归与分治思想设计与实现。3.3随机快速排序问题：利用随机快速排列算法对输入的n个元

2、素从小到大排列，并输出排列结果。要求利用递归与分治思想设计与实现。4.教师批改意见签字：H期：成绩实验报告细表1全排列].]算法设计思想可文字描适当添加一些伪代码，或者流程图来进行补充说明1、将当前元索与后面位置的每个元索依此交换2、交换后取后一个位置的元索为当前元索的位置，再执行13、当当前位置是最后一个元索的位置则输岀全排列伪代码为：publicstaticvoidperm(in]arrintk^intm){if(k==m-l){System.out・printIn(Arrays・1?05£厂匚门9(81"“));}else{for(inti=k;i

3、+){swap(arr，k，i);per/n(arrJk+lJm);swap(arr,k,i);}}}1.2程序源码全排列代码：packagequanpailie;importjava.uti1.Arrays;publicclassquanpailie{publicstaticvoidmain(String[]args)int[]arr={l,2,3};perm(arrJ0Jam.length);publicstaticvoidswap(int[]arrJinti^intj)inttemp=arr[i];arr[i]=arr[j];arr[j]二temp;}publ

4、icstaticvoidperm(int[Jarr^intintm){if(k==m-l){System.out.printIn(Arrays.toString(arr));}else{for(inti二k;i

5、7binjavaw.exe(2014年10月8日上午9:25:04)2313211J1J1J1J1J1J3-231121.4心得体会全排列在数学屮有学过，但是用代码实现由一定的难度。通过参考和修正，终于得到正确代码。这是一个很棒的过程。2二分搜索问题2]算法设计思想将n个元索以成个数大致相同的两半，取a[n/2]与x进行比较，如果x=a[n/2],则找到x,算法终止。若xva[n/2],则只要在数组a的左半部分继续搜索，若x>a[n/2],则只要在数组a的右半部分继续搜索。二分查找伪代码为publicstaticintbinarysearch(irrtleft,

6、intright,irrtx){if(left<=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;elseif(xa[middle])returnbinarySearch^a^miMle+l^right,x);}elsereturn-1;}2.2程序源码packagebinarySearch;publicclassbinarySearch{publicstaticvoidmain(String

7、[]args){inta[卜{2,4,8,9,18,35,90,98};System•out•printin(binarySea厂c/?(a，0，a•length-1^18));publicstaticintbinarySearch(intleft,intright,intx)if(left<=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;elseif(xa[middle])