算法设计与分析实验

《算法设计与分析实验》由会员分享，可在线阅读，更多相关《算法设计与分析实验（9页珍藏版）》请在装配图网上搜索。

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

2、式Fn1nF n- 1 +F n-2 n0,114) 创建一个 java 程序，递归实现 Fibonacci 数列 public static int fibonacci(int n)if(n=1) return 1;return fibonacci（n-1）+fibonacci（n-2）; 5）分析并写出整数划分的递归公式1n = 1,m = 1q n, n n m 16）创建一个java程序，递归实现整数划分问题public static int q(int n,int m)if(n1)|(m1) return 0; if(n=1)|(m=1) return 1; if(nm) retur

3、n 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 binar

4、ySearch(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;

5、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的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少）

6、；2） 编程实现最长公共子序列问题（给定两个序列X=x1,x2xm和 Y=y1,y2,yn，找出X和 Y的最长公共子序列）；3）编程实现3个序列的最长公共子序列问题。（选做）3.3 实验步骤1）找出矩阵连乘问题中的状态转移方程设计算Ai:j,1=i=j=n，所需的最小数乘次数为mij,则原问题的最优值为m1n.动态转移方程：=j J0iminik; m i k +mk+1 j +pi-1pkpji2）创建一个java程序，编程实现矩阵连乘问题public static void matrixChain(int p,int m,int s)int n=p.length-1;for(int i=1

7、;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(t 0; xi = yjmax c i j 1 ,c i 1 j i,j 0; xi = yj4) 创建一个java程序，编程实现最长公共子序列问题 public static int lcsLength(char x,char y,int b) int m=x.length-1;int n=y.leng

8、th-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;elsecij=cij-1; bij=3;return cmn;3.4 实验报告把实验内容（1），（2）写到实验报告上。实验四 动态规划（二）4.1 实验目的1）掌握动态规划的概念，理解动态规划的思想2）掌握递归和递推这两种实现动态规划的实现方法3）正确分析动态规划的时空复杂度4.2 实验内容4.3实验步骤4.4 实验报

9、告实验五 贪心算法（一）5.1 实验目的1）掌握贪心算法的概念，理解贪心算法的思想2）掌握贪心算法的应用范围，熟悉几种经典的贪心算法3）正确分析贪心算法的时空复杂度5.2 实验内容1）编程实现活动安排问题（有n个活动的集合E=1,2,n，其中，每个活动都要求使用同 一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一 个要求使用该资源的起始时间si和一个结束时间fi，且si1, 则设B=A-kU1。由于f1=f1的最优解。反证， 假设如能找到E的一个解B,它包含比A更多的活动，则将活动1加入B中将产生E的一 个解B,它包含比A更多的活动，这与A的最优性矛盾。因此，每

10、一步所做出的贪心选择都 将问题简化为一个更小的与原问题具有相同形式的子问题。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+;elseai=false;return count;5.4 实验报告把实验内容(1)写到实验报告上。6.16.26.36.47.17.27.37.48.18.28.38.4实验六 贪心算法（二）实验目的实验内容实验步骤实验报告实验七 回溯法（一实验目的实验内容实验步骤实验报告实验八 回溯法（二）实验目的实验内容实验报告