算法分析与设计实验二：动态规划法

算法设计与分析中的动态规划动态规划是一种常用的算法设计与分析方法，它在解决各种实际问题时具有广泛的应用。

动态规划的基本思想是将问题划分为若干个子问题，通过求解子问题的最优解来得到原问题的最优解。

本文将介绍动态规划的基本概念、应用场景以及算法的设计与分析方法。

一、动态规划的基本概念动态规划有三个基本要素，即最优子结构、边界条件和状态转移方程。

最优子结构是指原问题的最优解可以通过求解子问题的最优解得到。

边界条件是指最小的子问题的解，也就是动态规划中的初始条件。

状态转移方程是指原问题与子问题之间的关系，通过状态转移方程可以将原问题的解与子问题的解联系起来。

二、动态规划的应用场景动态规划广泛应用于各个领域，比如图论、字符串处理、计算几何等。

在图论中，动态规划可以用来求解最短路径问题；在字符串处理中，动态规划可以用来求解最长公共子序列问题；在计算几何中，动态规划可以用来求解最大矩形面积问题。

除此之外，动态规划还可以用来解决一些组合优化问题，比如背包问题和旅行商问题。

三、动态规划的算法设计与分析方法动态规划的算法设计与分析方法通常包括以下几个步骤：定义状态、确定状态转移方程、初始化边界条件、计算状态值以及求解最优解。

在定义状态时，需要明确状态变量的含义，以及状态之间的关系。

确定状态转移方程是动态规划的核心步骤，需要根据实际问题来构造合适的状态转移方程。

初始化边界条件是指求解最小子问题的解，通常需要根据实际问题来确定。

计算状态值是指利用状态转移方程来逐步求解子问题的最优解。

最后，通过求解最优解来得到原问题的解。

四、动态规划的实例分析以背包问题为例，说明动态规划的实际应用。

假设有一个背包，它的容量为C。

现有n个物品，每个物品的重量为w[i]，价值为v[i]。

要求选取若干个物品放入背包中，使得背包所装物品的总价值最大。

这个问题可以通过动态规划来求解，具体步骤如下：1. 定义状态：dp[i][j]表示前i个物品放入容量为j的背包中所得到的最大价值。

算法设计与分析中的动态规划动态规划是一种常用的算法设计与分析技术，通常用于求解具有重叠子问题和最优子结构性质的问题。

它的核心思想是将原问题分解为更小的子问题，并通过递推关系式将子问题的解整合为原问题的解。

在算法设计与分析领域，动态规划广泛应用于优化问题、最短路径问题、序列比对问题等。

一、动态规划的基本特征动态规划算法的正确性基于两个重要的特征：重叠子问题和最优子结构。

1. 重叠子问题重叠子问题是指在求解原问题时，子问题之间存在相互重叠的情况。

也就是说，子问题之间不是独立的，它们具有一定的重复性。

动态规划算法利用这个特征，通过保存已经求解过的子问题的解，避免重复计算，提高算法的效率。

2. 最优子结构最优子结构是指问题的最优解可以通过子问题的最优解推导得到。

也就是说，原问题的最优解可以通过一系列子问题的最优解进行构造。

这个特征是动态规划算法能够求解最优化问题的关键。

二、动态规划的基本步骤1. 确定状态动态规划算法需要明确问题的状态，即问题需要用哪些参数来描述。

状态一般与原问题和子问题的解相关。

2. 定义状态转移方程状态转移方程描述原问题与子问题之间的关系。

通过递推关系式，将原问题分解为更小的子问题，并将子问题的解整合为原问题的解。

3. 初始化根据问题的实际需求，对初始状态进行设定，并计算出初始状态的值。

这一步骤是递推关系式的起点。

4. 递推计算根据状态转移方程，通过递推关系式计算出子问题的解，并将子问题的解整合为原问题的解。

这一步骤通常采用迭代的方式进行。

5. 求解目标问题通过递推计算得到原问题的解，即为最优解或者问题的答案。

三、动态规划的应用动态规划算法在实际问题中具有广泛的应用。

