实验报告题目实验一递归与分治策略一、实验目的1．加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2．提高学生利用课堂所学知识解决实际问题的能力；3．提高学生综合应用所学知识解决实际问题的能力。
二、实验内容设计一个递归和分治算法，找出数组的最大元素，找出x在数组A中出现的次数。
三、实验要求（1）用分治法求解…问题；（2）再选择自己熟悉的其它方法求解本问题；（3）上机实现所设计的所有算法；四、实验过程设计（算法设计过程）1.设计一个递归算法，找出数组的最大元素。
2.设计一个分治算法，找出x在数组A中出现的次数。
3.写一个主函数，调用上述算法。
五、实验结果分析（分析时空复杂性，设计测试用例及测试结果）时间复杂性：最好情况下，O(n)最坏情况下：O(nlog(n)空间复杂性分析：O(n)六、实验体会通过写递归与分治策略实验，更加清楚的知道它的运行机理，分治法解题的一般步骤：（1）分解，将要解决的问题划分成若干规模较小的同类问题；（2）求解，当子问题划分得足够小时，用较简单的方法解决；（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。
做实验重在动手动脑，还是要多写写实验，才是硬道理。
七、附录：（源代码）#include"stdio.h"#define ElemType intint count(ElemType a[],int i,int j,ElemType x){int k=0,mid; //k用来计数，记录数组中x出现的次数if(i==j){if(a[i]==x) k++;return k;}else{mid=(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=a[n-1],j;if(n==1){max=a[n-1];return max;}else{j=Maxitem(a,n-1);if(j>max) 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("数组的最大元素为%d\n",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[]数组中选a[0]和b[0]开始，然后分别计算在以a[0]和b[0]开始的总的时间，再比较哪个最短。
五．实验结果分析六．实验体会始终觉得用代码写着比用笔直接计算要难点，不过代码解决的事一类问题，只需要输数据就可以。
所以还是代码好，不过要有好的逻辑思维和方法，才能写出好的七．附录：（源代码）#include "stdio.h"#include "iostream.h"#include "string.h"void main(){void sf(int a[],int b[],int n);int a[100],b[100],n,i;printf("请输入需要完成的作业数量：");scanf("%d",&n);printf("请输入A组机器完成作业对应的时间:");for(i=0;i<n;i++)scanf("%d",&a[i]);printf("请输入B组机器完成作业对应的时间:");for(i=0;i<n;i++)scanf("%d",&b[i]);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,v[100];for(i=0;i<n;i++){for(j=0;j<n;j++){if(a[i]<a[j]){d=a[i];a[i]=a[j];a[j]=d;d=b[i];b[i]=b[j];b[j]=d;}}}for(i=0;i<n;i++){low=i;high=i;while(a[i]==a[i+1]){i++;high=i;}if(low!=high){for(k=low;k<=high;k++){for(j=k;j<=high;j++){if(b[k]<b[j]){d=b[k];b[k]=b[j];b[j]=d;}}}}}for(i=0;i<n;i++){A=0;B=0;j=0;while(j<=i){A=A+a[j];j++;}while(j<n){B=B+b[j];j++;}v[i]=max(A,B);}i=1;d=v[0];while(i<n){if(v[i]<d){d=v[i];}i++;}printf("最短作业时间为：%d\n",d); }int max(int a,int b){if(a>b){return a;}else{return b;}}实验三贪心算法——“0/1背包”及“有限期作业调度”一、实验目的1．进一步理解算法设计的基本步骤及各步的主要内容、基本要求2．加深对贪婪法算法设计方法的理解与应用3．掌握将算法转化为计算机上机程序的方法4．培养学生应用所学知识解决实际问题的能力。
二．实验内容（1）给定n种物品和一个背包。
物品I的重量是w i，其价值为p i，背包的容量为M。
应如何选择装入背包的物品（每件物品可以全装也可以只装一部分），使得装入背包中物品的总价值最大?（2）给定n个作业j1, j2,…, j n。
对每个作业j i，有一个与之联系的限期d i>0和收益p i≥0，d i，p i均为整数，1≤I≤n。
对作业j i，只有在限期d i内完成，才能得到收益p i。
假定只有一台处理机为这批服务业服务，处理机每次只能处理一个作业，并且完成一作业需一个单位时间。
所谓一个可行解，是这批作业的一个子集J，J中每一作业均能在限期d i内完成。
调度的总收益是子集J中各作业收益之和。
具有最大收益的的可行解和为最优解。
如何求其最优解？三．实验要求（1）设计用贪婪法求解“背包问题”及“带有限期的计算机作业调度问题”的算法；（2）上机实现所设计的算法；（3）分析所设计的算法的时间/空间复杂性。
四．实验过程设计（算法设计过程）后面人的等到时间等于前面人的服务时间，要总的等待时间最短，就要前面的服务时间最短，就需要先让服务时间段的人先进行服务。
1.先按原来的顺序服务时间服务，得到一个等待时间2.升序排列后，得到一个等待时间五．结果分析六．实验体会后面人的等到时间等于前面人的服务时间，要总的等待时间最短，就要前面的服务时间最短，就需要先让服务时间段的人先进行服务。
这是总的实验思路。
贪心算法就是要尽可能的提高效率，得到想要的效益。
七．附录（源代码）#include "stdio.h"#include "iostream.h"#include "string.h"main(){int i,j,n,a[100],d=0,k=0;printf("请输入顾客的总人数：");scanf("%d",&n);printf("依次输入每个顾客的服务时间:");for(i=0;i<n;i++)scanf("%d",&a[i]);for(i=0;i<n;i++){d=0;for(int j=0;j<i;j++){d=d+a[j];//第j个人的等待时间}k=k+d;//总的等待时间}printf("此时等待的总时间为：%d\n",k);for(i=0;i<n;i++){for(int j=i;j<n;j++){if(a[i]>a[j]){d=a[i];a[i]=a[j];a[j]=d;}}}printf("按升序排列后的数组为：");for(i=0;i<n;i++)printf("%d",a[i]);k=0;for(i=0;i<n;i++){d=0;for(int j=0;j<i;j++){d=d+a[j];}k=k+d;}printf("\n此时等待的总时间为：%d\n",k);}实验四回溯法——“N皇后”问题一、实验目的1．掌握能用回溯法求解的问题应满足的条件；2．加深对回溯法算法设计方法的理解与应用；3．锻炼学生对程序跟踪调试能力；4．通过本次实验的练习培养学生应用所学知识解决实际问题的能力。
二．实验内容由N2个方块排成N行N列的正方形，称为N元棋盘，在N元棋盘上放置N个皇后，如果某两个皇后位于N元棋盘的同一行或同一列或同一斜线（斜率为±1）上，则称它们在互相攻击，试设计算法找出使N个皇后互不攻击的所有布局。
三．实验要求（1）用回溯法算法设计方法求解N元皇后问题（2）找出N皇后问题的互不攻击的所有解（3）皇后数N由键盘动态输入（4）上机实现所设计的算法；（5）分析所设计的算法的时间/空间复杂性。