算法设计与分析实验报告样本.docVIP

算法分析与设计实验报告重 庆 交 通 大 学学 生 实 验 报 告实验课程名称 算法设计与分析 开课实验室 数学实验室 学院 年级 09 专业班 信息2班 学 生 姓 名 学 号 09180223 开 课 时 间 2011 至 2012 学年第 1 学期评分细则评分报告表述的清晰程度和完整性（20分）程序设计的正确性（40分）实验结果的分析（30分）实验方法的创新性（10分）总成绩教师签名实验报告题目实验一 递归与分治策略开课实验室：数学实验室 指导老师：韩逢庆 时间：2011.9学院： 专业：信息与计算科学 班级：2009级2班姓名： 学号：09180223一、 实验目的 1加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握； 2提高学生利用课堂所学知识解决实际问题的能力； 3提高学生综合应用所学知识解决实际问题的能力。二、 实验内容 题目见：二分搜索问题、三分搜索问题、整数规划、全排列问题三、 实验要求 （1）用分治与递归法求解二分搜索问题、三分搜索问题、整数规划、全排列问题。 （2 ）再选择自己熟悉的其它方法求解本问题； （3）上机实现所设计的所有算法；四、 实验过程设计（算法设计过程）以二分搜索为例，设计如下算法过程：startLeft=1,right=n-1Middle=(left+right)/2Right=middle-1Left=middle+1 N bamiddle Y no b=amiddle N YReturn middleend五、 实验结果分析（分析时空复杂性，设计测试用例及测试结果）时间复杂性：最好情况下，最坏情况下最好情况下：对二分搜索与三分搜索，刚好处在整行数的中间位置或三分之一或三分之二位置处，一次搜索便找到。因此，时间复杂度如下：最坏情况下：所要找的数处在两端位置上，时间复杂度如下：总的情况下，时间复杂度为：空间复杂性分析：六、 实验体会 通过该实验，我体会到了递归与分治思想的精髓所在，对其算法的特点有了深刻理解，在以后遇到类似的问题的时候，有了这样的指导思想！递归与分治经常结合到一起解决实际问题，是一种高效率且简洁的算法。具有很强的实际应用意义。优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。七、 附录：（源代码）程序一、二分搜索与三分搜索源代码：#include#includeint erfensousuo(int *a,int b,int n)int left=0,right=n-1;while(leftamiddle)left=middle+1;elseright=middle-1;return -1;int sanfensousuo(int *a,int b,int n)int low=0,high=n-1,middle1,middle2;while(low=high)middle1=low+(high-low)/3;middle2=high-(high-low)/3;if(amiddle1=b)return middle1;else if(bamiddle1)/处于middle1左边high=middle1-1;elseif(bamiddle2)/处于中间low=middle1+1;high=middle2-1;elseif(amiddle2=b) return middle2;elselow=middle2+1;/处于middle2右边return -1;void main()int i=0,k,z,zhi,*a,n;cout您给定要输入数字的个数nendl;coutn=n;a=new int(n);cout请输入n个数字endl;for(i;iai;cout请输入你要查找的数：zhi;cout二分搜索结果为：endl;k=erfensousuo(a,zhi,n);if(k=-1)cout数组里面没有您要查找的数endl;elsecout您要查找的数位于数组的第k位endl;cout三分搜索结果为：endl;z=sanfensousuo(a,zhi,n);if(z=-1)cout数组里面没有您要查找的数endl;elsecout您要查找的数位于数组的第z位endl;if(k=z)cout二分搜索与三分搜索结果一样！两个搜索技术都正确！endl;elsecout二分搜索与三分搜索结果不一样，二分搜索或三分搜索算法设计有误！endl;程序运行结果如下：查找到所要查找的数的运行结果：未查找到所要查找数的运行结果：程序二、整数规划问题源代码:#include#include#define N 100 void main() int aN,i,j,k,m,n; while(1) cout请输入一个正整数 n(n100):n; if(n0) break; cout整数n可分解为endl; coutn=nn/2;a0-) for(j=1;jN;j+) aj=0; a1=n-a0; coutn=a0+a11) a1+i-=1; j+; while(1) if(a1+i+ja1+i) a1+i+j+=1;break; else j+; coutn=; for(k=0;k1+i+j;k+) coutak+; coutak0) i-; else break; for(a0=n/2;a00;a0-) for(j=1;jN;j+) aj=0; j=n/a0; for(k=1;kj;k+) ak=a0; ak=n-j*a0; if(!ak) k-; coutn=; for(m=0;mk;m+) coutam+; coutak1) ak+i-=1; j+; while(1) if(ak+i+jak+i) ak+i+j+=1; break; else j+; coutn=; for(m=0;mk+i+j;m+) coutam+; coutam1) i-; else break; 程序运行结果如下： 程序三、全排列问题源代码#includeiostream.hint n,count=0;int perm(int*list,int i,int n);void swap(int*a,int*b) int temp; temp=*a;*a=*b;*b=temp;void main() int list100; cout请输入需要全排列的个数n;cout请输入需要全排列的数endl;for(int k=0;klistk;perm(list, 0, n); cout共有count种排列endl; int perm(int*list,int i,int n)int j; if(i=n)cout第count+1种排列:endl;for(j=0;jn;j+) coutlistj; cout ; count+;coutendl; elsefor(j=i;jn;j+)swap(list+i,list+j); perm(list,i+1,n); swap(list+i,list+j); return count;程序运行结果如下：实验报告题目实验二 动态规划与回溯法开课实验室：数学实验室 指导老师：韩逢庆 时间：2011.9学院： 专业：信息与计算科学 班级：2009级2班姓名： 学号：09180223一、 实验目的 1掌握能用回溯法求解的问题应满足的条件；2加深对回溯法算法设计方法的理解与应用；3锻炼学生对程序跟踪调试能力；4通过本次实验的练习培养学生应用所学知识解决实际问题的能力。二、 实验内容 题目见：处理机调度问题、背包问题、欧氏旅行售货员问题三、 实验要求 （1）用动态法与回溯法求解背包问题、处理机调度问题、单双调旅行售货员问题； （2 ）再选择自己熟悉的其它方法求解本问题； （3）上机实现所设计的所有算法；四、 实验过程设计（算法设计过程）以游艇租赁问题为例：五、 实验结果分析（分析时空复杂性，设计测试用例及测试结果）时间复杂性：最好情况下，最坏情况下六、 实验体会 通过该实验，我体会到了动态规划与回溯法思想的精髓所在，对这两个算法的特点有了深刻理解，在以后遇到类似的问题的时候，有了这样的指导思想！回溯法其实就是遍历所有可能的情况，采用的是穷举法。输出满足条件的解，在实际生活中很实用。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。七、 附录：（源代码）处理机问题源代码：#define M 100#define N 100#includeiostream.hint jisuanp(int n,int a,int b)int sum=0;for(int i=0;i=bi)sum=sum+bi;elsesum=sum+ai;return sum;void main()int n,aM,bN,i=0,j=0,x,y;cout-请输入作业数量-n;cout请输入作业A的各个的所需时间x;while(x!=0)ai=x;i+;cinx;cout请输入作业B的各个的所需时间y;while(y!=0)bj=y;j+;ciny;for(int i1=0;i1i;i1+)coutAi1+1=ai1endl;for(int j1=0;j1j;j1+)coutBj1+1=bj1endl;int opt=jisuanp(n,a,b);cout处理的最短时间为：optendl;程序运行结果如下：游艇租赁问题源代码：#includeusing namespace std;#define N 200int fNN;int n;void init() int i,j; for(i=0;in;i+) for(j=0;jn;j+) fij=0; cout请输入每两站之间的租金：endl; for(i=0;in-1;i+) for(j=i+1;jn;j+) cout输入i+1站到j+1站的租金：fij;void dyna() for(int k=2;kn;k+) for(int i=0;in-k;i+) int j=i+k; for(int p=i+1;ptemp) fij=temp; int main() cout请输入游艇站的个数：n; init(); dyna();cout所需的最少费用：endl; coutf0n-1endl; return 0;程序运行结果如下：#include#include#includeint c; /背包容量 int n; /物品数 int weight100; /存放n个物品重量的数组 int price100; /存放n个物品价值的数组 int currentWeight=0; /当前重量 int currentPrice=0; /当前价值 int bestPrice=0; /当前最优值 int bestresolution100; /当前最优解 int bp=0;int bA100; /当前最优解 int times=0;void Print(); void Backtrack(int i) times+=1;if(in) Print();if(bestPricebp)bp=bestPrice;for(int j=1;j=n;j+) bAj=bestresolutionj;return; if(currentWeight+weighti=c) /将物品i放入背包，搜索左子树 bestresolutioni = 1; currentWeight += weighti; bestPrice += pricei; Backtrack(i+1); /完成上面的递归，返回到上一结点，物品i不放入背包，准备递归右子树 currentWeight -= weighti; bestPrice -= pricei; bestresolutioni = 0; Backtrack(i+1); void Print() int i; coutendl当前路径为 ; for(i=1;in;+i) coutbestresolutioni,; coutbestresolutioni 价值为bestPriceendl; void main() int i;