《算法设计》课程报告
课序号： 01 学号： 2012141461134
姓名：刘佳玉
任课教师：陈瑜
评阅成绩：
评阅意见：
提交报告时间：2014年 6 月 16 日
贪心算法
1、问题描述
（这是我在soj上找的一道题，以前没做出来，现在用贪心的思想做出来了）
约翰要去钓鱼。他有h小时可用（1≤h≤16），在这个地区有n个湖泊（2≤n≤25），所有的湖泊沿着一条单行道可到达。约翰从湖泊1开始，他可以在任何湖泊结束。他只能从一个湖，到下一个，但他没有必要停在任何湖除非他想停。对于每个i = 1，……，n-1，ti 表示从湖i到湖i+1的5分钟的时间间隔（0 < ti < = 192）。例如，t3 = 4意味着它从湖3湖4需要20分钟的时间。
为了帮助他们规划自己的钓鱼旅行，约翰已经收集了一些关于湖泊信息。对于每个湖泊的i，能钓到的鱼在最初的5分钟的数量，用fi表示（fi > = 0），是已知的。每钓5分钟的鱼，能钓到的鱼在接下来的5分钟的间隔降低一个恒定的数di（di＞＝0）。如果能钓到的鱼在一个时间区的数量小于或等于di，将不会有更多的鱼留在湖里在下一个时间间隔。为了简化规划，约翰认为没有人会在影响他期待钓到的鱼的数量的湖里钓鱼。
写一个程序来帮助约翰计划他的最大化期望钓到的鱼的数量的钓鱼之旅。在每个湖花费的时间数必须是5的倍数。
这个问题包含多个测试案例！
一个多输入的第一行是一个整数N，然后一个空白行后的N个输入块。每个输入块由问题描述中的格式表示的。每个输入块之间有一个空行。
输出格式包含N个输出块。输出块之间要有一个空白行。
输入
在输入中，会给你一个案例输入的数量。每一种情况下，以n开始，其次是h，接下来有一行n个整数指定fi（1 < =i< = n），然后有一行n个整数di（1≤i＜＝n），最后，有一行n - 1的整数ti（1≤i＜＝n-1）。输入在n=0的情况下终止。
输出
对于每个测试案例，输出在每个湖花费的时间数量，以逗号分隔，为实现计划的能钓到的鱼的最大数量（你必须把整个计划输出在一行，即使超过80个字符）。这是一个包含预期能钓到的鱼的数量。如果存在多个计划，选择一个花尽可能长的时间在湖1的计划，即使没有鱼能钓在一些时间里。如果不行，选择一个花尽可能长的时间湖2的计划，等等。每个案例之间有一个空行。
2、算法分析
看到这个题目后，你可能毫无思绪，怎样钓才能钓最多呢？请仔细看题，题目中说，沿湖是一条单行道，只能前进，不能后退，所以我要使前面钓的鱼最多，但如果不和后面的湖比较，怎么知道我前面掉的鱼是最佳的呢？我们不妨假设，我们只走到湖i（1<=i<=n），我们把花在路上的时间减去，这样就相当与我们可以再湖1和湖i之间任意选择一个湖钓鱼，这样每一个时间间隔我们在哪钓鱼通过比较一下不就清楚了吗，用一个循环找到最多到湖i钓鱼的最优解，然后这个问题就迎刃而解了。
3、程序源代码
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int f[30]; //能钓到的鱼的数量在某一时间块
int d[30]; //在某一时间块钓鱼后湖里的鱼减少的数量
int t[30]; //从湖i到湖i+1的时间
int s[30]; //最佳情况下在每个湖停留的时间
int fc[30]; //只到湖i钓鱼时各个湖能钓到的鱼的数量
int sc[30]; //只到湖i钓鱼时各个湖停留的时间
int main()
{
int T; //输入模块数
int n; //湖的数量
int h; //时间
int i,j,k;
int sum; //只到湖i钓鱼能钓到的鱼的总量
int maxh; //从湖1到湖i能钓到的最大数量的鱼的湖 int maxn; //当前能钓到的鱼的最大数量，初始为-1； int temp; //钓鱼花的时间
int kase=1; //案例数
printf("输入案例的数量：\n");
scanf("%d",&T);
while(T--)
{
printf("\n");
printf("案例%d:\n",kase++);
printf("输入湖泊的数量(0结束该组案例)：\n"); while(scanf("%d",&n)==1&&n)
{
printf("输入钓鱼的时间：\n");
scanf("%d",&h);
h*=12; //以每5分钟为一个时间单位
printf("输入初始时每个湖泊中的鱼的数量：\n");
for(i=1;i<=n;i++)
{
scanf("%d",&f[i]);
}
printf("输入每个湖泊在钓过一次鱼后鱼减少的数量：\n");
for(i=1;i<=n;i++)
{
scanf("%d",&d[i]);
}
printf("输入从湖泊i到湖泊i+1的时间：\n");
for(i=2;i<=n;i++)
{
scanf("%d",&t[i]);
}
t[1]=0; //从湖1到湖1的时间为0
maxn=-1; //初始maxn的值
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
fc[j]=f[j]; //复制能钓到的鱼的数量
}
for(j=1;j<=n;j++)
{
sc[j]=0; //开始时每个湖停留的时间为0
}
h=h-t[i]; //除去路上用的时间就是钓鱼的时间
//printf("h:%d\n",h); //查看h的值
sum=0; //初始只到湖i是能钓到的鱼的总数
for(k=1;k<=h;k++)
{
maxh=1; //当前时间段能钓到最多鱼的湖
for(j=1;j<=i;j++)
{
if(fc[j]>fc[maxh])
{
maxh=j;
}
}
if(fc[maxh]<=0)
{
break; //如果最大能钓到的鱼的数量<=0，那么就停止钓鱼，把时间花在湖1
}
sum+=fc[maxh]; //钓到的鱼的总量
fc[maxh]-=d[maxh]; //在湖maxh钓到的鱼的数量减少
sc[maxh]+=5; //在湖maxn停留的时间加5
}
//printf("sum:%d\n",sum);
if(sum>maxn) // 保存最优解
{
temp=0;
maxn=sum;
for(j=1;j<=n;j++)
{
s[j]=sc[j];
temp+=sc[j];
}
s[1]=s[1]+h*5-temp; //将剩余时间停留在湖1
}
/*for(j=1;j<=n;j++) //查看当前最优解
{
printf("%d ",s[j]);
}
printf("\n");*/
}
printf("输出在每个湖泊停留的时间：\n");
for(i=1;i<=n;i++) //输出
{
printf("%d",s[i]);
if(i!=n)
{
printf(", ");
}
}
printf("\n");
printf("能钓到的鱼的最大数量: %d\n",maxn);
printf("\n");
printf("输入湖泊的数量(0结束该组案例)：\n"); }
}
return 0;
}
4、测试数据与运行结果
样本输入
1
2
1
10 1
2 5
2
4
4
10 15 20 17
0 3 4 3
1 2 3
4
4
10 15 50 30
0 3 4 3
1 2 3
样本输出
45 5
Number of fish expected: 31
240 0 0 0
Number of fish expected: 480 115 10 50 35
Number of fish expected: 724 测试截图：
5、算法复杂性分析与讨论
由于有三个for循环：
for(i=1;i<=n;i++)
for(k=1;k<=h;k++)
for(j=1;j<=i;j++)
算法复杂度O（n）=k*n^2。由于这道题的n比较小，所以O（n^2）的算法也可以解决。
如果使用堆优化，可以更快，其O（n）=k*n*logn。
算法设计与分析实验报告 贪心算法 班级：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.通过实验实践、巩固线性表的相关操作； 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； 《算法设计》实习报告 班级 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 本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼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别的条件不变,向小车上加钩 算法设计与分析课程实验项目目录 学生：学号： *实验项目类型：演示性、验证性、综合性、设计性实验。 *此表由学生按顺序填写。 本科实验报告专用纸 课程名称算法设计与分析成绩评定 实验项目名称蛮力法指导教师 实验项目编号实验项目类型设计实验地点机房 学生学号 学院信息科学技术学院数学系信息与计算科学专业级 实验时间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 算法与分析实验报告软件工程专业 安徽工业大学 指导老师：许精明 实验内容 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，统一建模语言，一种面向对象的标准建模语言，用于软件系统的可视化建模)在系统工程应用领域的延续和扩展，是近年提出的用于系统体系结构设计的多用途建模语言，用于对由软硬件、数据和人综合而成的复杂系统的集成体系结构进行可视化的说明、分析、设计及校验。 在这里我们绘制参数图如下。在下面的参数图中，我们确定了系统中各部件的相互约束情况。 算法设计与分析实验报告 教师： 学号： 姓名： 实验一：串匹配问题 实验目的：(1) 深刻理解并掌握蛮力法的设计思想; (2) 提高应用蛮力法设计算法的技能; (3) 理解这样一个观点: 用蛮力法设计的算法, 一般来说, 经过适度的努力后, 都可以对算法的第一个版本进行一定程度的改良, 改进其时间性能。 三、实验要求：( 1) 实现BF 算法; (2 ) 实现BF 算法的改进算法: KMP 算法和BM 算法; (3 ) 对上述 3 个算法进行时间复杂性分析, 并设计实验程序验证 分析结果。 #include "stdio.h" #include "conio.h" #include 《算法设计》课程报告 课序号： 01 学号： 2012141461134 姓名：刘佳玉 任课教师：陈瑜 评阅成绩： 评阅意见： 提交报告时间：2014年 6 月 16 日 贪心算法 1、问题描述 （这是我在soj上找的一道题，以前没做出来，现在用贪心的思想做出来了） 约翰要去钓鱼。他有h小时可用（1≤h≤16），在这个地区有n个湖泊（2≤n≤25），所有的湖泊沿着一条单行道可到达。约翰从湖泊1开始，他可以在任何湖泊结束。他只能从一个湖，到下一个，但他没有必要停在任何湖除非他想停。对于每个i = 1，……，n-1，ti 表示从湖i到湖i+1的5分钟的时间间隔（0 < ti < = 192）。例如，t3 = 4意味着它从湖3湖4需要20分钟的时间。 为了帮助他们规划自己的钓鱼旅行，约翰已经收集了一些关于湖泊信息。对于每个湖泊的i，能钓到的鱼在最初的5分钟的数量，用fi表示（fi > = 0），是已知的。每钓5分钟的鱼，能钓到的鱼在接下来的5分钟的间隔降低一个恒定的数di（di＞＝0）。如果能钓到的鱼在一个时间区的数量小于或等于di，将不会有更多的鱼留在湖里在下一个时间间隔。为了简化规划，约翰认为没有人会在影响他期待钓到的鱼的数量的湖里钓鱼。 写一个程序来帮助约翰计划他的最大化期望钓到的鱼的数量的钓鱼之旅。在每个湖花费的时间数必须是5的倍数。 这个问题包含多个测试案例！ 一个多输入的第一行是一个整数N，然后一个空白行后的N个输入块。每个输入块由问题描述中的格式表示的。每个输入块之间有一个空行。 输出格式包含N个输出块。输出块之间要有一个空白行。 输入 在输入中，会给你一个案例输入的数量。每一种情况下，以n开始，其次是h，接下来有一行n个整数指定fi（1 < =i< = n），然后有一行n个整数di（1≤i＜＝n），最后，有一行n - 1的整数ti（1≤i＜＝n-1）。输入在n=0的情况下终止。 输出 课程名称：现代设计方法实验报告 实验项目： 1.AutoCAD使用的基本知识 2.AutoCAD基本命令使用 3.学习AutoCAD图形显示、图层和线性 实验一AutoCAD使用的基本知识 一、实验目的与要求： （1）掌握AutoCAD的安装和起动（2）了解AutoCAD操作界面组成 二、实验设备： AutoCAD安装软件、多媒体电脑等。 三、实验内容（实验步骤及操作方法）： 1. AutoCAD的安装非常方便，同其它软件包的安装基本一样，其要点如下： 在光盘上找到SETUP.EXE文件并执行； 在序列号对话框中输入正确的软件序列号； 在目标位置对话框中，可考虑将AutoCAD安装在空间相对富裕的驱动器下； 在安装类型对话框中，根据需要以及硬盘空间大小，合理选择安装类型为典型、完全、精简或自定义； 在文件夹名称对话框中，为AutoCAD指定一个程序文件夹。 2. AutoCAD操作界面的组成及作用 标题栏 标题栏位于工作界面的最上面，用来显示AutoCAD的程序图标以及当前正在运行文件的名字（第一个文件和没打开其他图形显示的是Drawing1.dwg）等信息。单击位于标题栏右侧的按钮，可分别实现窗口的最小化、还原、最大化以及关闭AutoCAD等操作。单击标题栏最左边AutoCAD的小图标，会弹出一个AutoCAD窗口控制下拉菜单，利用该下拉菜单中的命令，也可以进行最小化或最大化窗口、恢复窗口、移动窗口或关闭AutoCAD等操作，双击该控制图标可以关闭应用程序。 工具栏 工具栏是AutoCAD提供的一种调用命令的方式，它包含多个由图标表示的命令按钮，单击这些图标按钮，就可以调用相应的AutoCAD命令。 菜单栏与快捷菜单 AutoCAD的菜单栏由“文件”、“编辑”、“视图”、“插入”、“格式”、“工具”、“绘图”、“标注”及“修改”等菜单组成，这些菜单包括了AutoCAD几乎全部的功能和命令。 绘图区 绘图区是用户进行绘图和显示图形的区域，类似于手工绘图时的图纸。当鼠标指针位于绘图区时，会变成十字光标，其中心有一个小方块，称为目标框，可以用来选择对象，使其变成可编辑状态。 命令区与命令窗口 绘图区的下方是命令行及命令窗口。命令行用于显示用户从键盘、菜单或工具栏中按钮中输入的命令内容（命令不分大小写，可完整缩写）；命令窗口中含有AutoCAD启动后所用过的全部命令及提示信息。用户可通过按F2键来打开现代设计黄金分割法复合形法实验报告word文档良心出品
北京理工大学《数据结构与算法设计》实验报告实验一
机电产品设计实验报告
算法设计实验报告一(简单算法设计)
算法设计与实验报告讲解
机电产品现代设计方法实验报告
算法设计实验报告
银行家算法设计实验报告
现代设计方法实验报告
算法设计与分析实验报告
南京邮电大学算法设计实验报告——动态规划法
物体运动的方式实验报告
《算法设计与分析》实验报告
算法与设计实验报告
哈工大机电产品现代设计方法实验报告
算法设计与分析实验报告
算法设计实验报告(川大陈瑜)
现代设计方法实验报告
相关主题
文本预览