C程序设计（Programming in C ）.pptVIP

C程序设计 (Programming in C ) 这次课的主要内容 自顶向下、逐步求精方法 筛选法求素数 简单排序算法 几种基本的算法设计方法 枚举法、迭代法、递推与递归法、分治法 自顶向下、逐步求精 “自顶向下、逐步求精”的基本思路是：先进行整体规划、再进行详细设计，即先抽象后具体。 下面看一个例子，即筛法求素数 大约在公元前250年，古希腊数学家厄拉多赛(Eratosthenes)提出一个造出不超过N的素数构造法，称为厄拉多赛筛法。 它基于这样一个简单的性质：如果n≤N，且n是合数，则n必为一个不大于N的平方根的素数所整除。 基本方法如下：先列出不超过 的全体素数，设为2=p1＜ p2＜... ＜ pk ≤ ，然后依次排列2,3,...,N，在其中留下p1 ( =2 ) ，而把p1的倍数全部划掉，再留下p2 ，而把p2的倍数全部划掉，继续该过程，直到最后留下pk而划去pk的全部倍数，所有留下的数就是不超过N的全体素数。 筛法求素数 求出不大于正整数N的所有素数 排列2,3,...,N，取出2，再从中删除2的倍数； 取出3，再从中删除3的倍数； 剩余的数中最小者k必为素数，取出k，再从中删除k的倍数；重复这一步，直到所有的数都已取走或被删除； 所有取出的数汇集 在一起就形成了不大于N的素数表 筛法求素数 三个整数排序 五个整数排序 排序时数据集中存放在一段空间中 在前面的排序算法中，存放数据的位置(以a、b、c、d、e表示)之间没有联系 下面，约定排序时数据集中存放在一段存储空间中 例如：下面的7个整数连续地存放在位置1~位置7中 简单排序方法 简单排序方法有多种，这里我们介绍冒泡(起泡)排序法。 冒泡排序法(bubble sort)的基本思想是:通过对相邻元素的比较和交换，使全部记录排列有序。 冒泡排序的过程：对每两个相邻的元素进行比较，若为逆序，则将两者交换，这样的操作反复进行，直至全部记录都比较、交换完毕为止。如此经过一趟冒泡排序之后，就将关键字最大(或最小)的元素安排在最后一个(或第一个) 元素的位置上。然后，对后n-1个元素重复进行同样的操作，则将具有次大(或次小)元素安排在倒数(或正数)第二个元素的位置上。重复以上过程，直至没有元素需要交换时为止。至此，整个序列的记录按关键字由小到大的顺序排列完毕。 冒泡排序方法 以7个元素为例说明冒泡排序 位置1~位置7的元素初始排列如下所示 冒泡排序方法 第一步：令位置1和位置2的元素比较，若位置1的元素大，则交换 冒泡排序方法 第二步：令位置2和位置3的元素比较，若位置2的元素大，则交换 冒泡排序方法 第三步：令位置3和位置4的元素比较，若位置3的元素大，则交换 冒泡排序方法 第四步：令位置4和位置5的元素比较，若位置4的元素大，则交换 冒泡排序方法 第五步：令位置5和位置6的元素比较，若位置5的元素大，则交换 冒泡排序方法 第六步：令位置6和位置7的元素比较，若位置6的元素大，则交换 冒泡排序方法 第七步：令位置1和位置2的元素比较，若位置1的元素大，则交换 冒泡排序方法 第八步：令位置2和位置3的元素比较，若位置2的元素大，则交换 冒泡排序方法 第九步：令位置3和位置4的元素比较，若位置3的元素大，则交换 冒泡排序方法 第十步：令位置4和位置5的元素比较，若位置4的元素大，则交换 冒泡排序方法 第十一步：令位置5和位置6的元素比较，若位置5的元素大，则交换 冒泡排序方法 以7个元素为例说明冒泡排序，存放每个元素的位置以序号进行标记 经过六趟冒泡排序后，位置1~位置7中的元素排列如下所示 冒泡排序算法 7个元素进行冒泡排序时，需要六趟，用i表示趟数 冒泡排序算法 7个元素进行冒泡排序时，需要六趟，用i表示趟数 基本算法之枚举法 枚举法也称为穷举法，它的基本思想是：首先根据问题的部分条件预估答案的范围，然后在此范围内对所有可能的情况进行逐一验证，符合所举条件的情况均为答案，直到将所有情况验证完毕。 例如，百钱百鸡问题。 中国古代数学家张丘建在他的《算经》中曾提出著名的“百钱百鸡问题”，其题目如下： 鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何？ 百钱百鸡问题 例如，百钱百鸡问题。 中国古代数学家张丘建在他的《算经》中曾提出著名的“百钱百鸡问题”，其题目如下： 鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何？ 基本算法之迭代法 迭代法是一种数值近似求解的方法，在科学计算领域中，许多问题需要用这种方法解决。 迭代法的特点是：把一个复杂问题的求解过程转化为相对简单的迭代算式，然后重复执行这个简单的算式，直到得到最终解。 例如：计算S=1+2+3+4+…+100，其迭代方法如