实验报告算法思想

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