算法设计与分析实验报告
重 庆 交 通 大 学 学 生 实 验 报 告
实验课程名称 算法设计与分析 开课实验室 数学实验室
学院 数学与统计学院 年级13 专业班 信息与计算科学2 学 生 姓 名 辜朕圆 学 号 631322020223 开 课 时 间 2015 至 2016 学年 第 1 学期
假设合理 建模求解全面 结果分析完善 文档清晰 综合成绩 教师姓名
优 优 优 优 良 良 良 良 中 中 中 中 差 差 差 差 韩逢庆 2015-2016学年 第一学期
算法设计与分析实验报告
实验报告题目 实验一 递归与分治策略
开课实验室：数学实验室 指导老师：韩逢庆 时间：2015.9 学院：理学院 专业：信息与计算科学 班级：2013级2班
姓名： 辜朕圆 学号：631322020223
一、 实验目的
1．加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；
2．提高学生利用课堂所学知识解决实际问题的能力； 3．提高学生综合应用所学知识解决实际问题的能力。 二、 实验内容
题目 ①设a[0:n-1]是已排好序的数组。请写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。
②写出三分搜索法的程序。 三、 实验要求
（1）用分治法求解…问题；
（2 ）再选择自己熟悉的其它方法求解本问题； （3）上机实现所设计的所有算法； 四、 实验过程设计（算法设计过程）
1、已知a[0:n-1]是一个已排好序的数组，可以采用折半查找（二分查找）算法。如果搜索元素在数组中，则直接返回下表即可；否则比较
2015-2016学年 第一学期
算法设计与分析实验报告
搜索元素x与通过二分查找所得最终元素的大小，注意边界条件，从而计算出小于x的最大元素的位置i和大于x的最小元素位置j。 2、先判定输入的数x是否在数组的范围内，再将n个元素分成大致相同的三部分，取在数组a的左三分之一部分中继续搜索x。如果x>a[san2]，则只需在数组a的右三分之一部分中继续搜索x。上述两种情况不成立时，则在数组中间的三分之一部分中继续搜索x。 五、 实验结果分析
(1)例子为数组a[1,2,3,4,5,6,7,8,9],n=9,x=9。
实验结果为
(2)例子为数组a[1,2,3,4,5],x=3,n=5。
实验结果为
时间复杂性：最好情况下，最坏情况下
二分搜索每次把搜索区域砍掉一半，很明显时间复杂度为O(log n)。（n代表集合中元素的个数） 三分搜索法：O（3log3n） 空间复杂性分析：O（1）。
六、 实验体会
本次试验解决了二分查找和三分查找的问题，加深了对分治法的
2015-2016学年 第一学期
算法设计与分析实验报告
理解，收获很大，同时我也理解到学习算法是一个渐进的过程，算法可能一开始不是很好理解，但是只要多看几遍，再实践操作，毕竟实践是检验真理的唯一标准，只要动手就能感受自己写出算法的喜悦，从而良性循环越学越好。 七、 附录：（源代码）
(1) public static int binarySearch(int a[],int x,int n)
{
int left=0;int right=n-1;int i,j; while(left<=right) {
int middle=(left+right)/2;
if(x==a[middle]){i=j=middle;System.out.println(\);return if(x>a[middle])left=middle+1; else right=middle-1; }
i=right;j=left; return 0; }
1;}
(2)
public class sanfen {
public static int sanSearch(int []a,int x,int n){
int left=0;int right=n-1; while(right>left){
if(xa[right])
{ System.out.println(\根本不在数组里\); break; }
int san1=(left+right)/3; int san2=2*(left+right)/3; if(x==a[san1])
{
System.out.println(\找到了\); return san1; }
else if(xa[san2])left=san1+1;
2015-2016学年 第一学期
算法设计与分析实验报告
else{left=san1;right=fan2;} } }
}
public static void main(String []args) { }
sanfen s=new sanfen(); int []b={1,2,3,4,5}; s.sanSearch(b,3,5); return -1;
实验二 动态规划
一、实验目的
1．加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；
2．提高学生利用课堂所学知识解决实际问题的能力； 3．提高学生综合应用所学知识解决实际问题的能力。 二、实验内容
(1)设计一个O（n）时间的算法，找出由n个数组成的序列的最长单调递增子序列
(2)考虑下面的整数线性规划问题：maxi?12?cjnii ,i?1?axnii?b
xi为非负整数，1<=i<=n 试设计一个解此问题的动态规划算法，并分
析算法的计算复杂性。 三、实验要求
（1）用动态规划思想求解最优问题；
（2）再选择自己熟悉的程序设计语言实现所有算法； （3）分析所设计的算法的时间/空间复杂性。
2015-2016学年 第一学期