实验报告算法思想
《算法设计与分析》 试验报告 班级 姓名 学号 年 月 日 书目 试验一 二分查找程序实现…………………………………………………………………03页 试验二 棋盘覆盖问题(分治法).…………………………………………………………08页 试验三 0-1背包问题的动态规划算法设计……………………………………………….11页 试验四 背包问题的贪心算法………………………………………………………………14页 试验五 最小重量机器设计问题(回溯法)………………………………………………17页 试验六 最小重量机器设计问题(分支限界法)…………………………………………20页 指导老师对试验报告的评语 成果: 指导老师签字: 年 月 日 试验一:二分查找程序实现 一、试验时间:2013年10月8日,星期二,第一、二节地点:j13#328 二、试验目的及要求 目的: 建立算法困难度的理论分析与试验分析的联系,深刻体会算法困难度作为算法的好坏评价指标的本质含义。 要求: 1、用c/c++语言实现二分搜寻算法。 2、通过随机产生有序表的方法,测出在平均意义下算法比较次数随问题规模的变更曲线,并作图。 三、试验环境 平台:win7 32位操作系统 开发工具:codeblocks10.05 四、试验内容 对已经排好序的n个元素a[0:n-1],现在要在这n个元素中找出一特定元素x。 五、算法描述及试验步骤 算法描述: 折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采纳分治策略,可在最坏的状况下用o(log n)完成搜寻任务。它的基本思想是,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,假如x=a[n/2]则找到x,算法终止。假如xa[n/2],则我们只要在数组a的左半部接着搜寻x(这里假设数组元素呈升序排列)。假如xa[n/2],则我们只要在数组a的右半部接着搜寻x。二分搜寻法的应用极其广泛,而且它的思想易于理解。 确定算法困难度基本步骤: 1、首先设定问题规模n; 2、随即产生递增数列; 3、在n个有序数中随机取一个作为待查找量,搜寻之; 4、记录查找过程中的比较次数,再次生成新的有序表并查找,记录查找次数,每个数组重复10次; 5、变更问题规模n重复上述步骤2~4,n取100、200……1000; 6、依试验数据作图,并与理论图作比较; 7、二分搜寻算法平均查找次数: 问题规模为n时,平均查找次数为: a(n)=int(logn) + 1/2 // int() 函数为向下取整 即二分搜寻算法对于含有n个数据的有序表l平均作了约int(logn)+1/2次的查找操作。 试验步骤: 1. 初始化生成递增随机数列: for ( int j=100; j =1000; j+=100 ) { array[0]=10+rand()%15; for(int i=1; ij; i++) { array[i]=array[i-1]+1+rand()%3+rand()%10; } } 2. 定义二分查找算法: int binarysearch( const int b[], int searchkey, int low, int high ); 其中,返回值为int类型,数组b[]为待查递增序列,searchkey为所查数据,low为数组b[]左下标,hight为数组b[]右下标。 该算法实现过程为: 将数组b[]的n个元素分成个数大致相同的两半,取b[n/2]与searchkey作比较。假如searchkey=b[n/2],则找到searchkey,算法终止;假如searchkeyb[n/2],则只要在数组b的左半部接着搜寻searchkey;假如searchkeyb[n/2],则只要在数组b的右半部接着搜寻searchkey。 3. 实现主函数并完成全部代码。 4.算法困难性分析: 简洁看出,没执行一次算法的while循环,待搜寻数组的大小削减一半。因此,在最坏状况下,while循环被执行了o(logn)次。循环体内运算须要o(1)时间,因此整个算法在最坏状况下的计算时间困难性为o(logn)。 六、调试过程及试验结果 输出结果为:篇二:算法试验报告 实 验 报 告 课程: 计算机算法分析与设计 系科: 计算机科学与技术 班级: 姓名: xxxxx 学号:xxxxxxxxxxxxxx 年度: 2010-2011 学期: 上 计算机与信息科学学院 计算机科学试验教学中心 篇三:算法试验报告 重 庆 交 通 大 学 学 生 实 验 报 告 试验课程名称 算法设计与分析 开课试验室 数学试验室 学院 数学与统计学院 年级13 专业班 信息与计算科学2 学 生 姓 名 辜朕