计算机软件算法和计算机软件理论基础.ppt

第三章 计算机软件
算法和计算机软件理论基础
计算机软件及计算机软件技术
操作系统
程序设计语言及语言处理程序
计算机软件算法和计算机软件理论基础
算法和数据结构
算法
数据结构
计算机软件算法和计算机软件理论基础
算法与程序
软件的主体是程序，程序的核心是算法
要使计算机解决某个问题，首先针对问题设计一个解题步骤，然后在根据解题步骤编写程序并交给计算机执行。
这个“解题步骤”就是算法。
计算机软件算法和计算机软件理论基础
算法与程序
算法（Algorithm）：问题求解规则的一种过程描述。
在算法中要精确定义一系列规则，这些规则指定了相应的操作顺序，目标是在有限的步骤内得到所求问题的解答。
算法设计方法：由粗到细，由抽象到具体的逐步求精方法
程序：对解题对象和解题步骤用程序语言进行的一种描述。
程序中用具有一定结构的变量来表示问题的对象
用函数和语句来实现解题的操作
“算法”和“数据结构”是编写程序所要首先考虑的两个重要方面。
计算机软件算法和计算机软件理论基础
算法
算法就是解决问题的方法与步骤
计算机软件算法和计算机软件理论基础
计算机求解问题的步骤
(1) 确定并理解问题；
(2) 寻找解决问题的方法与步骤，并将其表示成算法(Algorithm) ；
(3) 使用某种程序设计语言描述该算法(编程), 并进行调试；
(4) 运行程序，获得问题的解答；
(5) 进行评估，改进算法和程序
计算机软件算法和计算机软件理论基础
算法是解决问题的方法与步骤
例：有三个硬币，其中一个是伪造的，另两个是真的，伪币与真币重量略有不同。现在提供一座天平，如何找出伪币呢？
分析：
方法明确而有序
按提供的条件进行操作
任何人均可仿照进行(共享智能)
开始
C是伪币
B是伪币
A是伪币
A＝B？
A＝C？
是
否
否
是
计算机软件算法和计算机软件理论基础
关于算法的三方面问题
如何确定算法（算法设计）？
如何表示算法（算法表示）？
如何使算法更有效（算法分析）？
计算机软件算法和计算机软件理论基础
例如，要对包含n个整数元素的数组A按元素值由小到大排序。
第1遍，给出粗略的思路：
① 从所有整数中选一个最小的，作为已排好序的第一个数；
② 在剩下的未排序整数中选出最小的，放在已排好序列的最后一个数后面；
③ 反复执行②，直到所有整数都放到已排好的序列中。
第2遍，细化，考虑“序列存放在何处” ，如何“反复执行”等。用“伪代码” 描述为：
for i=1 to n
{选出A[i]到A[n]中最小的元素，设为A[j]；
交换A[i]和[j];
}
计算机软件算法和计算机软件理论基础
筛选法排序
2
1
3
4
6
2
1
3
4
6
不交换
交换
3
1
2
4
6
4
1
2
3
6
交换
交换
6
1
2
3
4
6
1
2
3
4
交换
6
2
1
3
4
交换
交换
6
3
1
2
4
6
4
1
2
3
6
4
1
2
3
交换
6
4
2
1
3
6
4
3
1
2
交换
6
4
3
1
2
交换
6
4
3
2
1
第一轮比较
第二轮比较
第三轮比较
第四轮比较
计算机软件算法和计算机软件理论基础