文档介绍：3-4算法和数据结构
341算法
计算机求解问题的步骤
(1)确定并理解问题;
(2)寻找解决问题的方法与步骤,并将其表示成算法
(Algorithm):
(3)使用某种程序设计语言描述该算法(编程),并
进行调试;
(4)运行程序,获得问题的解答;
(5)进行评估,改进算法和程序
34算法和软堤结构
1 .什么是算法?
算法是解决问题的方法与步骤
■例:有三个硬币,其中一个是伪造的,另两个是真的,伪币与真币重量略有不同。现在提供一座天平, 如何找出伪币呢?
■分析:
方法明确而有序
按提供的条件进行操作
任何人均可仿照进行(共享音能)
34算法和数据结构
关于算法的三方面问题
如何确定算法(算法设计)?如何表示算法(算法表示)
■如何使算法更有效(算法分析)?
2 •算法设计举例
7
例:对整数进行排序
问题:任给一组(n个)整数,将它们从小到大进行排序
■粗略的思路:
①从所有整数中选一个最小的,作为已排序的第一个数
②从剩下未排序整数中选最小的数,添加到已排序整数的后面
③反复执行步骤②,直到所有整数都处理完毕
■进一步细化:
把待排序的整数放在一个数组a中,每个整数是数组a中的一个元素:a(1),a(2),a(3),…,a(n),
排好序的元素在a的前面部分,无序的元素留在后面,每“循环”一次,有序部分增加1个元素,无序部分减少1个元素每次“循环”只需在数组的无序元素部分选出最小的数反复进行次即可得到排序后的结果
“直接选择排序”算法举例
数组的初态全部是未排序元素在未排序元素中确定最小数位置与首元素交换,第1次循环结束在未排序元素中确定最小数位置与首元素交换,第2次循环结束在未排序元素中确定最小数位置与首元素交换,第3次循环结束
第6次循环后,排序结束
1 E s m同
I3
回E
mm
Imm
Tl
2 n
可
fl
T回
EH[Z1EI1S □四 I 凹
Private sub sort ( a() as integer, n as integer)
dim i as integer, j as Integer ,k as Integer'定义 3 个整型变 it for
1=1 to n-1 ,
for k=i+1 to n
if a(i)>a(k) then j=k next k
t=a(i):a(i)=a(j):a(j)=t
next i
End Sub
11
3 ,算法的表示
算法的表示方法
■文字说明
流程图表示
■用N-S盒图表示算法
用PAD图描述算法
伪代码(一种介于自然语言和程序设计语言之间
的文字和符号表达工具)
13
自然语言描述
■“比较A与E的重量,若A = B,则C是伪造的;否则再比校 A与C的重量,若A = C,则E是伪造的;否则A是伪造的「
缺点:
容易产生歧义,很难“精确”地进行表达叙述冗长,很难清楚地表达算法的逻辑流程
它描述了算法所执行操
15
算法的流程图表示
■流程图由结点和有向边构成,作的顺序及执行操作的条件
■流程图符号:
00 I 1
端点符 处理
判断流程线
比文字描述简明,但当算法比较复杂时,理解困难, 容易产生错误