算法设计与分析的实验报告

试验一递归与分治策略一、试验目的加深学生对分治法算法设计方法的根本思想、根本步骤、根本方法的理解与把握；提高学生利用课堂所学学问解决实际问题的力量；提高学生综合应用所学学问解决实际问题的力量。二、试验内容1、a[0:n-1]是已排好序的数组。请写二分搜寻算法，使得当搜寻元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置jj一样，x在数组中的位置。②写出三分搜寻法的程序。三、试验要求用分治法求解上面两个问题；再选择自己生疏的其它方法求解本问题；上机实现所设计的全部算法；四、试验过程设计〔算法设计过程〕1、a[0:n-1]是一个已排好序的数组，可以承受折半查找〔二分查找〕算法。假设搜寻元x与通过二分查找所得最终元素的大小，留意边界条件，从而计算出小于x的最大元素的位置i和大于x的最小元素位置j。2、将n个元素分成大致一样的三局部，取在数组ax。假设x>a[2(n-1)/3]，则只需在数组a的右三分之一局部中连续搜寻x。上述两种状况不成立时，则在数组中间的三分之一局部中连续搜寻x。五、试验结果分析二分搜寻法：时间简单性：时间简单性：二分搜寻每次把搜寻区域砍掉一半，很明显时间简单度为O(logn)。〔n代表集合中元素的个数〕三分搜寻法：O〔3log3n〕空间简单度：O〔1〕。六、试验体会看是不够的还要动手分析一下，这样才能学好算法。〔源代码二分搜寻法：#include<iostream.h>#include<stdio.h>intbinarySearch(inta[],intx,intn){intleft=0;intright=n-1;inti,j;while(left<=right){intmiddle=(left+right)/2;if(x==a[middle]){i=j=middle;return1;}if(x>a[middle])left=middle+1;elseright=middle-1;}i=right;j=left;return0;}intmain{ inta[10]={0,1,2,3,4,5,6,7,8,9};intn=10;intx=9;if(binarySearch(a,x,n))cout<<“找到“<<endl;elsecout<<“找不到“<<endl;return0;}试验二动态规划——求解最优问题一、试验目的加深学生对动态规划算法设计方法的根本思想、根本步骤、根本方法的理解与把握；提高学生利用课堂所学学问解决实际问题的力量；提高学生综合应用所学学问解决实际问题的力量。二、试验内容1ABniAa[i]，假设由机器Bb[i]。由于各作业的特点和机器的性能关系，很可能对于某些ia[i]>=b[ij，j!=ia[i]<b[j]。既不能将一个作业分2两台机器处理完这n〔从任何一台机器开工到最终一台机器停工的总的时间〕。争论一个实例:〔a[1],a[2],a[3],a[4],a[5],a[6]〕=(2,5,7,10,5,2);(b[1],b[2],b[3],b[4],b[5],b[6])=(3,8,4,11,3,4)。2、长江游艇俱乐部在长江上设置了n个游艇出租站1，2„„n。游客可在游艇出租站租用i到游艇出租站j之间的租金r〔i，j〕1<=i<j<=n。设计一个算法，计算出游艇1到游艇n三、试验要求用动态规划思想求解最优问题；再选择自己生疏的程序设计语言实现全部算法；分析所设计的算法的时间/空间简单性。四、试验过程设计〔算法设计过程〕1、对于给定的2台处理机AB处理n个作业，找出一个最优调度方案，使2台机器处理n个作业的时间最短。2、对于给定的游艇出租站i到游艇出租站j之间的租金为〔，，1<=i<j<=1n五、试验结果分析独立任务最优调度问题：租用游艇问题：时间简单性：独立任务最优调度问题：O(n*Sum)六、试验体会算法才是上上之策。〔源代码〕独立任务最优调度问题：usingSystem;namespacezydd{classProgram{staticvoidDlrwZydd(int[]a,int[]b,intn,int[]least,string[]result){for(inti=0;i<n;i++){least[i]=99;}intaSum=0,bSum=0;for(inti=0;i<n;i++){aSum+=a[i];bSum+=b[i];}intSum=1+Math.Min(aSum,bSum);int[,]timeA=newint[n,Sum];int[,]timeB=newint[n,Sum];int[,]timeMax=newint[n,Sum];char[,]who=newchar[n,Sum];char[]tempRlt=newchar[n];for(inti=0;i<=a[0];i++){timeA[0,i]=i;if(i<a[0]){

}else{}

