逐步求精和分治法

C程序设计 (Programming in C )

西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China

上次课程的内容提要

结构化方法的三种基本结构 顺序结构、选择结构、循环结构 在计算机软件技术的发展过程中，结构化是一种重要的技术 一个算法是描述对某类问题进行求解的一个计算过程 算法常用流程图、N-S盒图和伪代码等形式描述 流程图描述算法时直观形象，易于理解，但是不加限制地使流线随意 转向，可能使算法的逻辑难以理解 N-S盒图克服了流程图表示方法的缺点，能更好地体现结构化思想 伪代码表示算法时比较灵活，也易于修改，通常采用比较接近于计算 机程序的符号 必须掌握流程图、伪代码等常用的算法描述方法 如果一个算法不能分解为若干个基本结构，则不是一个结构化的算法

本次课内容西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China

三种基本结构

顺序结构和选择结构的流程图如下图所示a成立

a条件p不成立 成立

a

A B A

条件p

不成立

B b选择结构-1

A b选择结构-2

b顺序结构

西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China

三种基本结构

a 循环结构 成立 不成立 当型循环结构(while型循环)如图循环结构-1所示 条件p 直到型循环结构(Until型循环) 如图循环结构-2所示 A a条件p成立 不成立

B a b

A成立

选择结构-1

A

条件p不成立 成立

a条件p不成立

b循环结构-1

b循环结构-2

A

注意循环结构与选择结构的区别

b选择结构-2西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China

基本结构小结

只有一个入口 只有一个出口 结构中的每一部分都存在一条从入口到出口的路径 结构内不存在“死循环”a成立 不成立

aA B

p A b

B死循环

西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China

这次课的主要内容

自顶向下、逐步求精方法 筛选法求素数 简单排序算法 几种基本的算法设计方法 枚举法、迭代法、递推与递归法、分治法

西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China

自顶向下、逐步求精

西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China

自顶向下、逐步求精

“自顶向下、逐步求精”的基本思路是：先进行整体规划、再 进行详细设计，即先抽象后具体。 下面分析一个例子：筛法求素数

大约在公元前250年，古希腊数学家厄拉多赛(Eratosthenes)提出一 个造出不超过N的素数构造法，称为厄拉多赛筛法。 它基于这样一个简单的性质：如果n≤N,且n是合数，则n必为一个不 大于N的平方根的素数所整除。 基本方法如下：先列出不超过 N 的全体素数，设为2=p1< p2<... < pk ≤ N ,然后依次排列2,3,...,N,在其中留下p1 ( =2 ) ,而把p1 的倍数全部划掉，再留下p2 ,而把p2的倍数全部划掉，继续该过程， 直到最后留下pk而划去pk的全部倍数，所有留下的数就是不超过N的 全体素数。

1914年Lehmer发表了1~10006721的素数表，1951年Kulik等人扩大到 10999997,1976年，贝思和赫德森计算出1.2×1012内的素数表，…

西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China

筛法求素数

求出不大于正整数N的所有素数 排列2,3,...,N,取出2,再从中删除2的倍数； 取出3,再从中删除3的倍数； 剩余的数中最小者k必为素数，取出k,再从中删除k的倍 数；重复这一步，直到所有的数都已取走或被删除； 所有取出的数汇集 在一起就形成了不大于N的素数表

西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China

筛法求素数开始置prime为空，sieve包含整 数2,3,...,n

设有两个筛子，分别用sieve和 prime标识，初始时prime为空， 元素2~n放在sieve中 算法结束时，sieve为空，而不大 于n的素数都放在prime中j←k

sieve不为空？

N

Yk←找出sieve中最小的数

N将k放入prime中

j≤n?

Y 求精j表示k的 倍数从sieve中去掉j j←j+k

从sieve中去掉k及其倍数

结束西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China

简单排序算法

西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China

三个整数排序开始输入三个整数a,b,c a<b? N a<c? N b<c? N 输出a,b,c的值 结束西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China

Y Y