下面以两个经典问题为例，介绍动态规划在实际中的应用。

1. 背包问题背包问题是一种经典的优化问题，主要包括0/1背包问题和完全背包问题。

其核心思想是在限定的背包容量下，选择一些具有最大价值的物品放入背包中。

2. 最长公共子序列问题最长公共子序列问题是指给定两个序列，求解它们的最长公共子序列的长度。

算法分析与设计实验报告--动态规划《算法分析与设计》实验报告完成⽇期：20011.11.241、实验⽬的(1)掌握动态规划⽅法贪⼼算法思想(2)掌握最优⼦结构原理(3)了解动态规划⼀般问题2、实验内容(1)编写⼀个简单的程序，解决0-1背包问题。

设N=5，C=10，w={2，2，6，5，4},v={6,3,5,4,6}(2)合唱队形安排。

【问题描述】N位同学站成⼀排，⾳乐⽼师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。

合唱队形是指这样的⼀种队形：设K 位同学从左到右依次编号为1，2…，K，他们的⾝⾼分别为T1，T2，…，TK，则他们的⾝⾼满⾜T1<...Ti+1>…>TK(1<=i<=K)。

已知所有N位同学的⾝⾼，计算最少需要⼏位同学出列，可以使得剩下的同学排成合唱队形。

3、实验要求（1）写出源程序，并编译运⾏（2）详细记录程序调试及运⾏结果4、算法思想：利⽤动态规划的思想，解决诸如0—1背包问题，最⼤合唱队形问题等问题的最优解，能在最短的时间内，找到最好的解决⽅案的⼀种算法。

5、实验过程：1、0—1背包问题：源代码如下：#include#includeusing namespace std;#define N 5#define c 10int w[N+1]={0,2,2,6,5,4},v[N+1]={0,6,3,5,4,6};int m[N+1][c+1];int min(int x,int y){if(x<=y)return x;else return y;}int max(int x,int y){if(x>=y) return x;else return y;}void KnapSack(int v[],int w[]){int jMax=min(w[1],c);for (int j=1;j<=jMax;j++) //当0=m[1][j]=0;for (j=w[1];j<=c;j++) // 当j>=w[n]时, m(n,j)=v[n]m[1][j]=v[1];for (int i=2;i<=N;i++) //DP{ int jMax=min(w[i],c);for (j=1;jfor (j=jMax;j<=c;j++) //m(n,j)=v[n] 当j>=w[n] m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]); }}void main(){KnapSack(v,w);for(int i=1;i<=N;i++){for(int j=0;j<=c;j++)cout<cout<}}运⾏截图如下：合唱队形问题：代码如下：#include#includeusing namespace std;#define MAXN 200void main(){int n, a[MAXN], b[MAXN], c[MAXN], i, j, max,lab,pre[MAXN]; cout<<"输⼊数据个数："; cin>>n;cout<<"\n输⼊"<for (i = 1; i <= n; i++) //O(n)cin>> a[i];memset(b, 0, sizeof(a));memset(c, 0, sizeof(c));b[1] = 1;pre[i]=0; //i=1->nfor (i = 2; i <= n; i++){max = 0;for (j = i - 1; j >= 1; j--) {if (a[j]max) {max = b[j];pre[i]=j;}}b[i] = max + 1;}//lab:max所对应a数组元素下标O(n)max = b[1];for (i = 2; i <= n; i++){ if (b[i] > max){max = b[i];lab=i;}}cout<<"Longest Increasing Subsequence is："<i = lab;int num=max;j=max;while( num>0 ){c[j--]=a[i];i=pre[i];num--;}//输出数列O(n)for(i=1;i<=max;i++)cout<cout<}截图如下：6.实验过程分析本次实验做的是01背包和合唱队形，之前01背包也⽤贪⼼算法讨论过，但得不到最优解，这次实验⽤动态规划实现的，涉及到剪枝函数部分要考虑清楚，实验过程中通过画图，对理解有很⼤帮助；第⼆个实验其实是利⽤了两次LIS问题，再综合⼀下，总的来说，本次实验还是⽐较成功，对动态规划算法的思想理解得挺透彻的。