timeB[0,i]=b[0];who[0,i]=”b”;timeB[0,i]=0;who[0,i]=”a”;timeMax[0,i]=Math.Max(timeA[0,i],timeB[0,i]);}if(a[0]<=b[0]){}else{}

least[0]=a[0];tempRlt[0]=”a”;least[0]=b[0];tempRlt[0]=”b”;result[0]=newString(tempRlt);for(intk=1;k<n;k++){inttempSum=0;for(inttemp=0;temp<=k;temp++){tempSum+=a[temp];}for(inti=0;i<=tempSum;i++){ timeA[k,i]=i;if(i<a[k]){timeB[k,i]=timeB[k-1,i]+b[k];who[k,i]=”b”;}else{if((timeB[k-1,i]+b[k])<=timeB[k-1,i-a[k]]){}else{}}

timeB[k,i]=timeB[k-1,i]+b[k];who[k,i]=”b”;timeB[k,i]=timeB[k-1,i-a[k]];who[k,i]=”a”;timeMax[k,i]=Math.Max(timeA[k,i],timeB[k,i]);}for(inti=tempSum+1;i<aSum;i++){timeA[k,i]=tempSum;timeB[k,i]=0;}intflag=0;for(inti=0;i<=tempSum;i++){if(timeMax[k,i]>0&&timeMax[k,i]<least[k]){least[k]=timeMax[k,i];flag=i;}}tempRlt[k]=who[k,flag];for(inti=k;i>0&&flag>0;i--){if(tempRlt[i]==”a”){flag-=a[i];tempRlt[i-1]=who[i-1,flag];}if(tempRlt[i]==”b”){tempRlt[i-1]=who[i-1,flag];}}result[k]=newString(tempRlt);}}staticvoidMain(string[]args){constintN=6;int[]a=newint[N]{2,5,7,10,5,2};int[]b=newint[N]{3,8,4,11,3,4};int[]least=newint[N];string[]result=newstring[N];DlrwZydd(a,b,N,least,result);Console.WriteLine;for(inti=0;i<N;i++){Console.WriteLine(“按要求完成前{0}项任务的机器挨次为：“+result[i]+“时间为：{1}“,i+1,least[i]);}}}}试验三贪心算法一、试验目的进一步理解算法设计的根本步骤及各步的主要内容、根本要求加深对贪欲法算法设计方法的理解与应用把握将算法转化为计算机上机程序的方法培育学生应用所学学问解决实际问题的力量。二、试验内容1n个顾客同时等待一项效劳。顾客i需要的效劳时间为ti，1<=i<=nn个顾客的效劳次序才能使总的等待时间到达最小？总的等待时间是每个顾客等待效劳时间的综合。2、一辆汽车加满油后可行驶n公里。旅途中有假设干个加油站。设计一个有效算法，之处应在哪些加油站停靠加油，使沿途加油次数最少。并证明算法能产生一个最优解。三、试验要求设计用贪欲法求解“最优效劳次序问题”及“汽车加油问题”的算法；上机实现所设计的算法；分析所设计的算法的时间/空间简单性。四、试验过程设计〔算法设计过程〕12st[]是效劳数组，st[j]为第jsu[]是求和数组，su[jj上全部顾客的等待时间；2、设加油次数为k，每个加油站间距离为a[i]；i=0，1，2，3„„n始点到终点的距离小于Ｎ，则加油次数k=0；始点到终点的距离大于N，①加油站间的距离相等，即ａ[i]=a[j]=L=Nk=n；②加油站间的距离相等，即ａ[i]=a[j]=L>N，则不行能到达终点；③加油站间的距离相等，即ａ[i]=a[j]=L<N，则加油次数k=n/N(n%N==0)k=[n/N]+1(n%N！=0)；④加油站间的距离不相等，即ａ[i]！=a[jk五、试验结果分析最优效劳次序问题：时间简单度为O(nlogn)汽车加油问题：时间简单度为O(n)。六、试验体会〔源代码汽车加油问题：#include<iostream.h>#include<stdio.h>namespaceConsoleApplication1{classProgram{staticvoidMain(string[]args){Console.Write(“请输入汽车加满油后可行驶路程：“);intn=Convert.ToInt32(Console.ReadLine);Console.Write(“请输入途经加油站总数：“);intk=Convert.ToInt32(Console.ReadLine);int[]distance=newint[k+1];//加油站间距int[]note=newint[k];//记录加油站点Console.WriteLine(“请输入加油站间距！“);for(inti=0;i<=k;i++){//从始点起，加油站间距Console.Write(“站点间距{0}: “,i+1);distance[i]=Convert.ToInt32(Console.ReadLine);}intcount;//记录加油次数Problemp=newProblem;count=p.Greedy(distance,note,n);if(count>=0){if(count==0)Console.WriteLine(“汽车不用加油就可到达终点！“);else{Console.WriteLine(“汽车在旅途中需加{0}次油！“,count);Console.WriteLine(“分别在以下加油站加了油：“);for(inti=0;i<note.Length;i++){if(note[i]!=0){//输出需加油站点Console.WriteLine(“第“+note[i]+“个加油站！“);}}}}elseConsole.WriteLine(“汽车无法到达终点！“);Console.ReadKey;}}classProblem{publicintGreedy(int[]d,int[]note,intn){inti,j,s,add=0,p=0,k=d.Length;for(i=0;i<k;i++){if(d[i]>n){//不能到达目的地return-1;}}for(j=0,s=0;j<k;j++){s+=d[j];if(s>n){//需要加油add++;note[p++]=j;s=d[j];}}returnadd;}}}试验四回溯法一、试验目的1．把握能用回溯法求解的问题应满足的条件；加深对回溯法算法设计方法的理解与应用；熬炼学生对程序跟踪调试力量；通过本次试验的练习培育学生应用所学学问解决实际问题的力量。二、试验内容1、设某一机器由n个部件组成，每一种部件都可以从m个不同的供给商处购得。设w[i][j]是从供给商j处购得的部件i的重量，c[i][j]是相应的价格。试设计一个算法，给出总价格不c的最小重量机器设计。2、nnijc[i][j]。试设计一个算法，为每1件不同的工作，并使总费用到达最小。三、试验要求用回溯法算法设计方法求解最小重量机器设计问题和工作安排问题；上机实现所设计的算法；分析所设计的算法的时间/空间简单性。四、试验过程设计〔算法设计过程〕1、a.部件有n个，供给商有m个，分别用w[i][j]c[i][j]存储从供给商j处购得的部件i的重量和相应价格，d为总价格的上限。b.用递归函数backtrack(i)来实现回溯法搜寻排列树〔形式参数i表示递归深度。cp>d，则为不行行解，剪去相应子树，返回到i-1层连续执行。cw>=sum，则不是最优解，剪去相应子树，返回到i-1层连续执行。i>nsumi-1层连续执行；④用for循环对部件i从m(1≤jmc.主函数调用一次Knapsack(1)sum即为所求最小总重量。2、a.c[i][j]存储将工作i安排给第j个人所需的费用，用v[j]j个人是否已安排工作；b.用递归函数backtrack〔i，total〕来实现回溯法搜寻排列树〔形式参数i表示递归深n用来掌握递归深度，形式参数totals表示当前最优总费用：total>=s，则不是最优解，剪去相应子树，返回到i-1层连续执行；②假设i>n，则算法搜寻到一个叶结点，用s对最优解进展记录，返回到i-1层连续执行；③承受for循环针对n个人对工作i进展安排≤：1>v[j]==1，则第j个人已安排了工作，找第j+1个人进展安排；2>假设v[j]==i安排给第j〔即v[j]=1对工作i+1调用递归函数backtrack〔i+1，total+c[i][j]〕连续进展安排；3>backtrack〔i+1，total+c[i][j]〕调用完毕后则返回v[j]=0，将工作i对j+1个人进展安排；4>j>n时，for循环完毕；i=1时