算法设计与分析实验.docx

实验一 递归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+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,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;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(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,x2,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;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=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）掌握贪心算法的概念，理解贪心算法的思想2）掌握贪心算法的应用范围，熟悉几种经典的贪心算法3）正确分析贪心算法的时空复杂度5.2 实验内容1）编程实现活动安排问题（有n个活动的集合E=1,2,n，其中，每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且si1，则设B=A-k1。由于f1=f1的最优解。反证，假设如能找到E的一个解B，它包含比A更多的活动，则将活动1加入B中将产生E的一个解B，它包含比A更多的活动，这与A的最优性矛盾。因此，每一步所做出的贪心选择都将问题简化为一个更小的与原问题具有相同形式的子问题。4）创建一个java程序，编程实现活动安排问题public static int greedySeletor(int s,int f,boolean a) int n=s.length-1; a1=true; int j=1; int count=1; for(int i=2;i=fj) ai=true; j=i; count+; else ai=false; return count