算法设计与分析实验21. 实验背景算法设计与分析是计算机科学中重要的研究方向，涉及到算法的设计、分析和实现。

本次实验旨在帮助学生进一步理解和掌握常见的算法设计与分析方法，通过实践操作加深对算法原理的理解。

2. 实验目的本次实验的主要目的如下：- 理解动态规划算法设计思想；- 学习并掌握动态规划算法的实现方法； - 熟悉动态规划算法的时间复杂度分析方法。

3. 实验内容本次实验的主要内容是实现一个动态规划算法，并分析它的时间复杂度。

3.1 动态规划算法介绍动态规划算法是一种将问题分解成子问题并逐个求解的方法。

它通过存储子问题的解来避免重复计算，从而提高算法的效率。

动态规划算法通常采用自底向上的方式来求解问题，即先求解小规模的子问题，再逐步扩大规模，直到解决原始问题。

3.2 实现一个动态规划算法在本次实验中，我们将实现一个动态规划算法来解决一个具体的问题。

具体步骤如下： 1. 确定子问题：将原问题分解为子问题； 2. 确定状态转移方程：定义一个状态转移方程，用于表示子问题与原问题之间的关系； 3. 确定边界条件：确定子问题的边界条件，即最简单的情况下的解； 4. 自底向上求解：根据状态转移方程和边界条件，逐步求解子问题，最终得到原问题的解。

3.3 时间复杂度分析完成动态规划算法的实现后，我们需要对算法的时间复杂度进行分析。

时间复杂度是衡量算法性能的重要指标，它反映了算法在处理输入规模增大时所需的时间。

在分析时间复杂度时，我们需要考虑算法的基本操作次数，并且基于不同输入规模的情况，推导出算法的大O表示法。

4. 实验结果完成实验后，我们得到了动态规划算法的实现代码，并对其进行了时间复杂度分析。

下面是实验结果的总结： - 实现了动态规划算法，并成功解决了一个具体的问题； - 分析了实现代码的时间复杂度，并得出了算法的大O表示法。

5. 总结与展望本次实验通过实现动态规划算法，深入了解了动态规划的设计与分析方法。

算法分析与设计课程设计动态规划一、课程目标知识目标：1. 理解动态规划的基本概念、原理和应用场景；2. 学会运用动态规划方法解决实际问题，如背包问题、最长公共子序列等；3. 掌握动态规划与其他算法（如贪心、分治等）的区别和联系；4. 了解动态规划在实际应用中的优化方法及策略。

技能目标：1. 能够运用动态规划思想分析和解决具体问题，提高编程实现能力；2. 培养逻辑思维能力和问题解决能力，通过案例分析和实践，掌握动态规划的核心技巧；3. 学会运用数学知识对动态规划问题进行建模和求解。

情感态度价值观目标：1. 培养学生对算法分析与设计的学习兴趣，激发学习动力；2. 培养学生的团队合作精神，学会与他人共同解决问题；3. 增强学生对我国在计算机科学领域取得成就的自豪感，培养创新意识和爱国情怀。

课程性质：本课程属于算法分析与设计领域，旨在帮助学生掌握动态规划的基本原理和方法，提高解决实际问题的能力。

学生特点：学生已具备一定的编程基础和算法知识，具有一定的逻辑思维能力和数学基础。

教学要求：注重理论与实践相结合，通过案例分析、实践操作和课后练习，使学生能够熟练掌握动态规划方法，并应用于实际问题解决。

同时，关注学生个体差异，因材施教，提高教学质量。

二、教学内容1. 动态规划基本概念：包括动态规划的定义、特点和应用场景，以及与分治、贪心算法的对比分析。

教材章节：第3章 动态规划基础2. 动态规划核心要素：状态、状态转移方程、边界条件和最优子结构。

教材章节：第3章 动态规划基础3. 典型动态规划问题：a. 背包问题：0-1背包、完全背包、多重背包等；b. 最长公共子序列、最长公共子串；c. 最短路径问题：Dijkstra算法、Floyd算法。

