算法设计与分析

四川理工学院课程设计 算法设计与分析课程设计 学 生 学 号 专 业 信息与计算科学 班 级 2012 2 指导教师 吴树林 四川理工学院理学院 一一 问题描述 问题描述 输入一列整数 求出该列整数中的最大值与最小值 2 课程设计目的课程设计目的 通过课程设计 提高用计算机解决实际问题的能力 提高独立实践的能 力 将课本上的理论知识和实际有机的结合起来 锻炼分析解决实际问题的能 力 提高适应实际 实践编程的能力 在实际的编程和调试综合试题的基础上 把高级语言程序设计的思想 编程巧和解题思路进行总结与概括 通过比较系 统地练习达到真正比较熟练地掌握计算机编程的基本功 为后续的学习打下基 础 了解一般程序设计的基本思路与方法 3 问题分析问题分析 看到这个题目我们最容易想到的算法是直接比较算法 将数组的第 1 个元 素分别赋给两个临时变量 fmax A 1 fmin A 1 然后从数组的第 2 个元 素 A 2 开始直到第 n 个元素逐个与 fmax 和 fmin 比较 在每次比较中 如 果 A i fmax 则用 A i 的值替换 fmax 的值 如果 A i fmax 则用 A i 的值替 换 fmax 的值 否则才将 A i 与 fmin 比较 如果 A i fmax 情况 如果采用分治的思想 可以构造算法 其时间复杂度在最坏情况下和平均用时 均 为 3n 2 2 4 主要算法 分治法 描述主要算法 分治法 描述 4 1 当我们求解某些问题时 由于这些问题要处理的数据相当多 或求解 过程相当复杂 使得直接求解法在时间上相当长 或者根本无法直接求出 对 于这类问题 我们往往先把它分解成几个子问题 找到求出这几个子问题的解 法后 再找到合适的方法 把它们组合成求整个问题的解法 如果这些子问题 还较大 难以解决 可以再把它们分成几个更小的子问题 以此类推 直至可 以直接求出解为止 这就是分治策略的基本思想 把 n 个元素分成两组 A1 A 1 A int n 2 和 A2 A int N 2 1 A N 分别求这两组的最大值和最小值 然后分别将这两组的最大值和最小值相 比较 求出全部元素的最大值和最小值 如果 A1 和 A2 中的元素多于两个 则 再用上述方法各分为两个子集 直至子集中元素至多两个元素为止 例如有下面一组元素 13 13 9 5 7 23 0 15 用分治策略比较 的过程如下 图中每个方框中 左边是最小值 右边是最大值 从图中看出 用这种方法一 共比较了 10 次 比直接比较法的 14 次减少 4 次 即约减少了 1 3 4 2 分治法在每一层递归上都有三个步骤 分解 将原问题分解为若干个规模较小 相互独立 与原问题形式相同的子问 题 解决 若子问题规模较小而容易被解决则直接解 否则递归地解各个子问题 合并 将各个子问题的解合并为原问题的解 4 3 在用分治法设计算法时 最好使子问题的规模大致相同 换句话说 将一个问题分成大小相等的 k 个子问题的处理方法是行之有效的 许多问题可 以取 k 2 这种使子问题规模大致相等的做法是出自一种平衡 balancing 子 问题的思想 它几乎总是比子问题规模不等的做法要好 5 算法代码及运行结果算法代码及运行结果 5 1 分治法 import java util Arrays import java util Scanner public class lianxi public static void main String args System out println 请输入要比较数字的总个数 数组长度 Scanner cin new Scanner System in int a a cin nextInt int arr new int a for int i 0 i a i arr i cin nextInt if i a return int result new int 2 result minMax arr 0 arr length 1 System out println Arrays toString result public static int minMax int arr int l int r int min 0 int max 0 if l r min arr l max arr l else if l 1 r if arr l arr r min arr l max arr r else min arr r max arr l else int mid l r 2 int preHalf minMax arr l mid int postHalf minMax arr mid 1 r min preHalf 0 postHalf 1 preHalf 1 postHalf 1 return new int min max 分治法运行结果 5 2 直接法代码 import java util Scanner public class lianxi2 public static void main String args System out println 请输入要比较数字的总个数 数组长度 Scanner cin new Scanner System in int a a cin nextInt int list new int a for int i 0 i a i list i cin nextInt if i a return int max list 0 int min list 0 for int i 0 i a i 依次比较得最大值 大值下沉 if max list i min list i System out println 这些数字中最大的数字是 max System out println 这些数字中最小的数字是 min 直接法运行结果 5 3 排序法代码 import java util Arrays import java util Scanner public class lianxi2 public static void main String args System out println 请输入要比较数字的总个数 数组长度 Scanner cin new Scanner System in int a a cin nextInt int list new int a for int i 0 i a i list i cin nextInt if i a return 先从小到大进行排序在取最大值与最小值 Arrays sort list System out println 数组按从小到大排序为 for int i 0 i list length i System out print list i System out println 这些数字中最大的数字是 list a 1 System out println 这些数字中最小的数字是 list 0 排序法运行结果 六 六 各种算法比较与分析各种算法比较与分析 虽然所有算法运行结果相同 但是他们的运行时间却是有很大差距的 任 何一种以比较为基础的搜索算法 其最坏情况下的所用时间不可能低于 log n 不可能存在其最坏情况下时间比折半搜索数量级 阶 还低的 算法 事实上 折半搜索所产生的比较树的所有叶结点都在相邻的两个层次上 而且这样的二叉树使得比较树的高度最低 因此 折半搜索是解决搜索问题在 最坏情况下的最优算法 7 7 心得体会心得体会 课程设计终于做完了 虽然有些疲劳和困倦 但带给我很多的收获 算法 设计与分析已经学了一个学期 有许多知识都存在似懂非懂的现象 这种现象 通过实际的上机操作 实际应用 已经减少了许多 对这些知识也有了更深的 理解和很好的掌握 许多困惑 有许多已经通过实际操作解决了 并能够深刻 认识 但也有很多没有明白 通过课程设计 明白做一件事需要考虑到很多方 面的问题的 这些都是要在实践中摸索的 这与平时做练习是不同的 但也因 为平时有许多的练习基础 会使你做起程序来 更加得心应手 另外就是要把 错误总结 有许多错误或者陷阱是平时自己陷进去的 因此很深刻 但也有些 错误或者陷阱是自己还没有接触或者犯过的 这就