1、第第6章章 程序设计基础程序设计基础 6.1 算法与程序 6.2 Alice 程序设计初步 6.1 算法与程序算法与程序 本节要点本节要点 6.1.1 算法的基本概念 6.1.2 算法的表示 6.1.3 算法设计的基本方法 6.1.4 算法的评价 6.1.5 程序与程序设计语言 第第6 6章章6.16.1节节 6.1.1 算法的基本概念算法的基本概念 定义定义 有基本运算及规定的运算顺序所构成的完整的解题步骤信息。 算法就是计算机解题的过程 特征特征 可行性可行性 算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步， 即每个计算步都可以在有限时间内完成 确定性确定性 算法的每一步骤必
2、须有确切的定义 有穷性有穷性 算法必须能在执行有限个步骤之后终止 输入输入 算法执行的结果与输入有关，一个算法有0个或多个输入 输出输出 一个算法有1个或多个输出，没有输出的算法是无意义的 第第6 6章章6.16.1节节6.1.16.1.1 6.1.2 算法的表示算法的表示 自然语言自然语言 通俗易懂，不需要专门训练 歧义性，难以表达复杂的算法 不便翻译成计算机程序设计语言程序 程序流程图程序流程图 起止框 ：流程开始或结束 输入/输出框 ：输入或输出 处理框 ：对基本功能的描述 判断框 ：根据条件是否满足，进行路径选择 流向线 ：流程的路径和方向 第第6 6章章6.16.1节节6.1.26.
3、1.2 输入3个数，打印输出其中最大的数 伪代码伪代码 用介于自然语言和计算机语言之间的文字和符号（包括数学符号）来 描述算法 例：输入3个数，打印输出其中最大的数。可用如下的伪代码表示： Begin（算法开始） 输入 x，y，z IF xy 则 xMax 否则 yMax IF zMax 则 zMax Print Max End （算法结束） 计算机程序设计语言计算机程序设计语言 6.1.3 算法设计的基本方法算法设计的基本方法 列举法列举法 归纳法归纳法 递归法递归法 必须有递归的终止条件 过程的描述中包含它本身 例：计算斐波那契数列的第n项的函数F(n) F(n)=F(n-1)+F(n-2
4、) （n0） F(1)=1,F(0)=0 分治法分治法 把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问 题分成更小的子问题直到最后子问题可以简单的直接求解 回溯法回溯法 第第6 6章章6.16.1节节6.1.36.1.3 6.1.4 算法的评价算法的评价 正确性正确性 可读性可读性 健壮性健壮性 复杂性复杂性 第第6 6章章6.16.1节节6.1.46.1.4 6.1.5 程序与程序设计语言程序与程序设计语言 程序程序 告诉计算机要做什么的一系列指令，每条指令是一个要执行的动作 程序设计语言程序设计语言 机器语言 CPU可以识别的一组由0、1序列构成的机器指令的集合 例如：一条表
5、示加法的机器指令：00101100 00001010 汇编语言 用助记符来表示每一条机器指令 例如：ADD A，10 高级语言 面向过程的语言：Basic、Fortran、C 面向对象的语言：C+、Java 面向对象与可视化的语言：Visual Basic、Delphi、Visual C+ 非过程化的语言：数据库查询语句SQL 第第6 6章章6.16.1节节6.1.56.1.5 编译型语言处理程序功能示意图 程序与算法、数据结构之间的关系程序与算法、数据结构之间的关系 程序在描述算法的同时，必须完整地描述作为算法的操作对象的数据 结构 算法思想决定了程序的质量和性能 算法建立在数据结构的基础之上。
