算法实验报告.doc

实验一 快速排序与折半搜索1. 实验描述：具体描述见课本10.4节快速排序和11.3节折半搜索问题。2. 实验目的：通过快速排序问题，巩固并详细分析分治方法思想和解题步骤。3.实验设计思路：快速排序：折半查找：以处于区间中间位置记录的关键字和给定值比较，若相等，则查找成功，如不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值或区间大小小于零时为止。其中缩小范围有两种实现方式，一是使用循环的方式，二是使用递归的方式。本次实验选择的是使用循环的方式实现查找。4.实验环境及工具：操作系统：win7操作系统开发工具：eclipse3.4、jdk1.6开发工具：java5.实验数据结构及算法：快速排序：QuickSort类快速排序: public static void quickSort(Element elementArray,int startIndex,int endIndex)对子数组进行分割：public static int partition(Element elementArray,int starIndex,int endIndex)输出排序结果：public static void outputResult(Element elementArray)折半查找：SearchElement 打印输出结果：public static void PrintResult(int position, int x) 查询：public static int Search(int array, int x)/存在则返回当前位置，否则返回-1打印数组中的元素:public static void PrintArray(int array) 6.实验结果截图：7.实验总结：通过本实验，我了解掌握了快速排序、折半搜索的原理和具体实现过程，其实只要理解了快速排序、折半搜索算法原理，就可较好的编程实现快速排序算法。实验二 计数基数排序1. 实验描述：具体描述见课本10.8节计数排序及10.9节基数排序的实验。2.实验目的：通过计数排序及基数排序问题，更进一步了解排序思想和程序设计思想与技巧。3.实验设计思路：基数排序的总体思路就是将待排序数据拆分成多个关键字进行排序，也就是说，基数排序的实质是多关键字排序。多关键字排序的思路是将待排数据里德排序关键字拆分成多个排序关键字；第1个排序关键字，第2个排序关键字，第3个排序关键字.然后，根据子关键字对待排序数据进行排序。多关键字排序时有两种解决方案：最高位优先法（MSD）(Most Significant Digit first)最低位优先法（LSD）(Least Significant Digit first)4.实验环境及工具：操作系统：win7操作系统开发工具：eclipse3.4、jdk1.6开发工具：java5.实验数据结构及算法： class MultiKeyRadixSortTest public static void radixSort(int data, int radix, int d) public static void print(int data) 实验源码：import java.util.Arrays;public class Mu1tiKeyRadixSortTest public static void main(String args) int data = new int 1188,192,221,12,23 ;print(data);radixSort(dataj 10; 4);System.out.print1n(排序后数组:“);print(data);public static void radixSort(int data,int radixj int d) / /缓存数组int tmp = new intdata.1ength;/ buckets用于记录待排序元素的信息/ buckets数组定义了max-min个桶int buckets = new intradix;for(int i=e,rate=1; id; i+) / 重置count数组，开始统计下一个关键字Arrays.fi1l(buckets,0);1将data中的元素完全复制到tmp数组中System.arraycopy(dataj ,tmp,data.1ength);/ 计算每个待排序数据的子关键字for (int j= 8; j data.1ength; j+) int subKey = (tmpj 1rate) % radix;buckets subkey+; for (int j= 1; j= e; m-) (int m = data.1ength- 1;forint subKey = (tmpm /rate) % radix;data-bucketssubKey = tmpm;rate *= radix;public static void print(int data) (inti=e;idata.1ength; i+) forSystem.out.print(datai +“t);System.out.print1n( );4.6实验结果截图：4.7实验总结：通过本实验，自己了解了基数排序的原理和具体实现过程，其实只要理解了基数排序算法原理，就可较好的编程实现基数排序算法。实验三 最长公共子序列问题1. 实验描述：具体描述见课本4.3节，最长公共子序列问题。2. 实验目的：通过最长公共子序列问题，巩固并详细分析动态规划思想和解题步骤。3.实验设计思路： 设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk，则(1)若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。(2)若xmyn且zkxm，则Z是xm-1和Y的最长公共子序列。(3)若xmyn且zkyn，则Z是X和yn-1的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。程序的设计思路是:输入两个字符串，对两个串的存储数组x，y进行动态分配。调用函数void lcsLength(char x,char y,int c,int b)，求得最优值；调用函数 void lcs(int i,int j,char x,int b)构造最长公共子序列调用函数，最后得出最长公共子序列。4.实验环境及工具：操作系统：win7操作系统开发工具：eclipse3.4、jdk1.6开发工具：java5.实验数据结构及算法：Class LCS类定义resultList来存放结果：public static List resultList = new ArrayList();计算最优值：public static void lcsLength(char x,char y,int c,int b)构造最长公共子序列：public static void lcs(int i,int j,char x,int b)6.实验结果截图：7.实验总结：在做本次试验之前,自己对动态规划法不是非常的理解,后来结合课本看了利用动态规划法求最长公共子系列的基本步骤和具体例子之后,自己基本上了解了动态规划法的基本原理。课本上所列举的利用动态规划法解最长公共子序列的代码很简单,懂得动态规划法解最长公共子序列的基本原理之后,结合课本所提供的相关代码编码完成本次实验内容也是蛮容易，实现起来较顺利。