逐步求精和分治法

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和 …… 此处隐藏：2909字，全部文档内容请下载后查看。喜欢就下载吧 ……