教材章节：第4章 动态规划典型问题4. 动态规划优化方法：记忆化搜索、自底向上与自顶向下、状态压缩等。

教材章节：第5章 动态规划优化方法5. 实际应用案例分析：介绍动态规划在计算机科学、运筹学等领域的应用案例，提高学生实际应用能力。

实验二最长公共子序列（动态规划算法）班级：08计算机科学与技术（1）班学号：E08620113 姓名：戴斌江机器号：实验二最长公共子序列问题一、实验目的：1、理解动态规划算法的概念；2、掌握动态规划算法的基本要素；3、掌握设计动态规划算法的步骤；4、通过应用范例学习动态规划算法的设计技巧与策略；二、实验内容及要求：1、使用动态规划算法解决最长公共子序列问题：给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

2、通过上机实验进行算法实现。

3、保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。

三、实验原理：动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程（decision process)最优化的数学方法。

20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。

1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。

算法总体思想：1)动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题,先求解子问题，然后从这些子问题的解得到原问题的解。

2)与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。

子问题中存在大量的公共子问题，在分治求解过程中被多次重复计算，保存计算结果，为后面的计算直接引用，减少重复计算次数这就是动态规划的基本思想。

3)用动态规划算法求解问题，可依据其递归式以自底向上的方式进行计算。

在计算过程中，保存已解决的子问题的答案。

每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量重复计算，最终得到多项式时间算法。

实验二动态规划算法一、实验目的与要求1、熟悉最长公共子序列问题的算法；2、初步掌握动态规划算法；二、实验题若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。

例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。

给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z 是序列X和Y的公共子序列。

给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

三．(1)实验源代码://最长公共子序问题://问题描述: 若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，//是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。

//例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。

//给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z 是序列X和Y的公共子序列。

//给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

#include<bits/stdc++.h>using namespace std;#define max 1000//注意：这里使用的char数组，可以按字符输出，若改为string类型，//执行printf("%c",A[m-1])就会报错;char A[100],B[100]; //输入的两个串a和b//这里定义全局变量可以不赋值0，因为全局变量自动赋值0;int c[max][max]; //记录最长公共子序的长度；int b[max][max]; //记录状态号;void LCS(int m,int n){if(m==0||n==0){return;else if(b[m][n]==1){LCS(m-1,n-1);printf("%c",A[m-1]);}else if(b[m][n]==2){m=m-1;LCS(m,n);}else if(b[m][n]==3){n=n-1;LCS(m,n);}}void LCS_length(int m,int n){for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(A[i-1]==B[j-1]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}else if(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}}{printf("请输入两个待测的字符串:\n");scanf("%s",&A);scanf("%s",&B);int m=strlen(A); //m为A串长度；int n=strlen(B); //n为B串长度;LCS_length(m,n);printf("其最长公共子序的长度为:%d\n",c[m][n]);printf("其最长公共子序为:");LCS(m,n);return 0;}(2)运行结果为:(3)算法思路:最长公共子序列的结构有如下表示：设序列X=<x1, x2, …, x m>和Y=<y1, y2, …, y n>的一个最长公共子序列Z=<z1, z2, …, z k>，则：1.若x m=y n，则z k=x m=y n且Z k-1是X m-1和Y n-1的最长公共子序列；2.若x m≠y n且z k≠x m ，则Z是X m-1和Y的最长公共子序列；3.若x m≠y n且z k≠y n，则Z是X和Y n-1的最长公共子序列。

《算法设计与分析》实验指导实验二动态规划应用日期：一、实验目的1．理解动态规划的基本思想,了解最优子结构性质和子问题的重叠性质。

2．熟练掌握典型的动态规划问题。

掌握动态规划思想分析问题的一般方法,对较简单的问题能正确分析,并设计出动态规划算法,并能够用程序实现。

二、实验要求1. 认真学习动态规划方法基本思想、方法步骤,练习利用动态规划法分析问题解决问题,加深动态规划类程序的理解。

2. 阅读经典问题的关键代码段,仔细领会动态规划算法的精要。

