算法设计与分析实验

《算法设计与分析实验》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验一递归1.1实验目的1）掌握递归算法的概念，理解递归算法的思想2）掌握递归函数的写法，熟练运用递归函数3）正确分析递归算法的时空复杂度1.2实验内容1）编写程序递归地实现阶乘函数；2）编写程序递归地实现Fibonacci数列；3）编写程序递归实现整数划分问题1.3实验步骤1）写出阶乘函数的定义公式n!=1n=0nn-1!n>02）创建一个java程序，递归实现阶乘函数publicstaticintfactorial(intn){if(n==0)return1;returnn*factorial(n-1);}3）写出Fibonacci数列的定义公式Fn=

2、1n=0,1Fn-1+Fn-2n>14）创建一个java程序，递归实现Fibonacci数列publicstaticintfibonacci(intn){if(n<=1)return1;returnfibonacci(n-1)+fibonacci(n-2);}5）分析并写出整数划分的递归公式qn,m=1n=1,m=1qn,nnm>16）创建一个java程序，递归实现整数划分问题publicstaticintq(intn,intm){if((n<1)

3、

4、(m<1))return0;if((n==1)

5、

6、

7、(m==1))return1;if(n

8、程实现二分搜索publicstaticintbinarySearch(int[]a,intx,intn){intleft=0;intright=n-1;while(left<=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle])left=middle+1;elseright=middle-1;}return-1;}3）写出快速排序算法的伪代码4）创建一个java程序，编程实现快速排序privatestaticvoidqSort(intp,intr){if(p

9、0);if(i>=j)break;MyMath.swap(a,i,j);}a[p]=a[j];a[j]=x;returnj;}2.4实验报告把实验内容（1），（2）写到实验报告上。

10、实验三动态规划（一）3.1实验目的1）掌握动态规划的概念，理解动态规划的思想2）掌握递归和递推这两种实现动态规划的实现方法3）正确分析动态规划的时空复杂度3.2实验内容1）编程实现矩阵连乘问题（对于给定的相继n个矩阵{A1,A2,…,An}，如何确定计算矩阵连乘积A1A2…An的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少）；2）编程实现最长公共子序列问题（给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…yn},找出X和Y的最长公共子序列）；3）编程实现3个序列的最长公共子序列问题。（选做）3.3实验步骤1）找出矩阵连乘问题中的状态

11、转移方程设计算A[i:j],1<=i<=j<=n,所需的最小数乘次数为m[i][j],则原问题的最优值为m[1][n].动态转移方程：mij=0i=jmini≤k

12、;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[