算法设计及分析实验报告_Matlab实现
算法设计与分析实验报告贪心算法
算法设计与分析实验报告 贪心算法 班级：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] 《ACM算法与数据结构设计》课程大作业报告 题目：五位以内的对称素数 学生姓名 班级学号 学生学院计算机软件学院 学生专业计算机科学与技术 联系电话 电子邮 指导教师 指导单位计算机学院软件工程系 日期2011.5.24 注意事项 （1）课程大作业从《ACM算法与数据结构设计》课程实验二（2011年4月19日）或实验三（2011年5月10日）中任选一个课题完成。（2）课程大作业内容包括课题名称、课题内容和要求、课题分析、概要设计、详细设计、测试数据及其结果分析、调试过程中的问题、参考资料列表、课程小结等。 （3）课程报告可以打印，也可以手写，但前面两页内容、大作业撰写纲要、课程小结不可遗漏和更换。 （4）课程小结给出ACM程序设计过程的收获、遇到的问题，遇到问题解决问题过程的思考、程序调试能力的思考等，需要手写签字。（5）课程大作业提交时间为2011年5月24日（第14周星期二）晚19:00~20:00，地点：计算中心A机房。 一、课题名称： 五位以内的对称素数 二、课题内容和要求： 题目：判断一个数是否为对称且不大于五位数的素数。 要求：判断输入的一组数据（正整数）是否是五位以内的对称素数，逐个判断并输出“yes”或“no” 三、课题分析： 定义两个函数分别判断数据是否为素数（bool isprime(int n)），是否是对称数（bool issym(int n)）；在main()函数中利用if()语句来判断该数据是否是五位以内的数。只有同时满足三个条件，才能判断一个数据是五位以内的对称素数，输出“yes”；否则输出“no”。 输入输出方案： 输入: 输入数据含有不多于50个的正整数(0 《数据结构与算法设计》 实验报告 ——实验一 学院： 班级： 学号： 姓名： 一、实验目的 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，统一建模语言，一种面向对象的标准建模语言，用于软件系统的可视化建模)在系统工程应用领域的延续和扩展，是近年提出的用于系统体系结构设计的多用途建模语言，用于对由软硬件、数据和人综合而成的复杂系统的集成体系结构进行可视化的说明、分析、设计及校验。 在这里我们绘制参数图如下。在下面的参数图中，我们确定了系统中各部件的相互约束情况。 实验报告一 课程C++ 实验名称简单算法设计第 1 页专业_数学与应用数学_ __ 班级__ 双师一班学号105012011056 姓名陈萌 实验日期：2013 年 3 月9 日报告退发(订正、重做) 一、实验目的 1. 理解算法设计与分析的基本概念，理解解决问题的算法设计与实现过程； 2. 掌握简单问题的算法设计与分析，能设计比较高效的算法； 3. 熟悉C/C++语言等的集成开发环境，掌握简单程序设计与实现的能力。 二、实验内容 (一)相等元素问题 1.问题描述 元素唯一性问题：给出一个整数集合，假定这些整数存储在数组A[1…n]中，确定它们中是否存在两个相等的元素。请设计出一个有效算法来解决这个问题，你的算法的时间复杂性是多少？ 2. 具体要求（若在ACM平台上提交程序，必须按此要求）――平台上1767题 输入：输入的第一行是一个正整数m，表示测试例个数。接下来几行是m个测试例的数据，每个测试例的数据由两行组成，其中第一行为一个正整数n (n<=500)，表示整数序列的长度，第二行给出整数序列，整数之间用一个空格隔开。 输出：对于每个测试例输出一行，若该组测试例中存在两个相等的元素则输出”Yes”，否则，输出”No”。每个测试例的输出数据用一行表示。 3. 测试数据 输入：3 10 9 71 25 64 38 52 5 31 19 45 16 26 35 17 92 53 24 6 57 21 12 34 2 17 86 75 33 20 15 87 32 7 84 35 26 45 78 96 52 22 37 65 9 43 21 3 33 91 输出：No Yes No (二) 整数集合分解 1.问题描述 设计算法把一个n个元素的整数集合（n为偶数）分成两个子集S1和S2，使得：每个新的集合中含有n/2个元素，且S1中的所有元素的和与S2中的所有元素的和的差最大。 2. 具体要求（若在ACM平台上提交程序，必须按此要求）――平台上1768题 输入的第一行是一个正整数m，表示测试例个数。接下来几行是m个测试例的数据，每个测试例的数据由两行组成，其中第一行为一个正整数n (n为偶数，且n<=500)，表示原整数集合的长度，第二行给出这n个整数序列，整数之间用一个空格隔开。 输出：对于每个测试例输出两行，分别表示新生成的整数集合。其中，第一行是元素和比较小的整数集合，第二行是元素和比较大的整数集合，整数之间用一个空格隔开。两个测 算法设计与分析实验报告 学院：信息学院 专业：物联网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； 2017级《程序设计与算法综合实践》 期末大作业题目及评分标准 有如下情况之一者，为不及格。 （1）未能完成所选题目评分标准的最低要求。 （2）抄袭他人成果。 （3）大作业检查时不带电脑，或电脑没有C语言开发环境。 （4）出勤次数、课堂表现等不符合学校相关教学文件规定等其他情况。 备选题目目录 1.图书购买系统...............................................................................................................- 2 - 2.物流信息管理系统 ....................................................................................................- 3 - 3.PM2.5实时信息管理系统 ............................................................ - 5 - 4.电影评论系统 ............................................................................... - 6 - 5.游戏角色属性分析........................................................................ - 8 - 6.KTV点歌系统 ................................................................................ - 9 - 7.英语词斩系统 ............................................................................. - 11 - 8.校运动会成绩管理系统.............................................................. - 14 - 9.通讯录管理系统 ......................................................................... - 15 - 10.机票购买系统 ............................................................................. - 16 - 11.车辆销售管理系统...................................................................... - 17 - 12.饮品自动贩卖机系统.................................................................. - 18 - 《算法设计》实习报告 班级 XXXX 名 XX 学号 XXXXXXX 1.给出Dijkstra算法的思想,并用C或C++实现，并分析该算法的复杂度。对下 图所示的有向网，试利用Dijkstra算法求出从源点1到其他顶点的最短路径。 实习报告的内容： <一>解决问题和算法思想 这个问题即为单源最短路问题。解决单源最短路径的基本思想是把图中所有结点分为两组，每一个结点对应一个距离值。设置两个结点的集合S和T，集合S中存放已找到最短路径的结点，集合T存放当前还未找到最短路径的结点。初始状态时，集合S只包含源点，设为V0，然后不断从集合T中选择到源点V0路径长度最短的结点u加入到集合S中，集合S每加入一个新的结点u都要修改从源点V0到集合T中剩余结点的当前最短路径长度值，集合T中各结点的新的当前路径最短路径，为原来的最短路径与从源点过结点u到达该结点的路径长度中的较小者。此过程不断重复，直到集合T中的结点全部加入到集合S中为止。 <二>调试通过的源程序 (1)顺序表打包文件:seqlist.h typedef struct { datatype list[maxsize]; int size; }seqlist; void listinitiate(seqlist *l) { l->size=0; } int listlength(seqlist l) { return l.size; } int listinsert(seqlist *l,int i,datatype x) { int j; if(l->size>=maxsize) { printf("it is too full!\n"); return 0; } else if(i<0||i>l->size) { printf("error!\n"); return 0; } else { for(j=l->size;j>i;j--) l->list[j]=l->list[j-1]; l->list[i]=x; l->size++; return 1; } } int listdelete(seqlist *l,int i,datatype *x) { int j; if(l->size<=0) { printf("it is empty!\n"); return 0; } else if(i<0||i>l->size-1) { printf("error!\n"); return 0; } else { *x=l->list[i]; for(j=i+1;j<=l->size-1;j++) l->list[j-1]=l->list[j]; l->size--; return 1; } } int listget(seqlist l,int i,datatype *x) { if(i<0||i>=l.size-1) { printf("error!\n"); return 0; } else { *x=l.list[i]; return 1; } } （2）邻接矩阵打包文件:adjmgraph.h 银行家算法设计实验报告 银行家算法设计实验报告 一．题目分析 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 《软件系统分析与设计》 期末大作业 选题名称：游戏平台管理系统设计人：徐文豪刘青海 赖超宇甘智宏 班级：软工143班 南昌大学软件学院 2016.6.1 目录 一、整体描述 (2) 二、需求分析 (3) 三、系统功能概况 (4) 四、类的属性与方法 (5) 五、系统界面界限 (11) 六、设计模型 (13) 七、设计原则 (17) 八、设计模式······················ 一、整体描述 随着移动通讯的发展，手机应用也越来越多，其中，游戏应用占据了很大的比重，游戏平台管理系统是整合了大量游戏应用，以及玩家线上交流的平台。 主要受众群：拥有移动端或电脑端的人群。 应用前景：移动互联的发展为游戏平台的发展提供了很大的生存空间，应用前景十分广阔 盈利方式：向平台中游戏的开发商收取一定的费用，游戏玩家向游戏中注入资金时，收取一定比例的游戏收入。 面临的困难：游戏平台前期的推广，提高游戏平台本身对开发商和游戏玩家的吸引力，游戏平台能否适应大部分游戏玩家的要求。 玩家首先要注册账号，然后就可以在上面下载游戏应用，上传自己的游戏资源。同时，根据玩家的活跃程度获取相应积分，用积分可以兑换游戏礼包，也会根据玩家等级在游戏装备上给与相应的优惠和等级奖励。玩家在每一款游戏的评论区都可以交流游戏经验，提出意见和建议，以便游戏及时更新，弥补相应不足。玩家也可以建立游戏工会，不同游戏的玩家都可以加入，分享自己的游戏心得或者转赠游戏装备或积分。 二、需求分析 时间when：游戏厂商：随时；注册用户：随时；管理人员：正常工作时间。 地点Where：游戏厂商，管理人员：工作地点；注册用户：随地 人员who：游戏厂商，管理人员，注册用户， What：游戏厂商：推广游戏，管理人员：扩大服务，盈利；注册人员：玩游戏。 Why：游戏厂商：推广力度不大，效果不好，管理人员：方便管理，注册用户：良好的游戏环境。 性能Performance：系统提供服务的效率，响应时间快，由于是手机端的APP吞吐量不需要太大。 成本Cost：实现系统需要付出的代价，耗费****元 时间Time：2016年6月3日 可靠性Reliability: 需要系统长时间正确运行的能力 安全性Security: 由于该平台会涉及资金的流动，所以需要对信息安全的保护能力。 合规性Compliance: 需要符合各种行业的标准，法律法规，规范。技术性Technology:要求基于安卓平台开发。 兼容性Compatibility:需要与一些支付平台进行兼容能力。还有对游戏的兼容性。 本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼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．代码设计： 实验报告 （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别的条件不变,向小车上加钩 算法分析大作业 动态规划方法解 乘法表问题和汽车加油行驶问题目录 1.动态规划解乘法表问题 1.1问题描述------ 1.2算法设计思想------ 1.3设计方法------ 1.4源代码------ 1.5最终结果------ 2.动态规划解汽车加油行驶问题 2.1问题描述------ 2.2算法设计思想------ 2.3设计方法------ 2.4源代码------ 2.5最终结果------ 3.总结 1.动态规划解决乘法表问题 1.1问题描述 定义于字母表∑{a,b,c)上的乘法表如表所示： 依此乘法表,对任一定义于∑上的字符串,适当加括号表达式后得到一个表达式。 例如,对于字符串x=bbbba,它的一个加括号表达式为(b(bb))(ba)。依乘法表,该表达式的值为a。 试设计一个动态规划算法,对任一定义于∑上的字符串x=x1x2…xn，计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a。 1.2算法设计思想 设常量a,b,c 分别为 1, 2 ,3 。n 为字符串的长度。 设字符串的第 i 到第 j 位乘积为 a 的加括号法有result[i][j][a] 种， 字符串的第 i 到第 j 位乘积为 b 的加括号法有result[i][j][b] 种, 字符串的第 i 到第 j 位乘积为 c 的加括号法有 result[i][j][c] 种。 则原问题的解是：result[i][n][a] 。 设 k 为 i 到 j 中的某一个字符，则对于 k 从 i 到 j ：result[i][j][a] += result[i][k][a] * result[k + 1][j][c] + result[i][k][b] * result[k + 1][j][c] + result[i][k][c] * result[k + 1][j][a]; result[i][j][b] += result[i][k][a] * result[k + 1][j][a] + result[i][k][a] * result[k + 1][j][b] + result[i][k][b] * result[k + 1][j][b]; result[i][j][c] += result[i][k][b] * result[k + 1][j][a] + result[i][k][c] * result[k + 1][j][b] + result[i][k][c] * result[k + 1][j][c]; 算法设计与分析课程实验项目目录 学生：学号： *实验项目类型：演示性、验证性、综合性、设计性实验。 *此表由学生按顺序填写。 本科实验报告专用纸 课程名称算法设计与分析成绩评定 实验项目名称蛮力法指导教师 实验项目编号实验项目类型设计实验地点机房 学生学号 学院信息科学技术学院数学系信息与计算科学专业级 实验时间2012年3月1 日～6月30日温度24℃ 1.实验目的和要求： 熟悉蛮力法的设计思想。 2.实验原理和主要容： 实验原理：蛮力法常直接基于问题的描述和所涉及的概念解决问题。 实验容：以下题目任选其一 1).为蛮力字符串匹配写一段可视化程序。 2).写一个程序，实现凸包问题的蛮力算法。 3).最著名的算式谜题是由大名鼎鼎的英国谜人 H.E.Dudeney(1857-1930)给出的： S END +MORE MONEY . 这里有两个前提假设： 第一，字母和十进制数字之间一一对应，也就是每个字母只代表一个数字，而且不同的字母代表不同的数字；第二，数字0不出现在任何数的最左边。求解一个字母算术意味着找到每个字母代表的是哪个数字。请注意，解可能并不是唯一的，不同人的解可能并不相同。3.实验结果及分析： （将程序和实验结果粘贴，程序能够注释清楚更好。） 该算法程序代码如下： #include "stdafx.h" #include "time.h" int main(int argc, char* argv[]) { int x[100],y[100]; int a,b,c,i,j,k,l,m,n=0,p,t1[100],num; int xsat[100],ysat[100]; printf("请输入点的个数：\n"); scanf("%d",&num); getchar(); clock_t start,end; start=clock(); printf("请输入各点坐标:\n"); for(l=0;l现代设计黄金分割法复合形法实验报告word文档良心出品
《ACM算法与数据结构设计》大作业
北京理工大学《数据结构与算法设计》实验报告实验一
机电产品设计实验报告
算法设计实验报告一(简单算法设计)
算法设计与实验报告讲解
机电产品现代设计方法实验报告
《程序设计与算法综合实践》期末大作业题目及评分标准
算法设计实验报告
银行家算法设计实验报告
现代设计方法实验报告
软件系统分析与设计大作业
算法设计与分析实验报告
南京邮电大学算法设计实验报告——动态规划法
物体运动的方式实验报告
算法分析大作业动态规划方法解乘法表问题和汽车加油行驶问题#精选.
《算法设计与分析》实验报告