几种基本的C语言算法设计 PPT课件.ppt

几种基本的C语言算法设计_PPT课件C程序设计
(Programming in C )
(计算机学院张淑平)
2005计算机导论
这次课的主要内容
自顶向下、逐步求精方法
筛选法求素数
简单排序算法
几种基本的算法设计方法
枚举法、迭代法、递推与递归法、分治法
自顶向下、逐步求精
自顶向下、逐步求精
“自顶向下、逐步求精”的基本思路是:先进行整体规划、再进行详细设计,即先抽象后具体。
下面看一个例子,即筛法求素数
大约在公元前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。
筛法求素数
求出不大于正整数N的所有素数
排列2,3,...,N,取出2,再从中删除2的倍数;
取出3,再从中删除3的倍数;
剩余的数中最小者k必为素数,取出k,再从中删除k的倍数;重复这一步,直到所有的数都已取走或被删除;
所有取出的数汇集在一起就形成了不大于N的素数表
筛法求素数
设有两个筛子,分别用sieve和prime标识,初始时prime为空,元素2~n放在sieve中
算法结束时,sieve为空,而不大于n的素数都放在prime中
k←找出sieve中最小的数
sieve不为空?
Y
置prime为空,sieve包含整数2,3,...,n
开始
结束
将k放入prime中
从sieve中去掉k及其倍数
N
j ← k
j≤n?
从sieve中去掉j
j ← j + k
Y
N
求精
j表示k的倍数
简单排序算法
五个整数排序
算法:三个整数排序
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中*/
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;
END
推广至5个整数排序
排序时数据集中存放在一段空间中
在前面的排序算法中,存放数据的位置(以a、b、c、d、e表示)之间没有联系
下面,约定排序时数据集中存放在一段存储空间中
例如:下面的7个整数连续地存放在位置1~位置7中
1
2
3
4
5
6
7
43
18
9
13
55
7
43