3.选定实验题目，仔细阅读实验要求，设计好输入输出，按照分治法的思想构思算法，选取合适的存储结构实现应用的操作。

4. 实验要有详细的测试记录，包括各种可能的测试数据。

三、实验内容1.调试验证选择经典问题TSP问题、最长公共子序列、0/1背包问题之一,完善算法,用C/C++以及Javascript语言编写程序并调试。

2.巩固提高针对其中经典问题之一，通过检索论文资料，类比研究等方法对其算法进行优化，并通过实验得方式对其进行验证比较,上机调试，最终形成一篇不少于2000字得小论文。

实验报告一、实验目的掌握动态规划算法时间空间复杂度分析，以及问题复杂性分析方法。

二、实验内容现有n种物品，对1<=i<=n，第i种物品的重量为正整数W，价值为正整数V，背包能承受的最大载重量为正整数C，现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过C且总价值最大。

三、实验环境操作系统、调试软件名称、版本号，上机地点，机器台号四、问题分析令V（i,j）表示在前i(1<=i<=n)个物品中能够装入容量为就j(1<=j<=C)的背包中的物品的最大价值，则可以得到如下的动态规划；（1）V（i,0）=V(0,j)=0（2）V(i,j)=V(i-1,j) j<Wi V(i,j)=max{V(i-1,j),V(i-1,j-Wi)+Vi} j>Wi(1)式表明：如果第i个物品的重量大于背包的容量，则装入前i个物品得到的最大价值和装入前i-1的物品得到的最大价值是相同的，即物品i不能装入背包；第（2）个式子表明：如果第i个物品的重量小于背包的容量则会有以下两种情况：（a）如果把第i个物品装入背包，则背包物品的价值等于第i-1个物品装入容量位j-wi的背包中的价值加上第i个物品的价值vi（b）如果第i个物品没有入背包，则背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。

实验内容：1、实现资源分配的动态规划算法。

2、实现矩阵连乘的动态规划算法3、实现最长公共子序列的动态规划算法4、实现电路布线的动态规划算法5、实现m=2的流水线作业调度动态规划算法。

（任选一个完成）实验二 动态规划实验目的1. 掌握动态规划的基本思想方法；2. 了解适用于用动态规划方法求解的问题类型，并能设计相应动态规划算法；3. 掌握动态规划算法复杂性分析方法。

预习与实验要求1. 预习实验指导书及教材的有关内容，掌握动态规划的基本思想；2. 严格按照实验内容进行实验，培养良好的算法设计和编程的习惯；3. 认真听讲，服从安排，独立思考并完成实验。

实验设备与器材硬件：PC 机软件：C++或Java 等编程环境实验原理将待求解问题分解为若干子问题，通过子问题的解得到原问题的解，这是问题求解的有效途径。

但是如何实施分解呢？分治策略的基本思想是将规模为n 的问题分解为k 个规模较小的子问题，各子问题相互独立但与原问题求解策略相同。

但并不是所有问题都可以这样处理。

问题分解的另一个途径是将求解过程分解为若干阶段（级），一次求解每个阶段即得到原问题的解。

通过分解得到的各子阶段不要求相互独立，但希望它们具有相同类型，而且前一阶段的输出可以作为下一阶段的输入。

这种策略特别适合求解具有某种最优性质的问题。

贪心法属于这类策略：对问题()n P ，其求解过程中各贪心选择步骤构成决策序列k D D D D ,,,21 =，i D 的最优性仅仅依赖于121,,,-i D D D 。

贪心法不保证最后求出解的最优性。

动态规划法也是一个分阶段判定决策过程，其问题求解策略的基础是决策过程的最优原理：为达到某问题的最优目标T ，需要一次作出决策序列k D D D D ,,,21 =。

如果D 是最优的，则对任意()k i i <≤1，决策子序列k i i D D D ,,,21 ++也是最优的，即当前决策的最优性取决于其后续决策序列是否最优。

实验报告2.2(递归法)学号：201208070103 姓名：陈明班级：智能1201第16 周课程名称算法设计与分析实验课时 2实验项目整数因子分解问题实验时间2015年1月10日实验目的对于给定的正整数n，计算n共有多少种不同的分解式。

