华北水利水电学院算法分析与设计实验报告
20010～2011学年第二学期2008级计算机科学与技术专业
班级：2008109 学号：200810906 姓名：刘景超
实验一递归与分治算法的设计与实现
一、实验目的：
1、了解递归、分治算法的设计思路与设计技巧，理解递归的概念，掌握设计有效算法的
分治策略。
2、通过实际案例，领会算法的执行效率
二、试验内容：
棋盘覆盖、最接近点对、排序算法、矩阵乘法等，（也可选作其它问题）；
三、核心程序源代码：
#include
#include
void main()
{
void hanoi(int n,char one,char two,char three);
int m;
cout<<"请输入要移动的盘子的数目:"< cin>>m; cout<<"盘子的数目为:"< hanoi(m,'A','B','C'); } void hanoi(int n,char one,char two,char three) { void move(char x,char y); if(n==1) move(one,three); else { hanoi(n-1,one,three,two); move(one,three); hanoi(n-1,two,one,three); } } void move(char x,char y) { cout< } 四、试验结果： 五、小结 本想用MFC采用图形的方式展示移动的过程，可惜水平有限，实在是写不出来，只好采用控制台程序了。采用控制台程序表述还是很简单的，算法也不复杂。这次实验让我认识到我在MFC方面基础还很薄弱，还需要多多练习，慢慢提升自己。 编译原理实验报告 实验名称 _____________ 消除文法的左递归__________________________ 实验时间 _____________________________________________ 院系 _________________________________________ 班级 ______________________________________________ 学号 ____________________________________________ 姓名 1. 试验目的 ?掌握和理解消除左递归(包括直接左递归和间接左递归)在构建 LL(1)文法的作用和目的 ?掌握消除左递归(包括直接左递归和间接左递归)的方法和步骤。 ?写出对于输入任意的上下文无关文法可以输出消除了左递归的等 价文法。 2. 实验原理 ?直接左递归的消除 消除产生式中的直接左递归是比较容易的。例如假设非终结符 P的规则为 P—P a/ B 其中，B是不以P开头的符号串。那么，我们可以把P的规则改写为 如下的非直接左递归形式：P—尸’ P'—P'￡ 考虑更一般的情况，假定关于非终结符P的规则为 P—P a / P o2 / …/ P a n / [31 / [32 / …/ p m 其中，a (I = 1, 2,…，n)都不为￡而每个p j (j = 1, 2,…，m) 都不以P开头，将上述规则改写为如下形式即可消除P的直接左递归： P— p l P'/ 32 P'/…/p m P' P' — 01P' / a P'/…/ a n P'/￡ 算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include printf("\n"); for(i=0;i 《现代设计理论与方法》实验报告 、实验目的 机械优化设计是一门实践性较强的课程，学生通过实际上机计算可以达到以 下目的： 1. 加深对机械优化设计方法的基本理论和算法步骤的理解; 2. 培养学生独立编制或调试计算机程序的能力； 3. 掌握常用优化方法程序的使用方法； 4 .培养学生灵活运用优化设计方法解决工程实际问题的能力。 、实验项目、学时分配及对每个实验项目的要求 1.明确黄金分割法基本原理、计算步骤及程序框图; 吐 入「土 2?编制或调试黄金分割法应用程序； 1 黄金分割法 2 八' " 3 ?用测试题对所编程序进行测试； 4?撰写实验报告。 1.明确复合形法基本原理、计算步骤及程序框图 等； 2 复合形法 4 2?编制或调试复合形法应用程序； 3 ?用测试题对所编程序进行测试； 4?撰写实验报告。 二、测试题 1. 黄金分割法程序测试题 1 )rn"何二?-10r+36,取坷=0 ,卜皿1, 沪 程序如下: #in clude #define tt 0.01 float function(float x) float y=pow(x,2)-10*x+36;// return(y); void finding(float a[3],float f[3]) float t=tt,a1,f1,ia; int i; f[0]=function(a[0]); for(i=0;;i++) a[1]=a[0]+t;f[1]=function(a[1]); if(f[1] 实验报告分治与递归 中国矿业大学计算机科学与技术学院孟靖宇 一、实验目的与要求 1、熟悉C/C++语言的集成开发环境； 2、通过本实验加深对递归过程的理解 二、实验内容： 掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。 三、实验题 任意输入一个整数，输出结果能够用递归方法实现整数的划分。 四、算法思想 对于数据n,递归计算最大加数等于x 的划分个数+最大加数不大于x-1的划分个数。最大加数x 从n 开始，逐步变小为n-1, (1) 考虑增加一个自变量：对于数据n,最大加数n1不大于m 的划分个数记作),(m n q 。则有： ???????>>=<==-+--+=1 1,1),()1,()1,(1),(1),(m n m n m n m n m m n q m n q n n q n n q m n q 五、代码实现 #include "stdafx.h" #include return 0; } int q(intn,int m){ if((n<1)||(m<1)) return 0; if((n==1)||(m==1)) return 1; if(n 递归与分治实验报告 班级：计科1102 姓名：赵春晓学号：2011310200631 实验目的：进一步掌握递归与分治算法的设计思想，通过实际问题来应用递归与分治设计算法。 实际问题：1集合划分问题，2输油管道问题，3邮局选址问题，4整数因子分解问题，5众数问题。 问题1：集合划分 算法思想：对于n个元素的集合，可以划分为由m个子集构成的集合，例如{{1,2}{3,4}}就是由2个子集构成的非空子集。假设f（n，m）表示将n个元素划分成由m个子集构成的集合的个数。那么1）若m == 1 ，则f（n，m）= 1 ；2）若n == m ，则f（n，m）= 1 ；3）若不是上面两种情况则有下面两种情况构成：3.1）向n-1个元素划分成的m个集合里面添加一个新的元素，则有m*f(n-1,m)种方法；3.2）向n-1个元素划分成的m-1个集合里添加一个由一个元素形成的独立的集合，则有f(n-1,m-1)种方法。 实验代码： #include 《数据结构与算法设计》 实验报告 ——实验一 学院： 班级： 学号： 姓名： 一、实验目的 1.通过实验实践、巩固线性表的相关操作； 2.熟悉VC环境，加强编程、调试的练习； 3.用C语言编写函数，实现循环链表的建立、插入、删除、取数据等基本操作； 4.理论知识与实际问题相结合，利用上述基本操作实现约瑟夫环。 二、实验内容 1、采用单向环表实现约瑟夫环。 请按以下要求编程实现： ①从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的 结点编号依次为1，2，……，m。 ②从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到 第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点 的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出 了这个环表的全部结点为止。 三、程序设计 1、概要设计 为实现上述程序功能，应用单向环表寄存编号，为此需要建立一个抽象数据类型：单向环表。 （1）、单向环表的抽象数据类型定义为： ADT Joseph{ 数据对象：D={ai|ai∈ElemSet,i=1,2,3……,n,n≥0} 数据关系：R1={ 课程名称：机电产品现代设计方法上课时间：2015年春季 机电产品现代设计方法实验报告 姓名： 学号： 班级： 所在学院：机电工程学院 任课教师：张旭堂 一、实验项目与实验目的 实验项目: 典型机电产品多学科协同优化设计。 试验目的： (1) 掌握典型机电产品多学科协同优化设计软件环境组成，包括建模软件、分析软件、协同平台。 (2）自主设计产品模型、分析过程、优化目标。 (3) 对得到的优化结果进行定性分析，解释结果的合理性，编写上机实验报告。 二、实验环境 网络协同设计环境，如下图所示：包括产品CAD建模、有限元分析FEM、动力学仿真ADAMS和控制仿真MATLAB。计算机网络硬件环境和相应软件环境。图形工作站和路由器，安装协同设计仿真软件。 型 协同设计仿真平台组成 三、实验原理 典型机电产品协同设计仿真工作流程如下图所示。 1）利用CAD建模工具，建立产品模型； 2）利用ADAMS建立产品运动学模型； 3）根据CAD和ADAMS传过来的结构模型和边界条件分析零件应力场和应变场； 4）用ADAMS分析得到的运动参数（位移、速度）。 协同设计仿真平台组成 四、实验内容与步骤 （1）总体方案设计 SysML语言是UML语言(Unified Modeling Language，统一建模语言，一种面向对象的标准建模语言，用于软件系统的可视化建模)在系统工程应用领域的延续和扩展，是近年提出的用于系统体系结构设计的多用途建模语言，用于对由软硬件、数据和人综合而成的复杂系统的集成体系结构进行可视化的说明、分析、设计及校验。 在这里我们绘制参数图如下。在下面的参数图中，我们确定了系统中各部件的相互约束情况。 本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼110 专业班级：物联网1601 学号：2016002105 学生姓名：俞梦真 指导教师：郝晓丽 2018年05月04 日 实验一递归与分治算法 1.1 实验目的与要求 1．进一步熟悉C/C++语言的集成开发环境； 2．通过本实验加深对递归与分治策略的理解和运用。 1.2 实验课时 2学时 1.3 实验原理 分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。 需要注意的是，分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。 1.4 实验题目 1．上机题目：格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。 对于给定的正整数n，格雷码为满足如下条件的一个编码序列。 （1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。 （2）序列中无相同的编码。 （3）序列中位置相邻的两个编码恰有一位不同。 2．设计思想： 根据格雷码的性质，找到他的规律，可发现，1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。 3．代码设计： 共享知识分享快乐 编译原理实验报告 实验名称消除文法左递归 实验时间2014年12月12日 院系软件工程 ______________ 班级软件工程（2）班 学号E01214215 __________ 姓名刘翼________________ 实验目的： 输入：任意的上下文无关文法。输出：消除了左递归的等价文法。 实验原理： 1．直接左递归的消除 消除产生式中的直接左递归是比较容易的。例如假设非终结符P 的规则为 P—P a / B 其中，B是不以P开头的符号串。那么，我们可以把P的规则改写为如下的非直接左递归形式：P —B P' P'—a P' / ￡ 这两条规则和原来的规则是等价的，即两种形式从P推出的符号串是相同的。 设有简单表达式文法G[E] ： E —E+T/ T T —T*F/ F F —（E）/ I 经消除直接左递归后得到如下文法： E —TE' E ' —+TE' / ￡ T —FT' T' —*FT' / ￡ F —（E）/ I 考虑更一般的情况，假定关于非终结符P的规则为 P—P a 1 / P a 2 / …/ P a n / B 1 / B 2 / …/ B m 其中，a i （I = 1，2，…，n）都不为￡，而每个B j （j = 1，2，…，m都不以P开头，将上述规则改写为如下形式即可消除P的直接左递归： P—B 1 P' / B 2 P' / …/ B m P' P' —a 1P' / a 2 P' / …/ a n P' / ￡ 2．间接左递归的消除 直接左递归见诸于表面，利用以上的方法可以很容易将其消除，即把直接左递归改写成直接右递归。然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。有些文法虽然表面上不存在左递归，但却隐藏着左递归。例如，设有文法G[S] ： S—Qc/ c Q—Rb/ b R—Sa/ a 虽不具有左递归，但S、Q R都是左递归的，因为经过若干次推导有 S Qc Rbc Sabc Q Rb Sab Qcab R Sa Qca Rbca 算法设计与分析实验报告 学院：信息学院 专业：物联网1101 姓名：黄振亮 学号：20113379 2013年11月 目录 作业1 0-1背包问题的动态规划算法 (7) 1.1算法应用背景 (3) 1.2算法原理 (3) 1.3算法描述 (4) 1.4程序实现及程序截图 (4) 1.4.1程序源码 (4) 1.4.2程序截图 (5) 1.5学习或程序调试心得 (6) 作业2 0-1背包问题的回溯算法 (7) 2.1算法应用背景 (3) 2.2算法原理 (3) 2.3算法描述 (4) 2.4程序实现及程序截图 (4) 2.4.1程序源码 (4) 2.4.2程序截图 (5) 2.5学习或程序调试心得 (6) 作业3循环赛日程表的分治算法 (7) 3.1算法应用背景 (3) 3.2算法原理 (3) 3.3算法描述 (4) 3.4程序实现及程序截图 (4) 3.4.1程序源码 (4) 3.4.2程序截图 (5) 3.5学习或程序调试心得 (6) 作业4活动安排的贪心算法 (7) 4.1算法应用背景 (3) 4.2算法原理 (3) 4.3算法描述 (4) 4.4程序实现及程序截图 (4) 4.4.1程序源码 (4) 4.4.2程序截图 (5) 4.5学习或程序调试心得 (6) 作业1 0-1背包问题的动态规划算法 1.1算法应用背景 从计算复杂性来看,背包问题是一个NP难解问题。半个世纪以来,该问题一直是算法与复杂性研究的热点之一。另外,背包问题在信息加密、预算控制、项目选择、材料切割、货物装载、网络信息安全等应用中具有重要的价值。如果能够解决这个问题那么则具有很高的经济价值和决策价值，在上述领域可以获得最大的价值。本文从动态规划角度给出一种解决背包问题的算法。 1.2算法原理 1.2.1、问题描述： 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi ∈{0,1}, ?∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。 1.2.2、最优性原理： 设(y1,y2,…,yn)是 (3.4.1)的一个最优解.则(y2,…,yn)是下面相应子问题的一个最优解: 证明:使用反证法。若不然,设(z2,z3,…,zn)是上述子问题的一个最优解,而(y2,y3,…,yn)不是它的最优解。显然有 ∑vizi > ∑viyi (i=2,…,n) 且 w1y1+ ∑wizi<= c 因此 v1y1+ ∑vizi (i=2,…,n) > ∑ viyi, (i=1,…,n) 说明(y1,z2, z3,…,zn)是(3.4.1)0-1背包问题的一个更优解,导出(y1,y2,…,yn)不是背包问题的最优解,矛盾。 1.2.3、递推关系： 课程名称：机电产品现代设计方法 上课时间：2014年春季 机电产品现代设计方法实验报告 姓名： 学号： 班级： 所在学院：机电工程学院 任课教师：金天国张旭堂 实验名称机电产品现代设计方法 姓名学号班级 实验地点实验日期评分 指导教师张旭堂同组成员其他 1 静态存储器扩展实验 1.1 实验目的 （1）掌握典型机电产品多学科协同优化设计软件环境组成，包括建模软件、分析软件、协同平台； （2）自主设计产品模型、分析过程、优化目标； （3）对得到的优化结果进行定性分析，解释结果的合理性，编写上机实验报告。 1.2 实验内容 (1) 轴的有限元分析 (2) 基于Adams的运动学分析与仿真 1.3实验相关情况介绍（包含使用软件或实验设备等情况） 1.3.1使用软件 本实验使用软件为Adams及abaqus，利用Adams进行运动学仿真分析，利用abaqus进行有限元分析。 1.3.2实验设备 计算机。 1.4实验结果 1.4.1基于ADAMS 的运动学仿真 （1）构造ADAMS样机机械模型 根据指导书建立铲车的三维模型。三维模型可以通过专门三维建模软件进行建模，然后导入ADAMS，也可以直接用ADAMS建模。利用ADAMS建模过程在《adams 运动仿真例子》中有详述，直接给出建模后的模型，如图1所示： 图1 铲车模型 （2）构建约束 根据要求构造四个约束：基座和座架之间的创建转动副，轴肩与座架间构建转动副，铲斗与悬臂间构建转动副，悬臂与轴肩之间构建平动副。构建后的模型如图2所示： 图2 添加约束铲车模型 （3）添加运动 根据题意分别对四个运动副添加运动函数： （a）基座和座架之间的创建转动副：360d*time； 集美大学计算机工程学院实验报告 课程名称：编译原理 指导教师：付永钢 实验成绩： 实验编号： 实验二 实验名称：递归下降分析程序构造 班级：计算12 姓名： 学号： 上机实践日期：2014.11 上机实践时间： 4学时 一、实验目的 通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握常用的语法分析方法。通过本实验，应达到以下目标： (1) 掌握从源程序文件中读取有效字符的方法和产生源程序内部表示文件的方法； (2)掌握语法分析的实现方法； (3)上机调试编出的语法分析程序。 二、实验环境 Windows7 x64、VC6.0 三、实验原理 递归下降法是语法分析中最易懂的一种方法。它的主要原理是，对每个非终结符按其产生式结构构造相应语法分析子程序，其中终结符产生匹配命令，而非终结符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的。 递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。 自上向下分析过程中，如果带回溯，则分析过程是穷举所有可能的推导，看是否能推导出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术，可根据输入串的当前符号以及各产生式右部首符，选择某非终结符的产生式，效率高，且不易出错。 无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。即：假设A 的全部产生式为A →α1|α2|……|αn ，则必须满足如下条件才能保证可以唯一的选择合适的产生式 First(A →αi )∩First (A →αj )=Φ,当i≠j. 无左递归：既没有直接左递归，也没有间接左递归。 无回溯：对于人以非中介符号U 的产生式右部n x x x |...||21，其对应的字的首终结符号两两不相交。 如果一个文法不含回路（形如P P +?的推导），也不含以ε为右部的产生式，那么可以通过执行消除左递归的算法消除文法的一切左递归。 四、实验内容 完成以下描述算术表达式的LL(1)文法的递归下降分析程序构造 G[E]: E →TE ′ E ′→+TE ′|ε T →FT ′ 银行家算法设计实验报告 银行家算法设计实验报告 一．题目分析 1.银行家算法： 我们可以把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求资源相当于客户向银行家贷款。操作系统按银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程尚需求的资源量，若是系统现存的资源可以满足它尚需求的资源量，则按当前的申请量来分配资源，否则就推迟分配。 当进程在执行中继续申请资源时，先测试该进程申请的资源量是否超过了它尚需的资源量。若超过则拒绝分配，若没有超过则再测试系统尚存的资源是否满足该进程尚需的资源量，若满足即可按当前的申请量来分配，若不满足亦推迟分配。 2.基本要求： （1）可以输入某系统的资源以及T0时刻进程对资源的占用及需求情况的表项，以及T0时刻系统的可利用资源数。 （2）对T0时刻的进行安全性检测，即检测在T0时刻该状态是否安全。 （3）进程申请资源，用银行家算法对其进行检测，分为以下三种情况： A. 所申请的资源大于其所需资源，提示分配不合理不予分配并返回 B. 所申请的资源未大于其所需资源， 但大于系统此时的可利用资源，提 示分配不合理不予分配并返回。 C. 所申请的资源未大于其所需资源， 亦未大于系统此时的可利用资源，预 分配并进行安全性检查： a. 预分配后系统是安全的，将该进 程所申请的资源予以实际分配并 打印后返回。 b. 与分配后系统进入不安全状态，提示系统不安全并返回。 （4）对输入进行检查，即若输入不符合条件，应当报错并返回重新输入。 3.目的： 根据设计题目的要求，充分地分析和理解题 目，叙述系统的要求，明确程序要求实现的功能以及限制条件。 明白自己需要用代码实现的功能，清楚编写每部分代码的目的，做到有的放矢，有条理不遗漏的用代码实现银行家算法。 《现代机械设计方法学》实验报告 班级： 学号： 姓名： 成绩： 实验一、有限元分析 （一）目的： 1、初步掌握有限元软件分析力学问题的过程，包括几何建模、网格划分等前处理功能，掌握各种计算结果的阅读。 2、掌握材料数据、载荷、约束的添加方法。 （二）要求：学生独立完成一个算例的有限元分析，并阅读其计算结果，提交一个算例的分析报告。 （三）计算实例 1、问题的描述 为了考察铆钉在冲压时，发生多大的变形，对铆钉进行分析。 铆钉圆柱高：10mm 铆钉圆柱外径：6mm 铆钉下端球径：15mm 弹性模量：2.06E11 泊松比：0.3 铆钉材料的应力应变关系如下： 应变0.003 0.005 0.007 0.009 0.011 0.02 0.2 618 1128 1317 1466 1510 1600 1610 应力 /Mpa 1、有限元模型。 3、应力云图，可选主应力或σx、σy、τxy、V on Mises应力、Tresca应力之一输出结果图片，指明你所选的应力的最大值及其位置。 （三）思考题： 1、如果要提高边界处计算精度，一般应如何处理？ 答：在边界处划分网格 2、有限元网格划分时应注意哪些问题？ 答：选取的时候要将编号显示出来，这样就可以更好的选择，网格尽可能的小，这样结果就越准确。 实验二、优化实验 （一）目的： 初步掌握利用ANSYS软件或MATLAB软件对问题进行分析。 （二）要求： 学生独立完成一个算例的分析，并给出算例的计算结果。。 （三）算例 1.实际问题 梁的形状优化，优化目的是使梁的体积最小，同时要求梁上的最大应力不 超过30000psi，梁的最大挠度不大于0.5in,沿长度方向梁的厚度可以变化，但梁端头的厚度为定值t，采用对称建模。 使用两种方法进行优化，两种方法优化结果。 子问题近视法目标ANSYS 百分比（TVOL）体积in3 3.60 3.62 1.004 （DEFL）挠度max in 0.500 0.499 0.998 (STRS)应力max,psi 30000 29740 0.991 第一阶法目标ANSYS 百分比（TVOL）体积in3 3.6 3.61 1.003 （DEFL）挠度max in 0.5 0.5 1.001 STRS)应力max,psi 30000 29768 0.992 实验报告 （2009/2010学年第一学期） 课程名称算法分析与设计A 实验名称动态规划法 实验时间2009 年11 月20 日指导单位计算机学院软件工程系 指导教师张怡婷 学生姓名丁力琪班级学号B07030907 学院(系) 计算机学院专业软件工程 实验报告 实验名称动态规划法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20一、实验目的和任务 目的：加深对动态规划法的算法原理及实现过程的理解，学习用动态规划法解决实际应用中的最长公共子序列问题。 任务：用动态规划法实现求两序列的最长公共子序列，其比较结果可用于基因比较、文章比较等多个领域。 要求：掌握动态规划法的思想，及动态规划法在实际中的应用；分析最长公共子序列的问题特征，选择算法策略并设计具体算法，编程实现两输入序列的比较，并输出它们的最长公共子序列。 二、实验环境(实验设备) 硬件：计算机 软件：Visual C++ 三、实验原理及内容（包括操作过程、结果分析等） 1、最长公共子序列（LCS）问题是：给定两个字符序列X={x1,x2,……,x m}和Y={y1,y2,……,y n}，要求找出X和Y的一个最长公共子序列。 例如：X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。 通过“穷举法”列出所有X的所有子序列，检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法，求解时间为指数级别的，因此不可取。 2、分析LCS问题特征可知，如果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且x m≠z k，则Z是X m-1和Y的最长公共子序列； （3）若x m≠y n且z k≠y n，则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题，分解为求解较小规模的问题： 若x m=y m，则进一步分解为求解两个（前缀）子字符序列X m-1和Y n-1的最长公共子序列问题； 如果x m≠y n，则原问题转化为求解两个子问题，即找出X m-1和Y的最长公共子序列与找出X 和Y n-1的最长公共子序列，取两者中较长者作为X和Y的最长公共子序列。 由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，具有最优子结构性质。 3、令c[i][j]保存字符序列X i={x1,x2,……,x i}和Y j={y1,y2,……,y j}的最长公共子序列的长度，由上述分析可得如下递推式： 0 i=0或j=0 c[i][j]= c[i-1][j-1]+1 i,j>0且x i=y j max{c[i][j-1],c[i-1][j]} i,j>0且x i≠y j 由此可见，最长公共子序列的求解具有重叠子问题性质，如果采用递归算法实现，会得到一个指数时间算法，因此需要采用动态规划法自底向上求解，并保存子问题的解，这样可以避免重复计算子问题，在多项式时间内完成计算。 4、为了能由最优解值进一步得到最优解（即最长公共子序列），还需要一个二维数组s[][]，数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。 物体运动的方式实验报告 （文章一）：实验报告四年级4课.小吊车活动1：做小吊车（分组实验）制作目的：做小吊车并研究小吊车原理制作材料及工具：小纸盒吊车臂吊臂支架线绳两个铁丝钩一个剪刀锥子胶水钩码制作过程： 1.小组分工合作 2.观察小吊车模型组装各部分①四个点要对称，固定牢固；②绳子要从前往后穿，不要穿反了； 3.调试小吊车分别拉动两根线,看看小吊车的臂能否灵活运动. 实验现象:小吊车能提起或放下钩码实验结论：放松上牵引绳，拉紧下牵引绳，吊臂向下运动；拉紧上牵引绳，放松下牵引绳，吊臂向上运动。活动2:收与放实验目的：推断动物与人的肢体运动原理(分组实验) 实验过程： 1. 弯曲手臂，感受上臂上下肌肉的长短松紧变化。 2.伸直手臂，感受上臂上下肌肉的长短松紧变化。 3.反复几次体会与小吊车的原理的联系。实验现象：手臂骨骼就像小吊车的吊臂，肌肉就像绳子，手臂运动时，当肱二头肌收缩,肱三头肌舒张时,肱二头肌牵动前臂向内收缩;当肱三头肌收缩,肱二头肌舒张时,肱三头肌牵动前臂向外伸展. 实验结论：前臂收缩类似小吊车抬起重物。前臂伸展类似小吊车放下重物。6课.做沙盘（分组实验）制作目的:通过制作校园沙盘模型培养学生的设计制作能力。制作材 料:硬纸板学校平面图橡皮泥潮湿的沙土废旧泡沫包装纸小木棍颜料盒剪刀制作步骤：对校园建筑的布局进行观测2．用大的硬纸板做底座。在纸板上画好学校平面图。(明确建筑物.树木等的位置) 3.用橡皮泥旧泡沫等材料做出立体的楼房等校园建筑物，根据平面图摆放好位置。（可以用长方体或正方体的泡沫做楼房，硬纸板做围墙，小木棍做旗杆等）。4．要注意建筑物的比例。（四年级的学生还不能很精确地计算出比例尺，教师适当指导。）8课.快与慢实验目的:研究小车运动的快慢(分组实验) 实验材料:秒表（或电子手表）、长尺、玩具车（学生自带），橡皮泥，马达、电池等（学生自带）实验过程: 1.小组做好分工：赛车手、计时员、测量员、记录员。 2.找好起点（必要时确定好终点）； 3.秒表做好归零； 4.在相同时间内必须进行多次测量（不少于3次），并做好记录 5. .在相同距离内必须进行多次测量（不少于3次），并做好记录实验结论：1：相同时间内经过的距离越长,物体运动的速度越快2：相同距离下所用的时间越短,物体运动的速度越快活动2:玩小车实验目的：研究小车运动的快慢与载重物及路面光滑程度是否有关？(对比试验) 实验材料:秒表（或电子手表）, 木板, 玩具车（学生自带），钩码, 毛巾. 实验方法：1做好小组分工:赛车手、计时员、记录员; 2先测量空车时小车在木板上运动时间; 3别的条件不变,向小车上加钩 《算法设计与分析》实验报告 分治策略 姓名：XXX 专业班级：XXX 学号：XXX 指导教师：XXX 完成日期：XXX 一、试验名称：分治策略 （1）写出源程序，并编译运行 （2）详细记录程序调试及运行结果 二、实验目的 (1)了解分治策略算法思想 (2)掌握快速排序、归并排序算法 (3)了解其他分治问题典型算法 三、实验内容 (1)编写一个简单的程序，实现归并排序。 (2)编写一段程序，实现快速排序。 (3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现 要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天 四、算法思想分析 (1)编写一个简单的程序，实现归并排序。 将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行 排序，最终将排好序的子集合合并成为所要求的排好序的集合。 (2)编写一段程序，实现快速排序。 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有 数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数 据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据 变成有序序列。 (3)编写程序实现循环日赛表。 按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通 过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割， 直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让 这2个选手进行比赛就可以了。 五、算法源代码及用户程序 (1)编写一个简单的程序，实现归并排序。 #include 院系：计算机科学学院 专业、年级： 07计科2大班 课程名称：编译原理 学号姓名： 指导教师： 2010 年11月17 日 组员学号姓名 实验 名称 实验一：词法分析实验室9205 实验目的或要求 通过设计一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。 具体要求：输入为某语言源代码，达到以下功能： 程序输入/输出示例：如源程序为C语言。输入如下一段： main() { int a,b; a=10; b=a+20; } 要求输出如下（并以文件形式输出或以界面的形式输出以下结果）。 （2，”main”） （5，”（“） （5，”）“） （5，”{“} （1，”int”） （2，”a”） （5，”,”） （2，”b”） （5，”;”） （2，”a”） （4，”=”） （3，”10”） （5，”;”） （2，”b”） （4，”=”） （2，”a”） （4，”+”） （3，”20”） （5，”;”） （5，”}“） 要求： 识别保留字：if、int、for、while、do、return、break、continue等等，单词种别码为1。 其他的标识符，单词种别码为2。常数为无符号数，单词种别码为3。 运算符包括：+、-、*、/、=、>、<等；可以考虑更复杂情况>=、<=、!= ；单词种别码为4。分隔符包括：“，”“；”“（”“）”“{”“}”等等，单词种别码为5。 算法与分析实验报告软件工程专业 安徽工业大学 指导老师：许精明 实验内容 1：杨辉三角 2：背包问题 3：汉诺塔问题 一：实验目的 1：掌握动态规划算法的基本思想，学会用其解决实际问题。 2：通过几个基本的实验，提高算法分析与设计能力，提高动手操作能力和培养良好的编程习惯。 二：实验内容 1：杨辉三角 2：背包问题 3：汉诺塔问题 实验一：杨辉三角 问题分析： ①每行数字左右对称，由1开始逐渐变大，然后变小，回到1。 ②第n行数之和为2^n。 ③下一行每个数字等于上一行的左右两个数字之和。 算法设计及相关源代码： public void yanghui(int n) { int[] a = new int[n]; if(n==1){ System.out.println(1); }else if(n==2) { System.out.print(1 + " " +1); }else{ a[1]=1; System.out.println(a[1]); a[2]=1; System.out.println(a[1]+" "+a[2]); for(int i=3;i<=n;i++){ a[1]=a[i]=1; for(int j=i-1;j>1;j--){ a[j]=a[j]+a[j-1]; } for(int j=1;j<=i;j++){ System.out.print(a[j]+" "); } System.out.println(); } } } 实验结果：n=10 实验二：0-1背包问题 问题分析：：令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 1 实验目的 （1）掌握典型机电产品多学科协同优化设计软件环境组成，包括建模软件、分析软件、协同平台； （2）自主设计产品模型、分析过程、优化目标； (3) 对得到的优化结果进行定性分析，解释结果的合理性，编写上机实验报告。 2 实验内容 (1) 轴或负载台的有限元分析 (2) 基于Adams的运动学分析与仿真 3实验相关情况介绍（包含使用软件或实验设备等情况） 网络协同设计环境，如图1所示：包括产品CAD建模、有限元分析FEM、动力学仿真ADAMS和控制仿真MATLAB。计算机网络硬件环境和相应软件环境。图形工作站和路由器，安装协同设计仿真软件。 型 图1 协同设计仿真平台组成 典型机电产品协同设计仿真工作流程如下图2所示。 1）利用CAD建模工具，建立产品模型； 2）利用ADAMS建立产品运动学模型； 3）根据CAD和ADAMS传过来的结构模型和边界条件分析零件应力场和应变场；4）用ADAMS分析得到的运动参数（位移、速度）。 CAD模型 （STEP / IGES格式） 1.产品CAD建模 （CATIA） 3.CAE有限元分 析 （CATIA） FEM 分析结果 （应力、应变、模态） 2.动力学分析 （ADAMS） 驱动力、反应 时间 有限元输入载荷 4.控制仿真 （MATLAB） 运动参数：位 移、速度 动力参数：惯 量、载荷 图2 协同设计仿真平台组成 SysML语言是UML语言(Unified Modeling Language，统一建模语言，一种面向对象的标准建模语言，用于软件系统的可视化建模)在系统工程应用领域的延续和扩展，是近年提出的用于系统体系结构设计的多用途建模语言，用于对由软硬件、数据和人综合而成的复杂系统的集成体系结构进行可视化的说明、分析、设计及校验。 在这里我们绘制参数图如下。在下面的参数图中，我们确定了系统中各部件的相互约束情况。消除文法的左递归实验
算法设计与分析实验报告贪心算法
现代设计黄金分割法复合形法实验报告word文档良心出品
实验报告 分治与递归
递归与分治实验报告
北京理工大学《数据结构与算法设计》实验报告实验一
机电产品设计实验报告
算法设计与分析实验报告
消除左递归实验报告
算法设计与实验报告讲解
机电产品现代设计方法实验报告
编译原理-实验二-递归下降分析程序构造
银行家算法设计实验报告
现代设计方法实验报告
南京邮电大学算法设计实验报告——动态规划法
物体运动的方式实验报告
算法分析实验报告--分治策略
编译原理实验报告
算法与设计实验报告
哈工大机电产品现代设计方法实验报告
相关主题
文本预览