逐步求精和分治法.ppt

SchoolofComputerScience Engineering XidianUniversity China C程序设计 ProgramminginC 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China2 这次课的主要内容 自顶向下 逐步求精方法筛选法求素数简单排序算法几种基本的算法设计方法枚举法 迭代法 递推与递归法 分治法 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China3 自顶向下 逐步求精 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China4 自顶向下 逐步求精 自顶向下 逐步求精 的基本思路是 先进行整体规划 再进行详细设计 先抽象后具体 下面看一个例子 即筛法求素数大约在公元前250年 古希腊数学家厄拉多赛 Eratosthenes 提出一个造出不超过N的素数构造法 称为厄拉多赛筛法 它基于这样一个简单的性质 如果n N 且n是合数 则n必为一个不大于N的平方根的素数所整除 基本方法如下 先列出不超过的全体素数 设为2 p1 p2 pk 然后依次排列2 3 N 在其中留下p1 2 而把p1的倍数全部划掉 再留下p2 而把p2的倍数全部划掉 继续该过程 直到最后留下pk而划去pk的全部倍数 所有留下的数就是不超过N的全体素数 1914年Lehmer发表了1 10006721的素数表 1951年Kulik等人扩大到10999997 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China5 筛法求素数 求出不大于正整数N的所有素数排列2 3 N 取出2 再从中删除2的倍数 取出3 再从中删除3的倍数 剩余的数中最小者k必为素数 取出k 再从中删除k的倍数 重复这一步 直到所有的数都已取走或被删除 所有取出的数汇集在一起就形成了不大于N的素数表 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China6 筛法求素数 设有两个筛子 分别用sieve和prime标识 初始时prime为空 元素2 n放在sieve中算法结束时 sieve为空 而不大于n的素数都放在prime中 k 找出sieve中最小的数 开始 结束 求精 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China7 简单排序算法 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China8 三个整数排序 Y N 输出a b c的值 输入三个整数a b c a b 交换a和b的值 a c 交换a和c的值 b c 交换b和c的值 Y Y N N 开始 结束 算法 三个整数排序BEGINinputa b c 输入三个整数 ifa bthen交换a和b的值 ifa cthen交换a和c的值 ifb cthen交换b和c的值 printa b cEND 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China9 五个整数排序 设有五个整数需要进行排序 算法 三个整数排序BEGINinputa b c 输入三个整数 ifa bthen交换a和b的值 ifa cthen交换a和c的值 ifb cthen交换b和c的值 printa b cEND 算法 五个整数排序BEGINinputa b c d e 输入五个整数 ifa bthen交换a和b的值 ifa cthen交换a和c的值 ifa dthen交换a和d的值 ifa ethen交换a和e的值 找出最大数并放在a中 ifb cthen交换b和c的值 ifb dthen交换b和d的值 ifb ethen交换b和e的值 找出第二大的数并放在b中 ifc dthen交换c和d的值 ifc ethen交换c和e的值 找出第三大的数并放在c中 ifd ethen交换d和e的值 找出第四大的数并放在d中 printa b c d eEND 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China10 排序时数据集中存放在一段空间中 在前面的排序算法中 存放数据的位置 以a b c d e表示 之间没有联系下面 约定排序时数据集中存放在一段存储空间中例如 下面的7个整数连续地存放在位置1 位置7中 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China11 简单排序方法 简单排序方法有多种 这里我们介绍冒泡 起泡 排序法 冒泡排序法 bubblesort 的基本思想是 通过对相邻元素的比较和交换 使全部记录排列有序 冒泡排序的过程 对每两个相邻的元素进行比较 若为逆序 则将两者交换 这样的操作反复进行 直至全部记录都比较 交换完毕为止 如此经过一趟冒泡排序之后 就将关键字最大 或最小 的元素安排在最后一个 或第一个 元素的位置上 然后 对后n 1个元素重复进行同样的操作 则将具有次大 或次小 元素安排在倒数 或正数 第二个元素的位置上 重复以上过程 直至没有元素需要交换时为止 至此 整个序列的记录按关键字由小到大的顺序排列完毕 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China12 冒泡排序方法 43 18 9 13 55 7 43 以7个元素为例说明冒泡排序位置1 位置7的元素初始排列如下所示 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China13 冒泡排序方法 43 18 9 13 55 7 43 第一步 令位置1和位置2的元素比较 若位置1的元素大 则交换 交换 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China14 冒泡排序方法 第二步 令位置2和位置3的元素比较 若位置2的元素大 则交换 交换 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China15 冒泡排序方法 第三步 令位置3和位置4的元素比较 若位置3的元素大 则交换 交换 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China16 冒泡排序方法 第四步 令位置4和位置5的元素比较 若位置4的元素大 则交换 不交换 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China17 冒泡排序方法 第五步 令位置5和位置6的元素比较 若位置5的元素大 则交换 交换 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China18 冒泡排序方法 第六步 令位置6和位置7的元素比较 若位置6的元素大 则交换 交换 最大元素被交换到最后一个位置 位置7 下一趟则需将次大元素交换到倒数第二个位置 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China19 冒泡排序方法 第七步 令位置1和位置2的元素比较 若位置1的元素大 则交换 交换 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China20 冒泡排序方法 第八步 令位置2和位置3的元素比较 若位置2的元素大 则交换 交换 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China21 冒泡排序方法 第九步 令位置3和位置4的元素比较 若位置3的元素大 则交换 不交换 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China22 冒泡排序方法 第十步 令位置4和位置5的元素比较 若位置4的元素大 则交换 交换 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China23 冒泡排序方法 第十一步 令位置5和位置6的元素比较 若位置5的元素大 则交换 不交换 次大元素被交换到倒数第二个位置 位置6 下一趟则需将第三大元素交换到倒数第三个位置 依此类推 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China24 冒泡排序方法 以7个元素为例说明冒泡排序 存放每个元素的位置以序号进行标记经过六趟冒泡排序后 位置1 位置7中的元素排列如下所示 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China25 冒泡排序算法 7个元素进行冒泡排序时 需要六趟 i 1 i 6 开始 结束 Y i i 1 N 进行第i趟冒泡排序 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China26 冒泡排序算法 位置1 位置7以a1 a2 a7表示冒泡排序算法流程图如右所示 i 1 i 6 开始 结束 Y i i 1 N N j 1 j 7 i Y 比较aj和aj 1如果aj aj 1则交换 j j 1 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China27 几种基本算法设计方法 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China28 枚举法 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China29 基本算法之枚举法 枚举法也称为穷举法 它的基本思想是 首先根据问题的部分条件预估答案的范围 然后在此范围内对所有可能的情况进行逐一验证 符合所举条件的情况均为答案 直到将所有情况验证完毕 例如 百钱百鸡问题 中国古代数学家张丘建在他的 算经 中曾提出著名的 百钱百鸡问题 其题目如下 鸡翁一 值钱五 鸡母一 值钱三 鸡雏三 值钱一 百钱买百鸡 翁 母 雏各几何 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China30 百钱百鸡问题 例如 百钱百鸡问题 中国古代数学家张丘建在他的 算经 中曾提出著名的 百钱百鸡问题 其题目如下 鸡翁一 值钱五 鸡母一 值钱三 鸡雏三 值钱一 百钱买百鸡 翁 母 雏各几何 解 设x y z分别代表公鸡 母鸡 小鸡的数量 根据题意列方程 据题意可知 x y z的范围一定是0到100的正整数 那么 最简单的解题方法是 假设一组x y z的值 直接代入方程组求解 即在各个变量的取值范围内不断变化x y z的值 穷举x y z全部可能的组合 若满足方程组则是一组解 这样即可得到问题的全部解 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China31 迭代法 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China32 基本算法之迭代法 迭代法是一种数值近似求解的方法 在科学计算领域中 许多问题需要用这种方法解决 迭代法的特点是 把一个复杂问题的求解过程转化为相对简单的迭代算式 然后重复执行这个简单的算式 直到得到最终解 例如 计算S 1 2 3 4 100 其迭代方法如下 首先确定迭代变量S的初始值为0 其次确定迭代公式s i s 当i分别取值1 2 3 4 100时 重复计算迭代公式s i s 迭代100次后 即可求出S的值 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China33 基本算法之迭代法 迭代法更主要的应用是数值的近似求解 它既可以用来求解代数方程 又可以用来求解微分方程 在科学计算领域 人们时常会遇到求微分方程的数值解或解方程f x 0等计算问题 这些问题无法用求和或求均值那样的直接求解方法 为此 人们只能用数值计算的方法求出问题的近似解 而解的误差是人们可以估计和控制的 迭代法是一种数值近似求解的方法 在科学计算领域 许多问题需要用这种方法解决 例如 求方程x3 x 1 0在x 1 5附近的一个根 具体方法在数值计算课程中学习 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China34 递推与递归法 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China35 基本算法之递推和递归法 例如 计算级数 一般给出数列后项与前项的递推公式 要求计算数列通项 1 3 5 7 递推公式 f 1 1 f n 2 f n 1 1 2 4 8 递推公式 f 1 1 f n 2 f n 1 1 2 6 24 递推公式 f 0 1 f n n f n 1 1 1 2 3 5 8 递推公式 f 1 1 f 2 1 f n f n 1 f n 2 以上数列的共同特点是 在数列的未知项与已知项之间存在着一定关系 借助于已知项和这一关系 就可逐项求出未知项 计算这些数列通常用递推和递归两种算法 递推 递归 法是一种利用问题本身所具有的一种递推 递归 关系求解问题的一种方法 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China36 基本算法之递推和递归法 要计算15 可以从递推初始条件f 0 1出发 应用递推通项公式f n n f n 1 逐步求出f 1 f 2 f 3 f 14 即由简到繁逐次迭代 直到最后求出f 15 的值 用递推法求n的阶乘 f 0 1 f n n f n 1 用递归法求15 15 15 14 14 14 13 2 2 1 1 1 0 0 1递归法也是利用递推公式进行求解 所不同的是 它是由繁化简 用简单的问题和已知的操作运算来解决复杂的问题 这里不宜详细介绍 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China37 分治法 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China38 基本算法之分治法 分治法是一种解决问题的基本方法 简而言之 就是 分而治之 任何一个可以用计算机求解的问题所需的计算时间都与其规模有关 问题的规模越小 越容易直接求解 解题所需的计算时间也越少 分治法 divideandconquer 的基本思想是 将一个难以直接解决的大问题 分割成一些规模较小的相同问题 以便各个击破 分而治之 将一个规模为n的问题逐步分解为k个规模更小的子问题 这些子问题互相独立且与原问题性质相同 逐个解决分解出的子问题 由这些子问题的解构造出原问题的解 当k 2称为二分法 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China39 汉诺塔问题 问题 将A柱子上的n个圆盘借助于B柱子移到C柱子上去 问如何移动圆盘 规则 每次只能移动一张圆盘圆盘只能在这三个柱上存放大盘不能压在小盘上面 A 源 B 辅助 C 目的 西安电子科技大学计算机学院 SchoolofComputerScience Engineering XidianUniversity China40 汉诺塔问题 将A柱子上的n个圆盘分成两部分 1个园盘和n 1个园盘移动园盘方法 第一步 将A柱子的上面n 1个园盘移动到B柱子上面第二步 将A柱子上剩下的那个园盘移动到C柱子上面第三步 将B柱子上的n 1个园盘移动