实验环境Eclipse Luna, Java JDK1.7, Windows 8.1实验内容（算法、程序、步骤和方法）一、算法策略动态规划法。

把1~number的约数预先存起来，需要用得时候，直接在前面取得。

二、算法设计（步骤）1）把number的约数全部计算出来，存储在factor数组里面。

2）使用快速排序法QuickSort把factor按升序排序3）使用动态规划法。

把0~number的分解式的个数存在recordNum数组里面。

三、复杂度分析1）时间复杂度：首先时计算约数因子，其次是快速排序，最后是动态规划，这三步伟主要耗时。

故时间复杂T(n)=O(n)+O(n*log n)+O(k) (其中k为number 的约数个数，故为常数级别)。

故T(n)<O(n*log n)+ O(n*log n)=2 O(n*log n)故该算法的时间复杂度为 O(n*log n)2）空间复杂度：O(n)1）从控制台console输入数字，java封装类Scanner获得输入流；2）获得的数字，赋值给number数据记录和计算1）number=12时：2）number=11时：结论（结果）3）number=888888时：小结1）动态规划法相对于递归法来说，当输入规模很大时，应该考虑动态规划法；2）进行两个种方法的对比：Number=888888动态规划法：递归法：T(动态规划)=30毫秒，T(递归策略)=263毫秒显然，从耗时上来看，动态规划法要优于递归策略！指导老师评议成绩评定：指导教师签名：。

实验报告（ 2015/2016 学年第 2 学期）课程名称算法分析与设计实验名称动态规划法求解最长公共子序列实验时间2016 年 5 月24 日指导单位南京邮电大学计算机学院、软件学院指导教师陈xx学生姓名xx 班级学号xx学院(系) 计软院专业NIIT附件：#include<iostream>using namespace std;class LCS{public:LCS (int nx,int ny,char *x,char *y);void CLCS();void CLCSIM();int LCSLength();int LCSLengthIM();private:void CLCS(int i,int j);void CLCSIM(int i,int j);int **c,**s,**t,m,n;char *x,*y;};LCS::LCS(int nx,int ny,char *x,char *y){m=nx;n=ny;this->x=x;this->y=y;t=new int *[2];t[0]=new int [n+1];t[1]=new int [n+1];c=new int*[m+1];for(int i=0;i!=m+1; i++)c[i]=new int [n+1];s=new int*[m+1];for(i=0;i!=m+1; i++)s[i]=new int [n+1];}int LCS::LCSLength(){for (int i=1;i<=m;i++) c[i][0]=0;for (i=1;i<=n;i++) c[0][i]=0;for (i=1;i<=m;i++){for (int j=1;j<=n;j++){if (x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;s[i][j]=1;}else if (c[i-1][j]>=c[i][j-1]) {c[i][j]=c[i-1][j];s[i][j]=2;}else{c[i][j]=c[i][j-1];s[i][j]=3;}}}return c[m][n];}int LCS::LCSLengthIM(){for (int i=0;i<2;i++) t[i][0]=0;for (i=1;i<=n;i++) t[0][i]=0;for (i=1;i<=m;i++){for (int j=1;j<=n;j++){if (x[i]==y[j]){t[1][j]=t[0][j-1]+1;}else if (t[0][j]>=t[1][j-1]) {t[1][j]=t[0][j];}else{t[1][j]=t[1][j-1];}}for (j=1;j<=n;j++){t[0][j]=t[1][j];}}return t[1][n];}void LCS::CLCS(int i,int j){if (i==0||j==0) return ;if (s[i][j]==1){CLCS(i-1,j-1);cout<<x[i];}else if (s[i][j]==2) CLCS (i-1,j);else CLCS (i,j-1);}void LCS::CLCS(){CLCS(m,n);}void LCS::CLCSIM(int i,int j){if (i==0||j==0) return ;if (c[i][j]==c[i-1][j-1]+1){CLCS(i-1,j-1);cout<<x[i];}else if (c[i][j]=c[i-1][j]) CLCS (i-1,j);else CLCS (i,j-1);}void LCS::CLCSIM(){CLCSIM(m,n);}int main(){char x[8]={'0','a','b','c','b','d','a','b'}; char y[7]={'0','b','d','c','a','b','a'};cout<<"序列X:";for (int i=1;i<8;i++)cout<<x[i]<<" ";cout<<endl;cout<<"序列Y:";for (i=1;i<7;i++)cout<<y[i]<<" ";cout<<endl;LCS a(8,7,x,y);cout<<"最长公众子序列长度:"<<a.LCSLength()<<endl; cout<<"最长公众子序列:";a.CLCS();cout<<endl;return 0;}4。

