《算法设计与分析实验》由会员分享，可在线阅读，更多相关《算法设计与分析实验（10页珍藏版）》请在金锄头文库上搜索。
1、实验一 递归1.1实验目的1）掌握递归算法的概念，理解递归算法的思想2）掌握递归函数的写法，熟练运用递归函数3）正确分析递归算法的时空复杂度1.2 实验内容1）编写程序递归地实现阶乘函数；2）编写程序递归地实现Fibonacci数列；3）编写程序递归实现整数划分问题1.3 实验步骤1）写出阶乘函数的定义公式n!=1 n=0nn-1! n02）创建一个java程序，递归实现阶乘函数public static int factorial(int n)if(n=0) return 1;return n*factorial(n-1);3）写出Fibonacci数列的定义公式Fn=1 n=0,1Fn-1
2、+Fn-2 n14）创建一个java程序，递归实现Fibonacci数列public static int fibonacci(int n)if(n=1) return 1;return fibonacci(n-1)+fibonacci(n-2);5）分析并写出整数划分的递归公式qn,m=1 n=1,m=1qn,n nm16）创建一个java程序，递归实现整数划分问题public static int q(int n,int m)if(n1)|(m1) return 0;if(n=1)|(m=1) return 1;if(nm) return q(n,n);if(n=m) return q(n
3、,m-1)+1;return q(n,m-1)+q(n-m,m);1.4 实验报告把实验内容（1），（2），（3）写到实验报告上。实验二 分治策略2.1 实验目的1）掌握分治法的概念，理解分治法的思想2）掌握二分搜索，快速排序等最基本二分法的应用3）正确分析分治法的时空复杂度2.2 实验内容1）编程实现在一给定数列中查找某个元素；2）编程实现快速排序算法；3）编程实现最接近点对的问题。（选做）2.3 实验步骤1）写出二分搜索算法的伪代码2）创建一个java程序，编程实现二分搜索public static int binarySearch(int a,int x,int n)int left=0
4、;int right=n-1;while(leftamiddle) left=middle+1;else right=middle-1;return -1;3）写出快速排序算法的伪代码4）创建一个java程序，编程实现快速排序private static void qSort(int p,int r) if(pr) int q=partition(p,r); qSort(p,q-1); qSort(q+1,r); private static int partition(int p,int r) int i=p,j=r+1; Comparable x=ap; while(true) while
5、(a+pareTo(x)0 & i0); if(i=j) break; MyMath.swap(a,i,j); ap=aj; aj=x; return j;2.4 实验报告把实验内容（1），（2）写到实验报告上。实验三 动态规划（一）3.1 实验目的1）掌握动态规划的概念，理解动态规划的思想2）掌握递归和递推这两种实现动态规划的实现方法3）正确分析动态规划的时空复杂度3.2实验内容1）编程实现矩阵连乘问题（对于给定的相继n个矩阵A1,A2,An，如何确定计算矩阵连乘积A1A2An的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少）；2）编程实现最长公共子序列问题（给定两个序列X=x1,x
6、2,xm和Y=y1,y2,yn,找出X和Y的最长公共子序列）；3）编程实现3个序列的最长公共子序列问题。（选做）3.3实验步骤1）找出矩阵连乘问题中的状态转移方程设计算Ai:j,1=i=j=n,所需的最小数乘次数为mij,则原问题的最优值为m1n.动态转移方程：mij=0 i=jminikjmik+mk+1j+pi-1pkpj ij2）创建一个java程序，编程实现矩阵连乘问题public static void matrixChain(int p,int m,int s) int n=p.length-1; for(int i=1;i=n;i+) mii=0; for(int r=2;r=n
7、;r+) for(int i=1;in-r+1;i+) int j=i+r-1; mij=mi+1j+pi-1*pi*pj; sij=i; for(int k=i+1;kj;k+) int t=mik+mk+1j+pi-1*pk*pj; if(t0;xi!=yjmaxcij-1,ci-1j i,j0;xi!=yj4）创建一个java程序，编程实现最长公共子序列问题public static int lcsLength(char x,char y,int b) int m=x.length-1; int n=y.length-1; int c=new int m+1n+1; for(int i=
8、1;i=m;i+) ci0=0; for(int i=1;i=n;i+) c0i=0; for(int i=1;i=m;i+) for(int j=1;j=cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; return cmn;3.4实验报告把实验内容（1），（2）写到实验报告上。实验四 动态规划（二）4.1 实验目的1）掌握动态规划的概念，理解动态规划的思想2）掌握递归和递推这两种实现动态规划的实现方法3）正确分析动态规划的时空复杂度4.2 实验内容4.3 实验步骤4.4 实验报告实验五 贪心算法（一）5.1 实验目的1）掌握贪心算法的概念，理解
9、贪心算法的思想2）掌握贪心算法的应用范围，熟悉几种经典的贪心算法3）正确分析贪心算法的时空复杂度5.2 实验内容1）编程实现活动安排问题（有n个活动的集合E=1,2,n，其中，每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且sifi。如何安排这些活动，使得安排的活动场次最多）。2）编程实现哈夫曼编码。（选做）5.3 实验步骤1）验证活动安排问题拥有最优子结构2）选择贪心策略（按结束时间fi的非减序排列，每次选取时间结束最早的活动）3）用数学归纳法证明贪心算法能否得到整体最优解设E=1,2,n为所给的活动集合，由于E中活动按结束时间的非减序排列，故活动1具有最早的完成时间。首先证明活动安排问题有一个最优解以贪心选择开始，即该最优解中包含
