算法设计与分析第三章程序作业
源程序代码
1.最长公共子序列
#include
#include
#define N 1000
int e[N][N],f[N][N];
void LCSLength(int m,int n,char *x,char *y,int c[][N],int b[][N])//构造数组b[i][j]
{
int i,j;
for (i=1; i<=m;i++)
c[i][0]=0; //初始化, Y[j]为空时
for (i=1;i<=n;i++)
c[0][i]=0; //初始化，X[i]为空时
for (i=1;i<=m;i++) //两重循环，自下而上，// 计算子问题{X(i), Y(j)}
for (j=1;j<=n;j++){
if(x[i]==y[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])
{ //情况2
c[i][j]=c[i-1][j];
b[i][j]=2;
}
else //情况3
{
c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
}
void LCS(int i,int j,char *x,int b[][N])
{
if (i==0||j==0)
return;
if (b[i][j]==1)
{
LCS(i-1,j-1,x,b);
printf("%c",x[i]);
/*第1种情况下，X(i)和Y(j)的最长公共子序列由X(i-1)和Y(j-1)的解LCS(i-1, j-1, x, b)，加上位于最后的X[i]
组成*/
}
else if(b[i][j]==2)
LCS(i-1,j,x,b);
else
LCS(i,j-1,x,b); //其它2种情况下，原问题解等于子问题解
}
main()
{
char A[N],B[N],C[N],D[N];
int a=1,b=1,c=1,d=1;
char ch;
int i;
FILE * fp;
if((fp=fopen("最长公共子序列输入数据.txt","r"))==NULL)//打开文件失败
printf("Can't open file !!!");
else
{//读取文件内容
ch=fgetc(fp);
ch=fgetc(fp);
ch=fgetc(fp);
ch=fgetc(fp);
ch=fgetc(fp);
while(ch!='B'&&ch!=EOF) {
A[a]=ch;
a++;
ch=fgetc(fp);
while(ch=='\n')
ch=fgetc(fp);
}
a--;
ch=fgetc(fp);
ch=fgetc(fp);
ch=fgetc(fp);
ch=fgetc(fp);
while(ch!='C'&&ch!=EOF) {
B[b]=ch;
b++;
ch=fgetc(fp);
while(ch=='\n')
ch=fgetc(fp);
}
b--;
ch=fgetc(fp);
ch=fgetc(fp);
ch=fgetc(fp);
ch=fgetc(fp);
while(ch!='D'&&ch!=EOF) {
C[c]=ch;
c++;
ch=fgetc(fp);
while(ch=='\n')
ch=fgetc(fp);
}
c--;
ch=fgetc(fp);
ch=fgetc(fp);
ch=fgetc(fp);
ch=fgetc(fp);
while(ch!=EOF)
{
D[d]=ch;
d++;
ch=fgetc(fp);
while(ch=='\n')
ch=fgetc(fp);
}
d--;
}
fclose(fp);
printf("文件读取完成!!!\n");
/* for(i=0;i<=a;i++)
printf("%c",A[i]);
printf("\n");
for(i=0;i<=b;i++)
printf("%c",B[i]);
printf("\n");
for(i=0;i<=c;i++)
printf("%c",C[i]);
printf("\n");
for(i=0;i<=d;i++)
printf("%c",D[i]);
printf("\n"); */
printf("\n\n\nA和B的最长公共子序列为：\n");
LCSLength(a,b,A,B,e,f);
LCS(a,b,A,f);
printf("\n\n\nC和D的最长公共子序列为：\n");
LCSLength(c,d,C,D,e,f);
LCS(c,d,C,f);
printf("\n\n\nA和D的最长公共子序列为：\n");
LCSLength(a,d,A,D,e,f);
LCS(a,d,A,f);
system("pause");
return 0;
}
2.最大子段和
#include
#include
#define N 400
void MaxSum(int n,int *a) {
int sum=0,b=0;
int i,x1=0,y1=0,x=0,y=0;
for(i=1;i<=n;i++)
{
if (b>0)
{
b+=a[i];
y1=i;
}
else
{
b=a[i];
x1=i;
}
if(b>sum)
{
sum=b;
x=x1;
y=y1;
}
}
printf("\n该序列的最大子段和的位置为从第%d个到第%d个",x+1,y+1);
printf("\n该序列的和最大子段为：\n");
for(i=x;i<=y;i++)
printf("%d ",a[i]);
printf("\n它们的和为%d \n",sum);
}
main()
{
int A[N],B[N];
int a=0,b=0;
int i;
FILE *fp1,*fp2;
if((fp1=fopen("最大子段和输入数据-序列1.txt","r"))==NULL)//打开文件失败
printf("Can't open file1 !!!");
else //读取文件内容
for(i=0;!feof(fp1);i++)
fscanf(fp1,"%d\n",&A[i]);
a=i-1;
}
if((fp2=fopen("最大子段和输入数据-序列2.txt","r"))==NULL)//打开文件失败
printf("Can't open file2 !!!");
else
{
for(i=0;!feof(fp2);i++)
fscanf(fp2,"%d\n",&B[i]);
b=i-1;
}
fclose(fp1);
fclose(fp1);
printf("文件读取成功！！！\n\n\n");
printf("对于最大子段和输入数据-序列1 ");
MaxSum(a,A);//计算最大子段和
printf("\n\n对于最大子段和输入数据-序列2 ");
MaxSum(b,B);
// for(i=0;i<=b;i++)
// printf("%d ",B[i]);
system("pause");
return 0;
}
3.凸多边形最优三角剖分
#include
#include
#include
#define N 30
#define EARTH_RADIUS 6378.137
struct Base{//基站结构体
int ENODEBID;//基站标识
float LONGITUDE;//基站经度
float LATITUDE;//基站纬度
int NUM;//基站k-dist距离
};
void readfile(struct Base * base,int n) //读取文件函数
{
FILE * fp;
int i=0;
if(n==21)
fp=fopen("21个基站凸多边形数据.csv","rb");
else
fp=fopen("29个基站凸多边形数据.csv","rb");
if(fp==NULL)//打开文件失败
printf("Can't open file !!!");
else
{
while(EOF!=fscanf(fp,"%d,%f,%f,%d",&base[i].ENODEBID,&base[i].LO NGITUDE,&base[i].LATITUDE,&base[i].NUM))
{//将数据读入结构体数组
i++;
//printf("%d\n",i);
}
// printf("文件读入成功！！！\n\n\n");
fclose(fp);
}
float rad(float LatOrLon)
{
return LatOrLon * 3.14/180.0;
}
float distance(struct Base * base,int a,int b)//求两个基站间的距离
{
float s;
float radLat1,radLat2,radlng1,radlng2;
radLat1 = rad(base[a].LATITUDE);
radLat2 = rad(base[b].LATITUDE);
radlng1 = rad(base[a].LONGITUDE);
radlng2 = rad(base[b].LONGITUDE);
//利用正弦余弦公式求距离
if(radLat1==radLat2&&radlng1==radlng2)
s=0;
else
s
=acos(cos(radLat1)*cos(radLat2)*cos(radlng1-radlng2)+sin(radLat1)*s in(radLat2));
s = s * EARTH_RADIUS;
s=round(s*1000);
}
return s;
}
float weight(struct Base * base,int a,int b,int c)
{
float s,s1,s2,s3;
s1=distance(base,a,b);
s2=distance(base,b,c);
s3=distance(base,a,c);
//s=distance(base,a,b)+distance(base,b,c)+distance(base,a,c);
s=s1+s2+s3;
return s;
}
float MinWeightTriangulation(struct Base * base,int n,float t[][N],int s[][N])
{
int i,j,r,k;
float u=0;
for(i=1;i<=n;i++)
t[i][i]=0;
for(r=2;r<=n;r++) //r为当前计算的链长（子问题规模）for(i=1;i<=n-r+1;i++)//n-r+1为最后一个r链的前边界
{
j=i+r-1;//计算前边界为r，链长为r的链的后边界
t[i][j]=t[i+1][j]+weight(base,i-1,i,j);//将链ij划分为A(i) * ( A[i+1:j] )这里实际上就是k=i
s[i][j]=i;
for (k=i+1;k { u=t[i][k]+t[k+1][j]+weight(base,i-1,k,j); if(u { t[i][j]=u; s[i][j]=k; } } } return t[1][n]; } void Traceback(int i,int j,int s[][N]) { if(i==j) return; Traceback(i,s[i][j],s); Traceback(s[i][j]+1,j,s); printf("三角剖分顶点：V%d , V%d , V%d\n",i-1,j,s[i][j]); } main() { int i; float t[N][N]; int s[N][N]; struct Base base21[N];//结构体（N宏定义） struct Base base29[N];//结构体（N宏定义） readfile(base21,21);//将数据从文件中读到结构体中 readfile(base29,29);//将数据从文件中读到结构体中 printf("文件读入成功！！！\n\n\n"); // for(i=0;i<=28;i++) // printf("%6d %.3f %.5f %d\n",base29[i].ENODEBID,base29[i].LONGITU DE,base29[i].LATITUDE,base29[i].NUM); printf("凸21多边形的最优三角剖分值为%f",MinWeightTriangulation(base21,20,t,s)); printf("最优三角剖分结构为：\n"); Traceback(1,20,s); //s[i][j]记录了Vi-1和Vj构成三角形的第3个顶点的位置 printf("凸29多边形的最优三角剖分值为%f",MinWeightTriangulation(base29,28,t,s)); printf("最优三角剖分结构为：\n"); Traceback(1,28,s); //s[i][j]记录了Vi-1和Vj构成三角形的第3个顶点的位置 system("pause"); return 0; } 4.01背包问题 #include #include #define N 100 struct Goods{ int weight;//物品重量 int value;//物品价值 }; int knapsack(struct Goods *goods,int bag,int number,int p[][2],int head[]) { int left=0,right=0,next=1,i,j,k,m,y; p[0][0]=0; p[0][1]=0; head[number+1]=0; head[number]=1; for(i=number;i>=1;i--){ k=left; for(j=left;j<=right&&p[j][0]+goods[i-1].weight<=bag;j++){ y=p[j][0]+goods[i-1].weight; m=p[j][1]+goods[i-1].value; while(k<=right&&p[k][0] p[next][0]=p[k][0]; p[next][1]=p[k][1]; next++; k++; } if(k<=right&&p[k][0]==y){ if(m m=p[k][1]; } k++; } if(m>p[next-1][1]){ p[next][0]=y; p[next][1]=m; 课程设计实验报告 -----物联网实验 学院：电子工程学院班级：2011211204 指导老师：赵同刚 一．物联网概念 物联网是新一代信息技术的重要组成部分。物联网的英文名称叫“The Internet of things”。顾名思义，物联网就是“物物相连的互联网”。这有两层意思：第一，物联网的核心和基础仍然是互联网，是在互联网的基础上延伸和扩展的网络；第二，其用户端延伸和扩展到了任何物体与物体之间，进行信息交换和通信。因此，物联网的定义是：通过射频识别（RFID）、红外感应器、全球定位系统、激光扫描器等信息传感设备，按约定的协议，把任何物体与互联网相连接，进行信息交换和通信，以实现对物体的智能化识别、定位、跟踪、监控和管理的一种网络。 二．物联网作用 现有成熟的主要应用包括： —检测、捕捉和识别人脸，感知人的身份； —分析运动目标（人和物）的行为，防范周界入侵； —感知人的流动，用于客流统计和分析、娱乐场所等公共场合逗留人数预警； —感知人或者物的消失、出现，用于财产保全、可疑遗留物识别等； —感知和捕捉运动中的车牌，用于非法占用公交车道的车辆车牌捕捉； —感知人群聚集状态、驾驶疲劳状态、烟雾现象等各类信息。 三．物联网无线传感（ZigBee）感知系统 ZigBee是一种新兴的短距离、低功耗、低数据速率、低成本、低复杂度的无线网络技术。ZigBee在整个协议栈中处于网络层的位置，其下是由IEEE 802.15.4规范实现PHY（物理层）和MAC（媒体访问控制层），对上ZigBee提供了应用层接口。 ZigBee可以组成星形、网状、树形的网络拓扑，可用于无线传感器网络（WSN）的组网以及其他无线应用。ZigBee工作于2.4 GHz的免执照频段，可以容纳高达65 000个节点。这些节点的功耗很低，单靠2节5号电池就可以维持工作6～24个月。除此之外，它还具有很高的可靠性和安全性。这些优点使基于ZigBee的WSN广泛应用于工业控制、消费性电子设备、汽车自动化、家庭和楼宇自动化、医用设备控制等。 ZigBee的基础是IEEE802.15.4，这是IEEE无线个人区域网工作组的一项标准，被称作IEEE802.15.4(ZigBee)技术标准。ZigBee不仅只是802.15.4的名字。IEEE仅处理低级MAC 算法设计与分析实验报告 贪心算法 班级：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] 校园网的组建与应用 摘要： 本文针对实验室的设备环境，对校园网的组网方式进行了研究和模拟，并最终提出了一套完整的校园网组网方案。 实验中我们对路由器、交换机等组网基础设备进行了认真的研究。关于路由器，我们实现了本地基本配置，并分别使用路由器的串口和以太网口实现了不同网段的网络互联，对路由器静态及动态路由机制进行了探究。关于交换机，我们实现了VLAN的划分以及不同VLAN间的相互通信，对广播风暴现象的产生原理及解决方案进行了特定的实验。综合两者的功能，我们对多种网络拓扑结构进行了分析，讨论和改进。最后通过实验和模拟提出了一套完整的校园网组建方案。 在此方案中，我们在实现了网络互通的情况下，我们进行了IP地址的划分，IP地址利用DHCP进行自动分配。并根据模拟实际，对不同的主机进行VLAN划分，同时保证不同VLAN间的相互访问与特定VLAN的保护与单向访问。同时构建内部防火墙保证校园网与外部的安全访问。构建了完整可靠的网络之后，依据校园网的功能和服务需求，我们搭建了FTP服务器，用于提供基础的网络服务。 限于实验室条件的限制，我们的方案并不是完全能够适用于现实的。但是，通过实验使我们对校园网乃至更大的网络有了更加深刻的了解。 目录 一、前言 随着信息的调整膨胀，全球信息已经进入以计算机网络为核心的时代。作为科技先导的教育行业，计算机校园网已是教育进行科研和现代化管理的重要手段。近几年、校园网已经取得很大的发展，中国教育科研网投入运营，全国多所高校校园网络开通联网。 随着学校教育手段的现代化，很多学校已经逐渐开始将学校的管理和教学过程向电子化方向发展，校园网的有无以及水平的高低也将成为评价学校及学生选择学校的新的标准之一，此时，校园网上的应用系统就显得尤为重要。一方面，学生可以通过它在促进学习的同时掌握丰富的计算机及网络信息知识，毫无疑问，这是学生综合素质中极为重要的一部分；另一方面，基于先进的网络平台和其上的应用系统，将极大的促进学校教育的现代化进程，实现高水平的教学和管理。 学校目前正加紧对信息化教育的规划和建设。开展的校园网络建设，旨在推动学校信息化建设，其最终建设目标是将建设成为一个借助信息化教育和管理手段的高水平的智能化、数字化的教学园区网络，最终完成统一软件资源平台的构建，实现统一网络管理、统一软件资源系统，并保证将来可扩展骨干网络节点互联带宽为10G，为用户提供高速接入网络，并实现网络远程教学、在线服务、教育资源共享等各种应用；利用现代信息技术从事管理、教学和科学研究等工作。最终达到在网络方面，更好的对众多网络使用及数据资源的安全控制，同时具有高性能，高效率，不间断的服务，方便的对网络中所有设备和应用进行有效的时事控制和管理。 二、综述 2.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个整数序列，整数之间用一个空格隔开。 输出：对于每个测试例输出两行，分别表示新生成的整数集合。其中，第一行是元素和比较小的整数集合，第二行是元素和比较大的整数集合，整数之间用一个空格隔开。两个测 北京邮电大学 信息与通信工程学院 电路综合实验报告 串行口数据传输的仿真及硬件实现 姓名： 学号： 班内序号： 班级： 指导老师： 日期：2014年10月10日 摘要： 本实验模拟了现代数字逻辑电路中的数据传输过程。使用连续的代表0、1的高低电平作为数字信号，将该数字信号从输出端发送到接收端，并分别用串行、并行两种方式进行锁存，检测。本实验模拟了序列信号的发生装置、串并转换装置、串行并行两种方式的检测装置、锁存输出和控制电路，实现了一个简单的串行口数据传输模型。在此试验中，通过对常见芯片的组合实现功能，将一串由0、1组成的数字信号进行传输、转换、检测，使之显示在数码管上成为可读信息。并且，还实现了对此电路显示的控制，使数码管在满足条件的情况下才点亮。在实验中，还使用了Qua rtusⅡ对设计的电路进行了仿真模拟。 关键字： 数据传输、串并转换、数据检测、QuartusII Abstract： This experiment simulated data transfer in modern digital logic circuit. Digital signal was transferred from the output terminal to the receiving end, which was consisted of continuous high or low level represent 0 and 1 as digital signal, and latch, test it through serial or parallel mode. Our experiment simulated the producing equipment of sequence signal, the signal conversion module, testing module of serial and parallel mode, latch output and control circuit. It implements a simple serial port data communication model. In the experiment, we use the combination of simple chips to realize the function that transport, transfer and test a sequence of the digital signal consisting of 0 and 1, and display it on LED Segment Displays. In addition, we realize the control of display. The LED Segment Displays works only in specific conditions. We also conduct simulations on QuartusⅡ. Keywords: Data transmission, String conversion, Data detection, Quartus II 目录 一、实验目的 (4) 算法设计与分析实验报告 学院：信息学院 专业：物联网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移动通信设备观察实验 1.1RNC设备观察实验 a) 了解机柜结构 b) 了解RNC机框结构及单板布局 c) 了解RNC各种类型以及连接方式 1.2基站设备硬件观察实验 a) 初步了解嵌入式通信设备组成 b) 认知大唐移动基站设备EMB5116的基本结构 c) 初步分析硬件功能设计 2网管操作实验 a) 了解OMC系统的基本功能和操作 b) 掌握OMT如何创建基站 二、实验设备 TD‐SCDMA移动通信设备一套（EMB5116基站+TDR3000+展示用板卡）、电脑。 三、实验内容 1TD-SCDMA系统认识 TD-SCDMA是英文Time Division-Synchronous Code Division Multiple Access（时分同步码分多址）的简称，TD-SDMA是由中国提出的第三代移动通信标准(简称3G)，也是ITU批准的三个3G标准中的一个，以我国知识产权为主的、被国际上广泛接受和认可的无线通信国际标准。是我国电信史上重要的里程碑。 TD-SCDMA在频谱利用率、业务支持灵活性、频率灵活性及成本等方面有独特优势。TD-SCDMA由于采用时分双工，上行和下行信道特性基本一致，因此，基站根据接收信号估计上行和下行信道特性比较容易。TD-SCDMA使用智能天线技术有先天的优势，而智能天线技术的使用又引入了SDMA的优点，可以减少用户间干扰，从而提高频谱利用率。TD-SCDMA还具有TDMA的优点，可以灵活设置 上行和下行时隙的比例而调整上行和下行的数据速率的比例，特别适合因特网业务中上行数据少而下行数据多的场合。但是这种上行下行转换点的可变性给同频组网增加了一定的复杂性。TD-SCDMA是时分双工，不需要成对的频带。因此，和另外两种频分双工的3G标准相比，在频率资源的划分上更加灵活。 图1 3G网络架构 2硬件认知 2.1 RNC设备认知 TDR3000整套移动通信设备机框外形结构如图2所示。 银行家算法设计实验报告 银行家算法设计实验报告 一．题目分析 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．代码设计： 数据结构实验报告 实验名称：实验3——树（哈夫曼编/解码器） 学生姓名： 班级： 班内序号： 学号： 日期：2011年12月5日 1．实验要求 利用二叉树结构实现哈夫曼编/解码器。 基本要求： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频 度，并建立哈夫曼树 2、建立编码表(CreateTable)：利用已经建好的哈夫曼树进行编码，并将每个字符的 编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输 出。 4、译码(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出 译码结果。 5、打印(Print)：以直观的方式打印哈夫曼树（选作） 计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈夫曼编码的压缩效果。 并用I love data Structure, I love Computer。I will try my best to study data Structure.进行测试。 2. 程序分析 哈夫曼树结点的存储结构包括双亲域parent，左子树lchild，右子树rchild，还有字符word，权重weight，编码code 对用户输入的信息进行统计，将每个字符作为哈夫曼树的叶子结点。统计每个字符出现的次数作为叶子的权重，统计次数可以根据每个字符不同的ASCII码，根据叶子结点的权重建立一个哈夫曼树。 建立每个叶子的编码从根结点开始，规定通往左子树路径记为0，通往右子树路径记为1。由于编码要求从根结点开始，所以需要前序遍历哈夫曼树，故编码过程是以前序遍历二叉树为基础的。同时注意递归函数中能否直接对结点的编码域进行操作。 编码信息只要遍历字符串中每个字符，从哈夫曼树中找到相应的叶子结点，取得相应的编码。最后再将所有找到的编码连接起来即可。 译码则是将编码串从左到右逐位判别，直到确定一个字符。这就是哈夫曼树的逆过程。 实验报告 （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别的条件不变,向小车上加钩课程设计实验报告 北邮
算法设计与分析实验报告贪心算法
现代设计黄金分割法复合形法实验报告word文档良心出品
计算机网络课程设计实验报告
北京理工大学《数据结构与算法设计》实验报告实验一
机电产品设计实验报告
算法设计实验报告一(简单算法设计)
北邮电路综合实验报告——串行口数据传输的仿真及硬件实现
算法设计与实验报告讲解
机电产品现代设计方法实验报告
算法设计实验报告
北邮移动通信实验报告
银行家算法设计实验报告
现代设计方法实验报告
算法设计与分析实验报告
数据结构 哈夫曼编码 实验报告
南京邮电大学算法设计实验报告——动态规划法
物体运动的方式实验报告
相关主题
文本预览