《算法设计与分析》实验指导书计算机学院信息安全系毕方明本书是为配合《算法分析与设计实验教学大纲》而编写的上机指导，其目的是使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。

上机实验一般应包括以下几个步骤：（1）、准备好上机所需的程序。

手编程序应书写整齐，并经人工检查无误后才能上机。

（2）、上机输入和调试自己所编的程序。

一人一组，独立上机调试，上机时出现的问题，最好独立解决。

（3）、上机结束后，整理出实验报告。

实验报告应包括：题目、程序清单、运行结果、对运行情况所作的分析。

本书共分阶段4个实验，每个实验有基本题和提高题。

基本题必须完成，提高题根据自己实际情况进行取舍。

题目不限定如下题目，可根据自己兴趣爱好做一些与实验内容相关的其他题目，如动态规划法中的图象压缩，回溯法中的人机对弈等。

其具体要求和步骤如下：实验一分治与递归（4学时）一、实验目的与要求1、熟悉C/C++语言的集成开发环境；2、通过本实验加深对递归过程的理解二、实验内容：掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。

三、实验题任意输入一个整数，输出结果能够用递归方法实现整数的划分。

四、实验步骤1．理解算法思想和问题要求；2．编程实现题目要求；3．上机输入和调试自己所编的程序；4．验证分析实验结果；5．整理出实验报告。

一、实验目的与要求1、掌握棋盘覆盖问题的算法；2、初步掌握分治算法二、实验题：盘覆盖问题：在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。

在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

