算法设计与分析实验报告.doc

实验报告题目实验一 递归与分治策略一、 实验目的 1加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握； 2提高学生利用课堂所学知识解决实际问题的能力； 3提高学生综合应用所学知识解决实际问题的能力。二、 实验内容设计一个递归和分治算法，找出数组的最大元素，找出x在数组A中出现的次数。三、 实验要求 （1）用分治法求解问题； （2）再选择自己熟悉的其它方法求解本问题； （3）上机实现所设计的所有算法；四、 实验过程设计（算法设计过程）1. 设计一个递归算法，找出数组的最大元素。2. 设计一个分治算法，找出x在数组A中出现的次数。3. 写一个主函数，调用上述算法。五、 实验结果分析（分析时空复杂性，设计测试用例及测试结果）时间复杂性：最好情况下，O(n)最坏情况下：O(nlog(n)空间复杂性分析：O(n)六、 实验体会 通过写递归与分治策略实验，更加清楚的知道它的运行机理，分治法解题的一般步骤：（1）分解，将要解决的问题划分成若干规模较小的同类问题；（2）求解，当子问题划分得足够小时，用较简单的方法解决；（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。做实验重在动手动脑，还是要多写写实验，才是硬道理。七、 附录：（源代码）#includestdio.h#define ElemType intint count(ElemType a,int i,int j,ElemType x)int k=0,mid; /k用来计数，记录数组中x出现的次数if(i=j)if(ai=x) k+;return k;elsemid=(i+j)/2;k+=count(a,i,mid,x);k+=count(a,mid+1,j,x);return k;ElemType Maxitem(ElemType a,int n)ElemType max=an-1,j;if(n=1)max=an-1;return max;else j=Maxitem(a,n-1); if(jmax) max=j;return max;void main(void)ElemType a=1,5,2,7,3,7,4,8,9,5,4,544,2,4,123;ElemType b;ElemType x;int n;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提高学生利用课堂所学知识解决实际问题的能力；3提高学生综合应用所学知识解决实际问题的能力。二实验内容根据实验目的要求和实验条件，由学生运用所学知识，自行选择最优问题，自己设计算法，自行编程实现、自行对实验结果进行分析，自行完成实验项目报告的撰写等。在教师的指导下，最大限度发挥学生资助学习的积极性，为后续专业课的学习打下坚实基础。三实验要求（1）用动态规划思想求解最优问题；（2）再选择自己熟悉的程序设计语言实现所有算法；（3）分析所设计的算法的时间/空间复杂性。四实验过程设计（算法设计过程）实验3.3。先在a，b数组中选a0和b0开始，然后分别计算在以a0和b0开始的总的时间，再比较哪个最短。五实验结果分析六实验体会始终觉得用代码写着比用笔直接计算要难点，不过代码解决的事一类问题，只需要输数据就可以。所以还是代码好，不过要有好的逻辑思维和方法，才能写出好的七附录：（源代码）#include stdio.h#include iostream.h#include string.hvoid main()void sf(int a,int b,int n);int a100,b100,n,i;printf(请输入需要完成的作业数量：);scanf(%d,&n);printf(请输入A组机器完成作业对应的时间:);for(i=0;in;i+)scanf(%d,&ai);printf(请输入B组机器完成作业对应的时间:);for(i=0;in;i+)scanf(%d,&bi);f(a,b,n);void f(int a,int b,int n)int max(int a,int b);int i,j,d,low,high,k,A,B,v100;for(i=0;in;i+)for(j=0;jn;j+)if(aiaj)d=ai;ai=aj;aj=d;d=bi;bi=bj;bj=d;for(i=0;in;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(bkbj)d=bk;bk=bj;bj=d;for(i=0;in;i+)A=0;B=0;j=0;while(j=i)A=A+aj;j+;while(jn)B=B+bj;j+;vi=max(A,B);i=1;d=v0;while(in)if(vib)return a;elsereturn b;实验三 贪心算法“0/1背包”及“有限期作业调度”一、实验目的1进一步理解算法设计的基本步骤及各步的主要内容、基本要求2加深对贪婪法算法设计方法的理解与应用3掌握将算法转化为计算机上机程序的方法4培养学生应用所学知识解决实际问题的能力。二实验内容（1）给定n种物品和一个背包。物品I的重量是wi，其价值为pi，背包的容量为M。应如何选择装入背包的物品（每件物品可以全装也可以只装一部分），使得装入背包中物品的总价值最大?（2）给定n个作业j1, j2, jn。对每个作业ji，有一个与之联系的限期di0和收益pi0， di， pi均为整数，1In。对作业ji，只有在限期di内完成，才能得到收益pi。假定只有一台处理机为这批服务业服务，处理机每次只能处理一个作业，并且完成一作业需一个单位时间。所谓一个可行解，是这批作业的一个子集J，J中每一作业均能在限期di内完成。调度的总收益是子集J中各作业收益之和。具有最大收益的的可行解和为最优解。如何求其最优解？三实验要求（1）设计用贪婪法求解“背包问题”及“带有限期的计算机作业调度问题”的算法；（2）上机实现所设计的算法；（3）分析所设计的算法的时间/空间复杂性。四实验过程设计（算法设计过程）后面人的等到时间等于前面人的服务时间，要总的等待时间最短，就要前面的服务时间最短，就需要先让服务时间段的人先进行服务。1.先按原来的顺序服务时间服务，得到一个等待时间2.升序排列后，得到一个等待时间五结果分析六实验体会后面人的等到时间等于前面人的服务时间，要总的等待时间最短，就要前面的服务时间最短，就需要先让服务时间段的人先进行服务。这是总的实验思路。贪心算法就是要尽可能的提高效率，得到想要的效益。七附录（源代码）#include stdio.h#include iostream.h#include string.hmain()int i,j,n,a100,d=0,k=0;printf(请输入顾客的总人数：);scanf(%d,&n);printf(依次输入每个顾客的服务时间:);for(i=0;in;i+)scanf(%d,&ai);for(i=0;in;i+)d=0;for(int j=0;ji;j+)d=d+aj;/第j个人的等待时间k=k+d;/总的等待时间printf(此时等待的总时间为：%dn,k);for(i=0;in;i+)for(int j=i;jaj)d=ai;ai=aj;aj=d;printf(按升序排列后的数组为：);for(i=0;in;i+)printf(%d,ai);k=0;for(i=0;in;i+)d=0;for(int j=0;ji;j+)d=d+aj;k=k+d; printf(n此时等待的总时间为：%dn,k);实验四 回溯法“N皇后”问题一、实验目的1掌握能用回溯法求解的问题应满足的条件；2加深对回溯法算法设计方法的理解与应用；3锻炼学生对程序跟踪调试能力；4通过本次实验的练习培养学生应用所学知识解决实际问题的能力。二实验内容由N2个方块排成N行N列的正方形，称为N元棋盘，在N元棋盘上放置N个皇后，如果某两个皇后位于N元棋盘的同一行或同一列或同一斜线（斜率为1）上，则称它们在互相攻击，试设计算法找出使N个皇后互不攻击的所有布局。三实验要求（1）用回溯法算法设计方法求解N元皇后问题（2）找出N皇后问题的互不攻击的所有解（3）皇后数N由键盘动态输入（4）上机实现所设计的算法；（5）分析所设计的算法的时间/空间复杂性。四实验过程设计（算法设计过程）（1）分析N皇后问题的约束条件，并将其显示化，选择存储结构建立相应的数学模型；（2）根据所建立的数学模型，设计求解该问题的粗略算法；（3）对所设计的粗略算法求精，得具体算法；（4）在C/C+/VC+下实现所设计的算法；（5）分屏显示结果；（6）分析运行结果的正确性；（7）进行算法效率分析；（8）课后写出实验报告。五实验结果和分析六实验体会解n后问题主要在于可行解，一个一个的试，（t）能走通就往(t+1)下走，走不通就倒回去(t-1)换条走，再不行再回走。就要不停的尝试，不停的回溯，直到找全可行解，或者一个也没有就停止。还有重要的事约束条件，两个皇后不能在同行同列或者斜线上。七附录（源代码）#include stdio.h#include iostream.h#include string.h#include int n; int x100;int sum=0;int k=1;int nQueen(int nn)n=nn;void backtrack(int t);for(int i=0;i=n;i+)xi=0;backtrack(1);return sum;int place(int k)for(int j=1;jn)printf(第%d个解的答案为： ,k);k+;sum+;for(int i=1;i=n;i+)printf(%d,xi);elsefor(int i=1;i=n;i+)xt=i;if(place(t)backtrack(t+1);main()int nn;printf(输入n皇后n值： );scanf(%d %d,&n,&n);nQueen(nn);