《算法设计与分析》上机实验报告模板

算法设计与分析算法设计与分析 上上 机机 实实 验验 报报 告告 专 业软件工程 班 级软件 1101 班 学 号 04113035 学生姓名付添 完成日期 排版说明排版说明 1 一级标题用宋体四号 加粗 2 如有二级标题 请使用宋体 小四 加粗 3 正文汉字均用宋体 5 号 英文用 Times New Roman 字体 4 正文行距建议设置为 1 5 倍行距 5 实验报告中有图 表的 图 表格式必须标准 有编号 有标题 如下所示 图的标题 在下方 表的标题在上方 图图 1 XXXXXXX 图图 表表 1 XXXXXXX 表表 数据 1数据 2数据 3数据 4数据 5 1 上机题目及实验环境上机题目及实验环境 1 1 上机题目上机题目 计算能存放的程序数 1 2 实验环境实验环境 CPU 内存内存 操作系统操作系统 xp 软件平台软件平台 vc6 0 2 算法设计与分析算法设计与分析 基本思想基本思想 贪心算法总是作出在当前看来最好的选择 也就是说贪心算法并不从整体最优上加以 考虑 它所作出的选择只是在某种意义上的局部最优选择 当然 希望贪心算法得到的最终 结果也是整体最优的 虽然贪心算法不能对所有问题都得到整体最优解 但对许多问题它能 产生整体最优解 在一些情况下 即使贪心算法不能得到整体最优解 其最终结果却是最优 解的很好近似 就该题而言 算法设计算法设计 1 将数据集 S 均分为 S1 和 S2 2 求解 S1 和 S2 中的最大和最小值 3 最终的最大和最小值可以计算得到 min S1 S2 max S1 S2 4 采用同样的处理方法递归处理 S1 和 S2 min max S min max if S 2 then min min S max max S else split S evenly into S1 and S2 min max S1 min1 max1 min max S2 min2 max2 min min min1 min2 max max max1 max2 给出具体的原理 算法设计与分析细节等 3 核心代码核心代码 void min max int arry int i int j int min int max 找出最大值和最小值 int mid min1 min2 max1 max2 if i j max arry i min arry i else if j i 1 if arry i arry j min arry j max arry i else min arry i max arry j else mid i j 1 2 min max arry i mid min max arry mid 1 j min min1max2 max1 max2 在 main 函数中通过产生随机数给出数据通过调用 min max 函数实现找出最大值 最小值并 把他们返回 main 函数输出 4 运行与调试运行与调试 给出程序的运行结果 建议给出不同情况下的运行结果并加以比较 如排序算法可以给出输 入数据规模不等时的运行结果比较 如数组规模为 100 时的实验结果 数组规模为 1000 时的 实验结果 数组规模为 10000 时的实验结果等 程序运行有屏幕输出的 应给出屏幕截图 图 1 显示随机产生 100 个 0 到 100 个整数 找出了之间的最大值和最小值 图 2 显示随机产生 1000 个 0 到 100 个整数 找出了之间的最大值和最小值 图 3 显示随机产生 10 个 0 到 100 个整数 找出了之间的最大值和最小值 图 1 图 2 图图 3 5 结果分析和小结结果分析和小结 1 对结果的分析 分析结果可以采用图或者表的形式给出 运行时由于没有加随机数初始化函数 srand time 0 每次运行结果都一样 这个问题在设 计代码时由于时间匆忙也没有发现 知道被老师检查时 被老师发现 以致于我以后再也不会 犯这个错误了 2 本次上机实验的收获 心得体会 上机可以督促我自己写代码 每次上机前我都会先把代码大致写好 上机是运行并检查错 误 这样不仅提高我的写代码能力 同时对算法这门课也有了更深刻的认识 老师检查运行 结果可以发现我们的问题所在 对我们学习提供很大帮助 附录 附录 C C 源代码 源代码 列出程序源码 程序设计时注意设计风格 用分治法查找数组元素的最大值和最小值 include include include define M 10 void min max int arry int i int j int min int max int mid min1 min2 max1 max2 if i j max arry i min arry i else if j i 1 if arry i arry j min arry j max arry i else min arry i max arry j else mid i j 1 2 min max arry i mid min max arry mid 1 j min min1max2 max1 max2 void main int max min i j arry M k srand time 0 printf 随机产生 10