三、实验提示void chessBoard(int tr, int tc, int dr, int dc, int size){if (size == 1) return;int t = tile++, // L型骨牌号s = size/2; // 分割棋盘// 覆盖左上角子棋盘if (dr < tr + s && dc < tc + s)// 特殊方格在此棋盘中chessBoard(tr, tc, dr, dc, s);else {// 此棋盘中无特殊方格// 用t 号L型骨牌覆盖右下角board[tr + s - 1][tc + s - 1] = t;// 覆盖其余方格chessBoard(tr, tc, tr+s-1, tc+s-1, s);}// 覆盖右上角子棋盘if (dr < tr + s && dc >= tc + s)// 特殊方格在此棋盘中chessBoard(tr, tc+s, dr, dc, s);else {// 此棋盘中无特殊方格// 用t 号L型骨牌覆盖左下角board[tr + s - 1][tc + s] = t;// 覆盖其余方格chessBoard(tr, tc+s, tr+s-1, tc+s, s);}// 覆盖左下角子棋盘if (dr >= tr + s && dc < tc + s)// 特殊方格在此棋盘中chessBoard(tr+s, tc, dr, dc, s);else {// 用t 号L型骨牌覆盖右上角board[tr + s][tc + s - 1] = t;// 覆盖其余方格chessBoard(tr+s, tc, tr+s, tc+s-1, s);}// 覆盖右下角子棋盘if (dr >= tr + s && dc >= tc + s)// 特殊方格在此棋盘中chessBoard(tr+s, tc+s, dr, dc, s);else {// 用t 号L型骨牌覆盖左上角board[tr + s][tc + s] = t;// 覆盖其余方格chessBoard(tr+s, tc+s, tr+s, tc+s, s);}}一、实验目的与要求1、熟悉二分搜索算法；2、初步掌握分治算法；二、实验题1、设a[0:n-1]是一个已排好序的数组。

实验二、动态规划算法的应用班级：计072学号：**********姓名：***一、实验目的与实验内容1、掌握动态规划算法的基本设计思想与原则。

2、最长公共子序列、0-1背包，找零钱二、实验要求1．用C++/C完成算法设计和程序设计并上机调试通过。

2．撰写实验报告，提供实验结果和数据。

3．分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。

三、程序实现最长公共子序列：对字符串X和Y，首先构建子问题最有值的递归关系。

用c[i][j]记录序列X i和Y j的最长公共子序列的长度。

其中X i={x1,x2,…,x i};Y j={y1,y2,…,y j}.当i=0或j=0时，空序列就是X i和Y j的最长公共子序列。

故此时c[i][j]=0.其他情况下，由最优子结构性质可建立递归关系如下：0 i=0,j=0c[i][j]= c[i-1][j-1]+1 i,j>0;x i=y jmax{c[i][j-1],c[i-1][j]} i,j>0;x i=y j0-1背包问题：设所给0-1背包问题的子问题max∑n k=i v k x k∑n k=i v k x k<=jx k∈{0.1},i<=k<=n的最优值为m(i,j),即m(i,j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。

由0-1背包问题的最优子结构性质，可以建立计算m(i,j)的递归式如下：m(i,j)= max{m(i+1,j),m(i+1,j-w i)+v i} j>=w im(i+1,j) 0<=j<w iv n j>=w nm(n,j)= 0 0<=j<w n找零钱：在这次实验中，由于听错实验的最后一个题目，所以找零钱的这个实验我是完全参照0-1背包问题的。

时间复杂度：最长公共子序列：计算最优值c[i][j]的算法设计中，双层循环外规模为m，内规模为n，所以计算它的时间复杂度为0(mn).0-1背包与找零钱：由他的递归表达式可得时间复杂度为0(nc).四、心得体会通过此次实验，我的最深感触就是对算法的思想一定要理解，不然只是徒劳。

算法设计与分析实验报告算法设计与分析实验报告一、引言在计算机科学领域，算法设计与分析是非常重要的研究方向。

本次实验旨在通过实际案例，探讨算法设计与分析的方法和技巧，并验证其在实际问题中的应用效果。

二、问题描述本次实验的问题是求解一个整数序列中的最大子序列和。

给定一个长度为n的整数序列，我们需要找到一个连续的子序列，使得其和最大。

三、算法设计为了解决这个问题，我们设计了两种算法：暴力法和动态规划法。

1. 暴力法暴力法是一种朴素的解决方法。

它通过枚举所有可能的子序列，并计算它们的和，最终找到最大的子序列和。

然而，由于需要枚举所有子序列，该算法的时间复杂度为O(n^3)，在处理大规模数据时效率较低。

2. 动态规划法动态规划法是一种高效的解决方法。

它通过定义一个状态转移方程，利用已计算的结果来计算当前状态的值。

对于本问题，我们定义一个一维数组dp，其中dp[i]表示以第i个元素结尾的最大子序列和。

通过遍历整个序列，我们可以利用状态转移方程dp[i] = max(dp[i-1]+nums[i], nums[i])来计算dp数组的值。

最后，我们返回dp数组中的最大值即为所求的最大子序列和。

该算法的时间复杂度为O(n)，效率较高。

四、实验结果与分析我们使用Python编程语言实现了以上两种算法，并在相同的测试数据集上进行了实验。

1. 实验设置我们随机生成了1000个整数作为测试数据集，其中包含正数、负数和零。

为了验证算法的正确性，我们手动计算了测试数据集中的最大子序列和。

2. 实验结果通过对比实验结果，我们发现两种算法得到的最大子序列和是一致的，验证了算法的正确性。

同时，我们还对两种算法的运行时间进行了比较。

结果显示，暴力法的运行时间明显长于动态规划法，进一步证明了动态规划法的高效性。

五、实验总结通过本次实验，我们深入了解了算法设计与分析的方法和技巧，并通过实际案例验证了其在解决实际问题中的应用效果。

我们发现，合理选择算法设计方法可以提高算法的效率，从而更好地解决实际问题。