院系：计算机科学学院
专业：计算机科学与技术
年级： 2010级
课程名称：算法设计与分析基础
班号：
组号： 3 指导教师：邢光林
2012年 12月 30 日
组员
学号姓名
实验名称算法实验整体框架的构建实验室9#205
实验目的或要求1. 实验题目
算法实验主菜单的设计。
2．实验目的
⑴熟悉实验环境VC＋＋6.0；
⑵复习C、C++语言以及数据结构课程的相关知识，实现课程间的平滑过度；
3. 实验要求
1）设计的主菜单可以是图形模式的，也可以是控制台模式的。以控制台为例，主菜单大致如下：
－－－－－－－－－－－－－－－－－－－－－－－－－
《算法设计与分析》实验
－－－－－－－－－－－－－－－－－－－－－－－－－
1.算法分析基础——Fibonacci序列问题
2.分治法在数值问题中的应用——最近点对问题
3.减治法在组合问题中的应用——8枚硬币问题
4.变治法在排序问题中的应用——堆排序问题
5.动态规划法在图问题中的应用——全源最短路径问题
99. 退出本实验
－－－－－－－－－－－－－－－－－－－－－－－－－
请输入您所要执行的操作（1，2，3，4，5，99）：
2）点击操作后进入相应的实验项目或是相应项目的下一级菜单；
3）可以反复执行，直到退出实验。
程序代码void menu();
int main()
{
Fibonacci fibonacciImpl;
Heapsort heapsortImpl;
Martrix martrixImpl;
Thecoin thecoinImpl;
int chose;
menu();
cin>>chose;
while(chose!=99)
{
switch(chose)
{
case 1:{fibonacciImpl.fib1();cout< case 3:{thecoinImpl.Fake_coin();break;} case 4:{heapsortImpl.heapsort();break;} case 5:{break;} default:cout<<"请按序号输入操作"< } menu(); cin>>chose; } return 0; } void menu() { cout<<"---------------------------------------"< cout<<" 《《算法设计与分析》》实验"< cout<<"---------------------------------------"< cout<<"1. 算法分析基础——Fibonacci序列问题"< cout<<"2. 分治法在数值问题中的应用——矩阵相乘问题"< cout<<"3. 减治法在组合问题中的应用——8枚硬币问题"< cout<<"4. 变治法在排序问题中的应用——堆排序问题"< cout<<"5. 动态规划法在图问题中的应用——全源最短路径问题"< cout<<"99.退出本实验"< } 实 验 结 果 及 分 析 实验名称算法分析基础——Fibonacci序列问 题 实验室9#205 实验目的或要求 实验题目 给定一个非负整数n，计算第n个Fibonacci数 实验目的 1）理解递归算法和迭代算法的设计思想以及递归程序的调式技术 2）掌握并应用递归算法和迭代算法效率的理论分析(前验分析)和实际分析(后验分析)方法； 3）理解这样一个观点：不同的算法可以解决相同的问题，这些算法的解题思路不同，复杂程度不同，效率也不同； 实验要求 1）使用教材2.5节中介绍的迭代算法Fib(n),找出最大的n,使得第n个Fibonacci 数不超过计算机所能表示的最大整数，并给出具体的执行时间； 2）对于要求1),使用教材2.5节中介绍的递归算法F(n)进行计算,同样给出具体的执行时间，并同1)的执行时间进行比较； 3）对于输入同样的非负整数n，比较上述两种算法基本操作的执行次数； 4）对1)中的迭代算法进行改进，使得改进后的迭代算法其空间复杂度为Θ(1)； 5）设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。 实验原理（算法基本思想）1、递归法基本思想 递归就是定义一个函数，让它自己调用自己。 Fib（int n） //输入整数n，输出第n个斐波那契数 {if(n=0)return 0; Else if(n=1)return 1; Else return Fib(n-1)+Fib(n-2) } 2、迭代法 这种方法相对于递归法来说在时间复杂度上减小了不少，但代码相对就要复杂些了。Fib（int n） //输入整数n，输出第n个斐波那契数 {if(n=0)return 0; Else if(n=1)return 1; Else F0←0; F1←1; for(i=2;i { F2=f1+f0; //f1表示当前的值 F0←F1 F1←F2; } Return F2; } 程序代码//Fibonacci数列 #ifndef FINBONACCI_H //头文件 #define FINBONACCI_H class Fibonacci{ public: double fibonacci(int i,int& count); //计算fibonacci int fib2(); int fib1(); }; #endif int Fibonacci::fib2() { int i=1; double fib=0; int count; double x=INT_MAX; while(fib { i++; count=1; fib=fibonacci(i,count); cout< } cout<<"使用迭代算法时"< cout<<"第"< cout<<"总共进行了"< return 0; } int Fibonacci::fib1() { double fib=0; double a=0; double b=1; int count=0; double x=INT_MAX; int i; for(i=1;fib { fib=a+b; a=b; b=fib; count++; } i--; cout<<"使用迭代算法时"< cout<<"第"< cout<<"共做"< return 0; } double Fibonacci::fibonacci(int i,int& count) { count++; if(i<=1) return 1; return (fibonacci(i-1,count)+fibonacci(i-2,count)); } 实验 结果及分析通过比较两种方法求Fibonacci数列所用的时间，可以发现迭代法的效率明显高于递归法。同时也明白了不同的算法可以解决相同的问题，这些算法的解题思路不同，复杂程度不同，效率也不同。 实验名称分治法在数值问题中的应用 ——矩阵相乘问题 实验室9#205 实验目的或要求 实验题目 设M1和M2是两个n×n的矩阵，设计算法计算M1×M2的乘积。 实验目的 1）提高应用蛮力法设计算法的技能； 2）深刻理解并掌握分治法的设计思想； 3）理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对其进行改进，以提高算法的效率。 实验要求 1）设计并实现用BF方法求解矩阵相乘问题的算法； 2）设计并实现用DAC方法求解矩阵相乘问题的算法； 3）以上两种算法的输入既可以手动输入，也可以自动生成； 4）对上述两个算法进行时间复杂性分析，并设计实验程序验证 分析结果； 5）设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。 实验原理（算法基本思想） 1）蛮力法求解 蛮力法比较简单，直接使用矩阵相乘公式计算矩阵的每行每列的值，很容易就能得出答案 2）分治法求解 分治法思想 将问题实例划分为同一问题的几个较小的实例。对这些较小实例求解，通常使用递归方法，但在问题规模足够小时，也会使用另一种算法。如果有必要，合并这些问题的解，以得到原始问题的解。 求解矩阵相乘的DAC算法，使用了strassen算法。 DAC（A[]，B[]，n） { If n=2 使用7次乘法的方法求得解 Else Divide（A）//把A分成4块 Divide（B）//把B分成4块 调用7次strassen算法求得解的4块 合并这4块得到解并返回 } 程序代码//矩阵相乘问题 #ifndef MARTRIX_H #define MARTRIX_H struct TSMartrix { int data[100][100]; int mu;//矩阵的行数 int nu;//矩阵的列数 }; class Martrix{ public: void martrix() ; //随机生成一个矩阵 void Rand_CreateSMartrix(struct TSMartrix &M); //输出矩阵到控制台 void OutputSMartrix(struct TSMartrix M); //分治法--两个矩阵相乘 void DAC_MultSMatrix(struct TSMartrix M,struct TSMartrix N,struct TSMartrix &Q); //分割矩阵 void divide(struct TSMartrix M,struct TSMartrix &M00,struct TSMartrix &M01,struct TSMartrix &M10,struct TSMartrix &M11); //合并矩阵 void merge(struct TSMartrix &Q,struct TSMartrix M00,struct TSMartrix M01,struct TSMartrix M10,struct TSMartrix M11); //矩阵相加 struct TSMartrix AddSMatrix(struct TSMartrix M,struct TSMartrix N); //矩阵相减 struct TSMartrix SubSMatrix(struct TSMartrix M,struct TSMartrix N); private: struct TSMartrix M00,M01,M10,M11; struct TSMartrix N00,N01,N10,N11; struct TSMartrix Q00,Q01,Q10,Q11; struct TSMartrix s1,s2,s3,s4,s5,s6,s7; }; #endif void Martrix::martrix() { long start,end; struct TSMartrix M,N,Q; do { Rand_CreateSMartrix(M); Rand_CreateSMartrix(N); if(M.mu!=N.mu||M.mu!=M.nu||N.mu!=N.nu) printf("两个矩阵不同维，无法用分治法!!!\n"); }while(M.nu!=N.mu||M.mu!=M.nu||N.mu!=N.nu); Q.mu=M.mu; Q.nu=M.mu; start=clock(); DAC_MultSMatrix(M,N,Q); end=clock(); printf("矩阵M：\n"); OutputSMartrix(M); printf("矩阵N：\n"); OutputSMartrix(N); printf("矩阵M*N：\n"); OutputSMartrix(Q); printf("历时%ld毫秒\n",end-start); } //随机生成一个矩阵 void Martrix::Rand_CreateSMartrix(struct TSMartrix &M) { int i,j; printf("请输入矩阵的行数，列数："); scanf("%d%d",&M.mu,&M.nu); srand((unsigned)time(NULL)); for(i=0;i for(j=0;j M.data[i][j]=rand()%10; printf("生成成功!\n"); } //输出矩阵 void Martrix::OutputSMartrix(struct TSMartrix M) { int i,j; for(i=0;i { for(j=0;j printf("%-5d",M.data[i][j]); puts("\n"); } } //分治法--两个矩阵相乘 void Martrix::DAC_MultSMatrix(struct TSMartrix M,struct TSMartrix N,struct TSMartrix &Q) { int n=M.mu; if(n==2) { int m1,m2,m3,m4,m5,m6,m7; m1=(M.data[0][0]+M.data[1][1])*(N.data[0][0]+N.data[1][1]); m2=(M.data[1][0]+M.data[1][1])*N.data[0][0]; m3=M.data[0][0]*(N.data[0][1]-N.data[1][1]); m4=M.data[1][1]*(N.data[1][0]-N.data[0][0]); m5=(M.data[0][0]+M.data[0][1])*N.data[1][1]; m6=(M.data[1][0]-M.data[0][0])*(N.data[0][0]+N.data[0][1]); m7=(M.data[0][1]-M.data[1][1])*(N.data[1][0]+N.data[1][1]); Q.data[0][0]=m1+m4-m5+m7; Q.data[0][1]=m3+m5; Q.data[1][0]=m2+m4; Q.data[1][1]=m1+m3-m2+m6; } else { n=n/2; M00.mu=M01.mu=M10.mu=M11.mu=M00.nu=M01.nu=M10.nu=M11.nu=N00.mu=N01.mu=N10.mu=N11.mu=N0 0.nu=N01.nu=N10.nu=N11.nu=n; s1.mu=s1.nu=s2.mu=s2.nu=s3.mu=s3.nu=s4.mu=s4.nu=s5.mu=s5.nu=s6.mu=s6.nu=s7.mu=s7.nu=n; divide(M,M00,M01,M10,M11); divide(N,N00,N01,N10,N11); DAC_MultSMatrix(AddSMatrix(M00,M11),AddSMatrix(N00,N11),s1); DAC_MultSMatrix(AddSMatrix(M10,M11),N00,s2); DAC_MultSMatrix(M00,SubSMatrix(N01,N11),s3); DAC_MultSMatrix(M11,SubSMatrix(N10,N00),s4); DAC_MultSMatrix(AddSMatrix(M00,M01),N11,s5); DAC_MultSMatrix(SubSMatrix(M10,M00),AddSMatrix(N00,N01),s6); DAC_MultSMatrix(SubSMatrix(M01,M11),AddSMatrix(N10,N11),s7); Q00=AddSMatrix(s1,AddSMatrix(s4,SubSMatrix(s7,s5))); Q01=AddSMatrix(s3,s5); Q10=AddSMatrix(s2,s4); Q11=AddSMatrix(s1,AddSMatrix(s3,SubSMatrix(s6,s2))); merge(Q,Q00,Q01,Q10,Q11); } } //分割矩阵 void Martrix::divide(struct TSMartrix M,struct TSMartrix &M00,struct TSMartrix &M01,struct TSMartrix &M10,struct TSMartrix &M11) { int n=M00.mu; int i,j; for(i=0;i for(j=0;j { M00.data[i][j]=M.data[i][j]; M01.data[i][j]=M.data[i][n+j]; M10.data[i][j]=M.data[n+i][j]; M11.data[i][j]=M.data[n+i][j+n]; } } //合并矩阵 void Martrix::merge(struct TSMartrix &Q,struct TSMartrix M00,struct TSMartrix M01,struct TSMartrix M10,struct TSMartrix M11) { int n=M00.mu; int i,j; for(i=0;i for(j=0;j { Q.data[i][j]=M00.data[i][j]; Q.data[i][j+n]=M01.data[i][j]; Q.data[i+n][j]=M10.data[i][j]; Q.data[i+n][j+n]=M11.data[i][j]; } } //矩阵相加 struct Martrix::TSMartrix AddSMatrix(struct TSMartrix M,struct TSMartrix N) { struct TSMartrix Q; int n=M.mu; int i,j; Q.mu=Q.nu=n; for(i=0;i for(j=0;j Q.data[i][j]=M.data[i][j]+N.data[i][j]; return Q; } //矩阵相减 struct Martrix::TSMartrix SubSMatrix(struct TSMartrix M,struct TSMartrix N) { struct TSMartrix Q; int n=M.mu; int i,j; Q.mu=Q.nu=n; for(i=0;i for(j=0;j Q.data[i][j]=M.data[i][j]-N.data[i][j]; return Q; } 实 验结果及分析经过这个实验，我明白了蛮力法几乎可以解决所有的问题，但是算法的效率不高。对蛮力法进行改进，经过适当的努力后，算法的效率可以得到提高 实验名称减治法在组合问题中的应用——8枚 硬币问题 实验室9#205 实验目的或要求 实验题目 在8枚外观相同的硬币中，有一枚是假币，并且已知假币与真币的重量不同，但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，设计一个高效的算法来检测这枚假币。 实验目的 1）深刻理解并掌握减治法的设计思想并理解它与分治法的区别； 2）提高应用减治法设计算法的技能。 3）理解这样一个观点：建立正角的模型对于问题的求解是非常重要的。 实验要求 1）设计减治算法实现8枚硬币问题； 2）设计实验程序，考察用减治技术设计的算法是否高效； 3）扩展算法，使之能处理n枚硬币中有一枚假币的问题。 实验原理（算法基本思想） 减治法主要有三种变种 减去一个常量 减去一个常量因子 减可变规模 与分治法的区别：分治法把实例分为几部分分别求解减治法把实例的规模减为一个更小的实例求解 A（n）//输入硬币个数n，要求必须有假币且已知假币只有1个（假设更重） {if n=1,这枚就是假币 Else if n=2，较重的那枚是假币 Else 把n个硬币分为3份，2份相等，另一份与这2份的相差个数尽可能小 称2份个数相等的 If这2份重量相等，假币在第3堆中，对第3堆使用该算法 Else 在较重的那堆中，对该堆硬币使用该算法 } 程序代码//假币问题 #ifndef THECOIN_H #define THECOIN_H //用减治法处理假币问题 class Thecoin{ public: void Fake_coin(); int Fake_coin_DC(int array[],double n,int num); private: int flag; }; #endif void Thecoin::Fake_coin() { int n,array[100]; printf("输入硬币个数:"); scanf("%d",&n); flag=n; for(int i=0;i {printf("输入第%d硬币的重量:",i+1); scanf("%d",&array[i]); } Fake_coin_DC(array,n,0); } int Thecoin::Fake_coin_DC(int array[],double n,int num) { if(n>=4) { double key; int i=0,k=0,m=0,u=0; key=ceil(n/3); for(i=num;i<=num+key-1;i++)//3分 k=k+array[i]; for(i;i<=num+2*key-1;i++) m=m+array[i]; for(i;i<=num+n-1;i++) u=+array[i]; if(abs(k-m)>0) { Fake_coin_DC(array,key,num); Fake_coin_DC(array,key,num+key); } else Fake_coin_DC(array,n-num-2*key,num+2*key); } else { if(n==3) { if(array[num]!=array[num+1]) { if(abs(array[num]-array[num+2]>0)) {printf("第%d枚是假币",num+1); d(num+1,array);} else {printf("第%d枚是假币",num+2);d(num+2,array);} } else if(array[num]!=array[num+2]) {printf("第%d枚是假币",num+3);d(num+3,array);} } if(n==2) { if(abs(array[num]-array[num+1])>0) { if(num==0) {if(abs(array[0]-array[2])>0) {printf("第%d枚是假币",num+1);d(num+1,array);} else {printf("第%d枚是假币",num+2);d(num+2,array);} } if(num+1==flag-1) { if(abs(array[num-1]-array[num+1])>0) {printf("第%d枚是假币",num+2);d(num+2,array);} if(abs(array[num-1]-array[num])>0) {printf("第%d枚是假币",num+1);d(num+1,array);} } if(num+1!=flag-1&&num!=0) { if(abs(array[num]-array[num+2])>0) {printf("第%d枚是假币",num+1);d(num+1,array);} if(abs(array[num+1]-array[num+2])>0) {printf("第%d枚是假币",num+2);d(num+2,array);} } } } if(n==1&&(abs(array[num]-array[num-1])>0)) {printf("第%d枚是假币",num+1);d(num+1,array);} } return 0;} void d(int m,int array[]) { if(m==1&&array[0] else if(m==1) printf("且假币重量大于真币.\n"); if(m!=1&&array[m-1] else if(m!=1) printf("且假币重量大于真币.\n"); } 实验结果及分析通过这个实验，理解并掌握了减治法的设计思想并理解了它与分治法的区别。在写这个算法前，一定要建立正确的求解模型。 1、设计是创造性的劳动，设计的本质是创新。 2、现代设计方法有六个特点,分别是:程式性、创造性、系统性、优化性、综合性、计算机辅助设计（CAD）。 3、传统的分析方法往往把事物分解为许多独立的互不相干的部分进行研究。由于是孤立、静止地分析问题，所得的结论往往是片面的、有局限性的。而系统工程的方法是把事物当作一个整体的系统来研究，从系统出发，分析各组成部分之间的有机联系及系统与外界环境的关系，是一种较全面的综合研究方法。 4、设计系统是一种信息处理系统。 5、系统工程的观点，设计系统是一个由时间维、逻辑维和方法维组成三维系统。时间维：反映按时间顺序的设计工作阶段；逻辑维：解决问题的逻辑步骤；方法维：设计过程中的各种思维方法和工作方法。 6、设计工作阶段—时间维一般工程设计可分为四个阶段： 1）产品规划（明确设计任务）；2）原理方案设计；3）技术设计；4）施工设计。产品规划过程中的调查研究，包括：市场调研、技术调研、社会调研、环境调研。产品规划阶段形成的是可行性研究报告或设计任务书。 原理方案设计形成方案原理图。技术设计阶段形成零件草图等。 施工设计阶段形成零件图、部件装配图、全部生产图纸、设计说明书、工艺文件、使用说明书。 7、产品设计的三种类型 （1）开发型设计针对设计任务提出新的功能原理方案，完成从产品规划到施工设计的全过程的设计，此类设计是创新设计。 （2）适应型设计在原理方案基本保持不变的情况下，变化更换部分部件或结构，使产品更广泛地适应使用要求的设计。 （3）变参数型设计产品功能、原理方案、结构型式基本确定，通过改变尺寸与性能参数，满足不同的工作需要的设计。（测绘与仿制） 8、解决问题的合理逻辑步骤是：分析-综合-评价-决策。 评价是筛选的过程二、原理方案设计 1、系统功能分析法—系统化设计方法，它是将工程设计任务或机械产品看作技术系统，用系统工程方法进行分析和综合。 2、技术系统—以一定技术手段来实现社会特定需求的人造系统。 技术系统的功能就是将输入的能量、物料和讯号进行有目的的转换或变化后输出。技术系统是一个转换装置。随时间变化的能量、物料和讯号称为能量流、物料流和讯号流。 主要传递讯号流的技术系统—仪器。 主要传递能量流与物料流的技术系统—机器。 3、对输入和输出的变换所作的抽象描述称为系统。 技术系统的用途或所具有的特定能力称为系统的功能 4、分析系统的总功能常采用“黑箱法”。分析比较系统的输入和输出能量、物料和讯号，其差别和关系反映的就是系统的总功能。黑箱法要求设计者不要首先从产品结构着手，而应从系统功能出发设计产品。 5、功能分解分解到直接找到解法的分功能称为功能元。功能分析的结果用功能树的形式表达 完成分功能的技术实体是功能载体。 6、求系统原理解N=n1·n2······ni······nm 式中：m—功能元数；ni—第i 种功能元解的个数。 7、功能分析法的设计步骤 算法设计与分析实验报告 贪心算法 班级：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] 中国地质大学研究生课程论文封面 课程名称现代设计方法 教师姓名 研究生姓名 研究生学号 研究生专业机械工程 所在院系机电学院 日期: 2013 年 1 月 8 日 评语 注：1、无评阅人签名成绩无效； 2、必须用钢笔或圆珠笔批阅，用铅笔阅卷无效； 3、如有平时成绩，必须在上面评分表中标出，并计算入总成绩。 有限元分析简介 摘要: ANSYS 软件具有建模简单、快速、方便的特点, 因而成为大型通用有限元程序的代表。对有限元作了一个总体的介绍, 并着重介绍了ANSYS 软件, 简要地叙述了ANSYS 软件的主要技术特点和各部分构成以及其主要的分析功能,从其构成及功能中可以看到,ANSYS 软件的确是工程应用分析的有效工具。 1、有限元分析的基本概念和计算步骤 1.1、有限元分析的基本概念 有人将CAE技术称为当今“科学与技术的完美结合”。这句话说得比较夸张，但不可否认，CAE技术的确是现代产品研发的重要基础技术，其理论性和需要的学科知识厚重而宽广。有限元软件是目前CAE的主流分析软件之一，在全球拥有最大的用户群。有限元分析（FEA，Finite Element Analysis）利用数学近似的方法对真实物理系统（几何和载荷工况）进行模拟。还利用简单而又相互作用的元素，即单元，就可以用有限数量的未知量去逼近无限未知量的真实系统。 有限元分析的基本概念是用较简单的问题代替复杂问题后再求解。它将求解域看成是由许多称为有限元的小的互连子域组成，对每一单元假定一个合适的(较简单的）近似解，然后推导求解这个域总的满足条件(如结构的平衡条件），从而得到问题的解。这个解不是准确解，而是近似解，因为实际问题被较简单的问题所代替。由于大多数实际问题难以得到准确解，而有限元不仅计算精度高，而且能适应各种复杂形状，因而成为行之有效的工程分析手段。 有限元是那些集合在一起能够表示实际连续域的离散单元。有限元的概念早在几个世纪前就已产生并得到了应用，例如用多边形（有限个直线单元）逼近圆来求得圆的周长，但作为一种方法而被提出，则是最近的事。有限元法最初被称为矩阵近似方法，应用于航空器的结构强度计算，并由于其方便性、实用性和有效性而引起从事力学研究的科学家的浓厚兴趣。经过短短数十年的努力，随着计算机技术的快速发展和普及，有限元方法迅速从结构工程强度分析计算扩展到几乎所有的科学技术领域，成为一种丰富多彩、应用广泛并且实用高效的数值分析方法。 《数据结构与算法设计》 实验报告 ——实验一 学院： 班级： 学号： 姓名： 一、实验目的 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个整数序列，整数之间用一个空格隔开。 输出：对于每个测试例输出两行，分别表示新生成的整数集合。其中，第一行是元素和比较小的整数集合，第二行是元素和比较大的整数集合，整数之间用一个空格隔开。两个测 学习“现代设计方法”课程感想 11材料2班夏万林学号20110410210234 现代设计方法，用英文取名为“Modern Design Technique”，是当今时代为产品制造或工程项目完成到实体化全过程而制订的技术上的方案、图样与程序。“现代设计方法”是对应于传统设计方法而提出与发展的，为一种大概念，有大的范畴，其下位可有现代机械设计方法、现代模具设计方法等。 进入大三，迎接我们的是真正的专业课，不再是以前的公共课或者是专业基础课，而《优化设计导论》作为专业课中的必修课，即是非常重要的一门课，同时也是一门结合机械类各科目知识的一门综合性课程。在近一学期的学习中，我不仅仅是学到了比较多的综合性设计方法同时也很好的认识了我们的好老师-卢老师。卢老师的课堂教学非常幽默且具有非常强的科学性。卢老师基本上是每节课都会要求同学自己动手画画做做，不要总是这样听着而什么是事都不做，尽量调动大家学习的积极性，让大家多学点，让同学愿意听，想去学。 这门课程给我们讲解了有限元设计、优化设计、机电一体化设计、计算机辅助设计、创新设计、生命周期设计、虚拟设计、稳健设计、并行设计、智能设计等十种现代设计方法。其中前面四种为较成熟应用正普及类，后面六种为较新颖内容正发展类，可以说是设计学的一个大综合。广义最优化方法有解析法、数值法、图解法、实验法、情况研究法等，工程技术问题中的最优化方法主要是指解析法和数值法，且以数值法为最典型、最具代表性，因此、本书主要讲述数值法。 纵观世界机械类设计发展历史，从19世纪中叶英国工业革命至今，机械工业不断革新其要求也不断改变，现今对各个设计员的要求不断提升，由以前的单一机械结构设计到后来的机电一体化再到如今的机、电、计算机三位一体的设计要求，这样对于我们大学生尤其是三本院校的大学生，本身基础较薄弱，学习现代设计要求也不断提高、相应的难度也在提升。 通过这半个学期的学习，自己对现代设计方法有了一定的认知和掌握。我觉得开设本课程要达到的主要目的是：通过对经典解析法、线性规划与非线性规划法、数值法中的基本概念、理论和方法的学习，对工程设计实例分析的了解和熟悉，我们可以拓宽视野，增强创新设计意识，掌握现代设计方法的基本思想和基本方法，初步具有解决机械优化设计和分析问题的能力。学校的图书馆也有许多相关的书籍期刊，通过课本的学习和课外知识的学习以及《机械设计》课程学习的基础，我对设计过程的复杂性和相关基础过程有了一定的认识，其过程主要为首先是任务的提出，确定需求和潜在的需求；然后是可理解的形成，即概念设计，包括扫描技术可能和产生矛盾统一设想；最后是对可能解的评估、优选和确认，并产生最终解。通过这门课程的学习我还解决了另一个问题，对机械设计的现代设计方法的相关类型有了一定的认识。通过课程中的优化设计、解析法、数值法等方面的学习我深刻的认识到现代设计方法主要基于以下四个类型开展设计方案的。主要是结构模块化设计方法、基于产品特征知识的设计方法、系统化设计方法、智能化设计方法四个方面的设计方法，我的学习提 算法设计与分析实验报告 学院：信息学院 专业：物联网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、问题的描述 为了考察铆钉在冲压时，发生多大的变形，对铆钉进行分析。 铆钉圆柱高：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 银行家算法设计实验报告 银行家算法设计实验报告 一．题目分析 1.银行家算法： 我们可以把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求资源相当于客户向银行家贷款。操作系统按银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程尚需求的资源量，若是系统现存的资源可以满足它尚需求的资源量，则按当前的申请量来分配资源，否则就推迟分配。 当进程在执行中继续申请资源时，先测试该进程申请的资源量是否超过了它尚需的资源量。若超过则拒绝分配，若没有超过则再测试系统尚存的资源是否满足该进程尚需的资源量，若满足即可按当前的申请量来分配，若不满足亦推迟分配。 2.基本要求： （1）可以输入某系统的资源以及T0时刻进程对资源的占用及需求情况的表项，以及T0时刻系统的可利用资源数。 （2）对T0时刻的进行安全性检测，即检测在T0时刻该状态是否安全。 （3）进程申请资源，用银行家算法对其进行检测，分为以下三种情况： A. 所申请的资源大于其所需资源，提示分配不合理不予分配并返回 B. 所申请的资源未大于其所需资源， 但大于系统此时的可利用资源，提 示分配不合理不予分配并返回。 C. 所申请的资源未大于其所需资源， 亦未大于系统此时的可利用资源，预 分配并进行安全性检查： a. 预分配后系统是安全的，将该进 程所申请的资源予以实际分配并 打印后返回。 b. 与分配后系统进入不安全状态，提示系统不安全并返回。 （4）对输入进行检查，即若输入不符合条件，应当报错并返回重新输入。 3.目的： 根据设计题目的要求，充分地分析和理解题 目，叙述系统的要求，明确程序要求实现的功能以及限制条件。 明白自己需要用代码实现的功能，清楚编写每部分代码的目的，做到有的放矢，有条理不遗漏的用代码实现银行家算法。 本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼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学年第二学期研究生课程考核 （读书报告、研究报告） 考核科目：现代设计方法及理论 学生所在院（系）：机电学院 学生所在学科：机械制造及其自动化 题目：机械产品方案的现代设计方法及发展趋势 第 1 页（共 6 页）机械产品方案的现代设计方法及发展趋势 科学技术的飞速发展，产品功能要求的日益增多，复杂性增加，寿命期缩短，更新换代速度加快。然而，产品的设计，尤其是机械产品方案的设计手段，则显得力不从心，跟不上时代发展的需要。目前，计算机辅助产品的设计绘图、设计计算、加工制造、生产规划已得到了比较广泛和深入的研究，并初见成效，而产品开发初期方案的计算机辅助设计却远远不能满足设计的需要。为此，作者在阅读了大量文献的基础上，概括总结了国内外设计学者进行方案设计时采用的方法，并讨论了各种方法之间的有机联系和机械产品方案设计计算机实现的发展趋势。 根据目前国内外设计学者进行机械产品方案设计所用方法的主要特征，可以将方案的现代设计方法概括为下述四大类型。 1、系统化设计方法 系统化设计方法的主要特点是：将设计看成由若干个设计要素组成的一个系统，每个设计要素具有独立性，各个要素间存在着有机的联系，并具有层次性，所有的设计要素结合后，即可实现设计系统所需完成的任务。 系统化设计思想于70年代由德国学者Pahl和Beitz教授提出，他们以系统理论为基础，制订了设计的一般模式，倡导设计工作应具备条理性。德国工程师协会在这一设计思想的基础上，制订出标准VDI2221“技术系统和产品的开发设计方法。 制定的机械产品方案设计进程模式，基本上沿用了德国标准VDI2221的设计方式。除此之外，我国许多设计学者在进行产品方案设计时还借鉴和引用了其他发达国家的系统化设计思想，其中具有代表性的是： (1)将用户需求作为产品功能特征构思、结构设计和零件设计、工艺规划、作业控制等的基础，从产品开发的宏观过程出发，利用质量功能布置方法，系统地将用户需求信息合理而有效地转换为产品开发各阶段的技术目标和作业控制规程的方法。 (2)将产品看作有机体层次上的生命系统，并借助于生命系统理论，把产品的设计过程划分成功能需求层次、实现功能要求的概念层次和产品的具体设计层次。同时采用了生命系统图符抽象地表达产品的功能要求，形成产品功能系统结构。 (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现代设计方法期末总结
算法设计与分析实验报告贪心算法
现代设计黄金分割法复合形法实验报告word文档良心出品
现代设计方法-有限元分析报告
北京理工大学《数据结构与算法设计》实验报告实验一
机电产品设计实验报告
算法设计实验报告一(简单算法设计)
学习“现代设计方法”课程感想
算法设计与实验报告讲解
机电产品现代设计方法实验报告
算法设计实验报告
现代设计方法实验报告
银行家算法设计实验报告
算法设计与分析实验报告
现代设计方法及理论
南京邮电大学算法设计实验报告——动态规划法
物体运动的方式实验报告
《算法设计与分析》实验报告
相关主题
文本预览