文档介绍：乔林
计算机程序设计基础
Email: ******@.
Tel: 62792961
第十一章算法设计与分析
学习目标
了解大多数问题都可以用几种不同的算法解决
掌握什么样的算法是正确的
了解解决同一问题的不同算法其性能各不相同
了解算法复杂度的概念,用它可对随着问题规模成比例增长的运行时间的变化作定性分析
学会用大“O”符号表示算法复杂度;掌握最常见的复杂度类型,并且理解每个复杂度类型的性能特点
算法的概念与特征
算法的由来
解决问题的方法与步骤
演算过程的抽象表述
算法的基本特征
有穷性:算法必须能够在有限步内终止
确定性:每一步骤的顺序和内容不能有二义性
有效性:所有操作都有明确含义并能够实现
有零个或多个输入:算法应该接受处理数据
有一个或多个输出:算法必须能够输出结果
正确性不是算法的特征,算法的正确性由设计者保证!
算法举例一
33 幻方
用数字1~9组成33方阵,各行各列各对角线的数字之和为15
算法步骤
S1:把1放在第一行中间的一格
S2:在右上方斜对角线方向给出下一个自然数
在此过程中,若该数已出方框,则将其写在该行或该列另一端
S3:写完三个数后,将第四个数写在第三个数下
S4:重复上述操作, 直到格子填满为止
算法举例一
1
算法举例一
2
1
算法举例一
2
1
2
算法举例一
2
1
3
2
算法举例一
2
1
3
3
2
算法举例一
2
1
3
3
4
2