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

算法设计与分析实验报告.doc重庆交通大学学生实验报告实验课程名称算法分析与设计升课实验室数学实验室学院理学院年级11专业班信息与计算科学2学生姓名许智达学号 631122020217开课时间2013至2014学年第L学期评分细则评分报告表述的清晰程度和完整性(20分)程序设计的正确性(40分)实验结果的分析(30分)实验方,法的创新性(10分)总成绩教师签名实验一递归与分治策略一、实验目的加深学生对递归与分治策略设计方法的基本思想、基本步骤、基本方法的理解与掌握;提高学生利用课堂所学知识解决实际问题的能力;提高学生综合应用所学知识解决实际问题的能力。A.■L=J二、实验过程设计(算法设计过程)三分法是对二分法的改进而编写成的。二分法中,将已排好的数组分为两个部分,左边(left)大于中间的元素(middle=(left+right)/2),而右边(right)小于中间元素,利用while语句将数组找完,输出要找的数字;若没有找到,就返回在三分法中,将数组分为三个部分,即tl=(-left+right)/3+left,t2=(-left+right)*2/3+left,,也是用while语句,将数组找完,输出找到的数字:若没有找到则返回-1。三、实验结果分析时间复杂性:最好情况卜:O⑴,最坏情况卜:O(log7?)空间复杂性分析:储存数组的长度n,和left,right,middle,共n+3。四、实验体会在编写这是实验的代码时,通过改进二分法搜索的思想,进而将三分搜索编写出来。通过这次试验,使我加深了对二分法思想的印象。附录:(源代码)#include<>intbinarySearch(inta[],intn,intx,int&i,int&j)(intmiddle;〃中值intright=n-l;//数组的右边界intleft=O;〃数组的左边界while(left<=right)(middle=(left4-right)/2;if(x==a[middle])(i=j=middle;returnmiddle;}if(x>afmiddle])left=middle+l;elseright=middle-l;i=right;j=left;}return-1;〃查询失败}intmain(void){inti;intj;intmiddle;intb[]={1,2,3,4,5,6,7,8,12,22};〃用来测试的数组middle=binarySearch(b,10,13,i,j);〃调用二分搜索算法if(middle!=-1)〃查询成功(printf("thex'spositionis:%d,iis%d,jis%d\n",middle,i,j);}else〃查询失败{anlfindthiselement,theiis:%d,jis%d\n",i,j);}return0;实验二动态规划一、实验目的加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握;提高学生利用课堂所学知识解决实际问题的能力;提高学生综合应用所学知识解决实际问题的能力。二、实验内容题目1:用两台处理机A和B处理n个作业。社第i个作业交给机器A处理时需要时间ai,若由机器B来处理,则需要时间bi。由于各作业的特点和机器的性能关系,很可能对于某些i,有aixbi,而对于某些j,j!=i,有ajvbj。既不能将一个作业分开由两台机器处理,也没有一台机器能同时处理2个作业。设计一个动态规划算法,使得这两台机器处理完这n个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。题目2:给定n种物品和一个背包。物品i的重量是wi,体积是bi,其价值为vi,背包容量为C,容积为D。问:应该如何选择装入背包中的物品,使得装入背包中的物品的总价值最大?在选择装入背包的物品时,对每种物品i只有两种选择,即装入背包或不装入背包。不能将物品i装入背包多次,也不能只装入部分的物品i。试设计一个解此问题的动态规划算法,并分析算法的计算复杂性。实验过程设计(算法设计过程)L=J处理机处理作业过程:在界面上输入A、B两组数据分别代表任务在A、B机器下处理所需要的时间,分析每个作业在A、B处理机上最短的时间。而且当其中一个处理机在处理作业时,另一个处理机可以处理下一个作业。要求处理该组作业的时间最短。背包装入问题:在背包容重量和容积一定的情况下,选择背包能够容纳下的最大价值的物品装入背包中;每个物品只有两种选择:装入背包或者不装入背包,在背包容量和容积能够接受的情况下,选择装入的物品的价值总和最大。U!实验结果分析处理机处理作业问题:1=1背包价值最大装入问题:时间复杂性:最好情况下最坏情况下处理机处理任务问题:0(mA2*n人3)背包问题:0(abc)附录:(源代码)处理机处理作业问题: