算法设计与分析试验报告

1、实验报告题目实验一递归与分治策略一、实验目的1 .加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2 .提高学生利用课堂所学知识解决实际问题的能力；3 .提高学生综合应用所学知识解决实际问题的能力。二、实验内容设计一个递归和分治算法，找出数组的最大元素，找出x在数组A中出现的次数。三、实验要求(1)用分治法求解问题；(2)再选择自己熟悉的其它方法求解本问题；(3)上机实现所设计的所有算法；四、实验过程设计(算法设计过程)1 .设计一个递归算法，找出数组的最大元素。2 .设计一个分治算法，找出x在数组A中出现的次数。3 .写一个主函数，调用上述算法。五、实验结果分析(分析

2、时空复杂性，设计测试用例及测试结果)时间复杂性：最好情况下，O(n)最坏情况下：O(nlog(n)空间复杂性分析：O(n)六、实验体会通过写递归与分治策略实验，更加清楚的知道它的运行机理，分治法解题的一般步骤：(1)分解，将要解决的问题划分成若干规模较小的同类问题；(2)求解，当子问题划分得足够小时，用较简单的方法解决；(3)合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。做实验重在动手动脑，还是要多写写实验，才是硬道理。七、附录：(源代码)#include"stdio.h"#defineElemTypeintintcount(ElemTypea,inti,int

3、j,ElemTypex)intk=0,mid;/k用来计数，记录数组中x出现的次数if(i=j)if(ai=x)k+;returnk;elsemid=(i+j)/2;k+=count(a,i,mid,x);k+=count(a,mid+1,j,x);returnk;ElemTypeMaxitem(ElemTypea,intn)ElemTypemax=an-1,j;if(n=1)max=an-1;returnmax;elsej=Maxitem(a,n-1);if(j>max)max=j;returnmax;)voidmain(void)(ElemTypea=1,5,2,7,3,7,4,8,

4、9,5,4,544,2,4,123;ElemTypeb;ElemTypex;intn;b=Maxitem(a,15);printf("数组的最大元素为dn",b);printf("输入想要计数的数组元素：n");scanf("%d",&x);n=count(a,0,14,x);printf("%d在数组中出现的次数为%d次n",x,n);实验二动态规划一一求解最优问题一、实验目的1 .加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2 .提高学生利用课堂所学知识解决实际问题的能力；

5、3 .提高学生综合应用所学知识解决实际问题的能力。二.实验内容根据实验目的要求和实验条件，由学生运用所学知识，自行选择最优问题，自己设计算法，自行编程实现、自行对实验结果进行分析，自行完成实验项目报告的撰写等。在教师的指导下，最大限度发挥学生资助学习的积极性，为后续专业课的学习打下坚实基础。三.实验要求(1)用动态规划思想求解最优问题;(2)再选择自己熟悉的程序设计语言实现所有算法;(3)分析所设计的算法的时间/空间复杂性。四.实验过程设计(算法设计过程)实验3.3。先在a,b数组中选a0和b0开始，然后分别计算在以a0和b0开始的总的时间，再比较哪个最短。五.实验结果分析六.实验体会始终觉得

6、用代码写着比用笔直接计算要难点，不过代码解决的事一类问题，只需要输数据就可以。所以还是代码好，不过要有好的逻辑思维和方法，才能写出好的七.附录：(源代码)#include"stdio.h"#include"iostream.h"#include"string.h"voidmain()voidsf(inta,intb,intn);inta100,b100,n,i;printf("请输入需要完成的作业数量：");scanf("%d",&n);printf("请输入A组机器完成作业对

7、应的时间：");for(i=0;i<n;i+)scanf("%d",&ai);printf("请输入B组机器完成作业对应的时间：");for(i=0;i<n;i+)scanf("%d",&bi);f(a,b,n);voidf(inta,intb,intn)intmax(inta,intb);inti,j,d,low,high,k,A,B,v100;for(i=0;i<n;i+)for(j=0;j<n;j+)if(ai<aj)d=ai;ai=aj;aj=d;d=bi;bi=bj;b

8、j=d;for(i=0;i<n;i+)low=i;high=i;while(ai=ai+1)i+;high=i;if(low!=high)for(k=low;k<=high;k+)for(j=k;j<=high;j+)if(bk<bj)d=bk;bk=bj;bj=d;)for(i=0;i<n;i+)(A=0;B=0;j=0;while(j<=i)(A=A+aj;j+;)while(j<n)(B=B+bj;j+;)vi=max(A,B);)i=1;d=v0;while(i<n)(if(vi<d)(d=vi;)i+;)printf("

9、最短作业时间为:%dn",d);)intmax(inta,intb)(if(a>b)(returna;)elsereturnb;实验三贪心算法一一“0/1背包”及“有限期作业调度”一、实验目的1 .进一步理解算法设计的基本步骤及各步的主要内容、基本要求2 .加深对贪婪法算法设计方法的理解与应用3 .掌握将算法转化为计算机上机程序的方法4 .培养学生应用所学知识解决实际问题的能力。二.实验内容(1)给定n种物品和一个背包。物品I的重量是w"其价值为pi,背包的容量为M。应如何选择装入背包的物品(每件物品可以全装也可以只装一部分)，使得装入背包中物品的总价值最大？(2)给

10、定n个作业j1,j2，jn。对每个作业ji，有一个与之联系的限期dj>0和收益Pi>0,dj,pi均为整数，1&I&n。对作业ji，只有在限期di内完成，才能得到收益Pi。假定只有一台处理机为这批服务业服务，处理机每次只能处理一个作业，并且完成一作业需一个单位时间。所谓一个可行解，是这批作业的一个子集J,J中每一作业均能在限期di内完成。调度的总收益是子集J中各作业收益之和。具有最大收益的的可行解和为最优解。如何求其最优解？三.实验要求(1)设计用贪婪法求解“背包问题”及“带有限期的计算机作业调度问题”的算法；(2)上机实现所设计的算法；（3）分析所设计的算法的时间

11、/空间复杂性。四.实验过程设计（算法设计过程）后面人的等到时间等于前面人的服务时间，要总的等待时间最短，就要前面的服务时间最短，就需要先让服务时间段的人先进行服务。1 .先按原来的顺序服务时间服务，得到一个等待时间2 .升序排列后，得到一个等待时间五.结果分析*工:存习归尊机.作蛆整法mbugM法，w的昌后昌ke士毫列的yanXi擘IW¥2026064/?:5s2旬六.实验体会后面人的等到时间等于前面人的服务时间，要总的等待时间最短，就要前面的服务时间最短，就需要先让服务时间段的人先进行服务。这是总的实验思路。贪心算法就是要尽可能的提高效率，得到想要的效益。七.附录（源代码）#inc

12、lude"stdio.h"#include"iostream.h"#include"string.h"main()inti,j,n,a100,d=0,k=0;printf("请输入顾客的总人数：")；scanf("%d",&n);printf("依次输入每个顾客的服务时间：");for(i=0;i<n;i+)scanf("%d",&ai);for(i=0;i<n;i+)(d=0;for(intj=0；j<i；j+)(d=d

13、+aj;/第j个人的等待时间)k=k+d;/总的等待时间)printf("此时等待的总时间为：%dn",k);for(i=0;i<n;i+)(for(intj=i;j<n;j+)(if(ai>aj)(d=ai;ai=aj;aj=d;)printf("按升序排列后的数组为：");for(i=0;i<n;i+)printf("%d",ai);k=0;for(i=0;i<n;i+)(d=0;for(intj=0;j<i;j+)(d=d+aj;)k=k+d;)printf("n此时等待的总时间为：

14、%dn",k);)实验四回溯法一一“N皇后”问题一、实验目的1 .掌握能用回溯法求解的问题应满足的条件；2 .加深对回溯法算法设计方法的理解与应用；3 .锻炼学生对程序跟踪调试能力；4 .通过本次实验的练习培养学生应用所学知识解决实际问题的能力。2 .实验内容由N2个方块排成N行N列的正方形，称为N元棋盘，在N元棋盘上放置N个皇后，如果某两个皇后位于N元棋盘的同一行或同一列或同一斜线(斜率为土)上，则称它们在互相攻击，试设计算法找出使N个皇后互不攻击的所有布局。3 .实验要求(1)用回溯法算法设计方法求解N元皇后问题(2)找出N皇后问题的互不攻击的所有解(3)皇后数N由键盘动态输入(

15、4)上机实现所设计的算法；(5)分析所设计的算法的时间/空间复杂性。四.实验过程设计(算法设计过程)(1)分析N皇后问题的约束条件，并将其显示化，选择存储结构建立相应的数学模型；(2)根据所建立的数学模型，设计求解该问题的粗略算法；(3)对所设计的粗略算法求精，得具体算法；(4)在C/C+/VC+下实现所设计的算法；(5)分屏显示结果；(6)分析运行结果的正确性；(7)进行算法效率分析；(8)课后写出实验报告。五.实验结果和分析'学习V十菖机作业、售法Debug，肖去cxe"输入n皇后n值士44灯向yjdu&hn孕车aAs-L12e第第咋为为t24133142cont

16、inue.六.实验体会解n后问题主要在于可行解，一个一个的试，(t)能走通就往(t+1)下走，走不通就倒回去(t-1)换条走，再不行再回走。就要不停的尝试，不停的回溯，直到找全可行解，或者一个也没有就停止。还有重要的事约束条件，两个皇后不能在同行同列或者斜线上。七.附录(源代码)#include"stdio.h"#include"iostream.h"#include"string.h"#include<cmath>intn;intx100;intsum=0;intk=1;intnQueen(intnn)n=nn;voidbacktrack(intt);for(inti=0;i<=n;i+)xi=0;backtrack(1);returnsum;intplace(intk)for(intj=1;j<k;j+)(if(abs(k-j)=abs(xj-xk)|(xj=xk)(return0;return1;voidbacktrack(intt)(i