交换a和b的值 交换a和c的值 交换b和c的值

Y

算法：三个整数排序 BEGIN input a,b,c; /*输入三个整数*/ if a<b then 交换a和b的值; if a<c then 交换a和c的值; if b<c then 交换b和c的值; print a,b,c; END

五个整数排序算法：五个整数排序 BEGIN input a,b,c,d,e; /*输入五个整数*/ if a<b then 交换a和b的值; if a<c then 交换a和c的值; if a<d then 交换a和d的值; if a<e then 交换a和e的值; /*找出最大数并放在a中*/ 推广至5个 整数排序 if b<c then 交换b和c的值; if b<d then 交换b和d的值; if b<e then 交换b和e的值; /*找出第二大的数并放在b中*/ if c<d then 交换c和d

的值; if c<e then 交换c和e的值; /*找出第三大的数并放在c中*/ if d<e then 交换d和e的值; /*找出第四大的数并放在d中*/ print a,b,c,d,e; END13

算法：三个整数排序 BEGIN input a,b,c; /*输入三个整数*/ if a<b then 交换a和b的值; if a<c then 交换a和c的值; if b<c then 交换b和c的值; print a,b,c; END

西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China

排序时数据集中存放在一段空间中

在前面的排序算法中，存放数据的位置(以a、b、c、d、 e表示)之间没有联系 下面，约定排序时数据集中存放在一段存储空间中 例如：下面的7个整数连续地存放在位置1~位置7中1 2 3 4 5 6 7 43 18 9 13 55 7 4314

西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China

简单排序方法

简单排序方法有多种，这里我们介绍冒泡(起泡)排序法。

冒泡排序法(bubble sort)的基本思想是:通过对相邻元素的比较和 交换，使全部记录排列有序。 冒泡排序的过程：对每两个相邻的元素进行比较，若为逆序，则将 两者交换，这样的操作反复进行，直至全部记录都比较、交换完毕 为止。如此经过一趟冒泡排序之后，就将关键字最大(或最小)的元 素安排在最后一个(或第一个) 元素的位置上。然后，对后n-1个元 素重复进行同样的操作，则将具有次大(或次小)元素安排在倒数(或 正数)第二个元素的位置上。重复以上过程，直至没有元素需要交换 时为止。至此，整个序列的记录按关键字由小到大的顺序排列完毕。

西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China

冒泡排序方法

以7个元素为例说明冒泡排序 位置1~位置7的元素初始排列如下所示 1 2 43 18

3 4 5 6 7

9 13 55 7 43

西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China

冒泡排序方法

第一步：令位置1和位置2的元素比较，若位置1的元素大，则交换

1 2 3 4 5 6 7

43 18 9 13 55 7 43交换

1 2 3 4 5 6 7

18 43 9 13 55 7 43

西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China

冒泡排序方法

第二步：令位置2和位置3的元素比较，若位置2的元素大，则交换

1 2 3 4 5 6 7

18 43 9 13 55 7 43交换

1 2 3 4 5 6 7

18 9 43 13 55 7 43

西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China

冒泡排序方法

第三步：令位置3和位置4的元素比较，若位置3的元素大，则交换

1 2 3 4 5 6 7

18 9 43 13 55 7 43交换

1 2 3 4 5 6 7

18 9 13 43 55 7 43

西安电子科技大学计算机学院 - School of Computer Science & Enginee

ring, Xidian University, China

冒泡排序方法

第四步：令位置4和位置5的元素比较，若位置4的元素大，则交换

1 2 3 4 5 6 7

18 9 13 43 55 7 43不交换

1 2 3 4 5 6 7

18 9 13 43 55 7 43

西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China

冒泡排序方法

第五步：令位置5和位置6的元素比较，若位置5的元素大，则交换

1 2 3 4 5 6 7

18 9 13 43 55 7 43交换

1 2 3 4 5 6 7

18 9 13 43 7 55 43

西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China

本文来源：https://www.bwwdw.com/article/9w14.html