02算法及算法的描述方法.ppt

C程序设计 (Programming in C ) 上次课程的内容提要 C语言是一种得到广泛应用的高级程序设计语言 用高级程序语言编写的程序需要进行翻译才能被计算机执行，对于C语言程序，该翻译过程由C编译器完成 明确本课程的学习目标：初步掌握程序设计基本知识和良好的程序设计风格 用计算机解决问题的首要步骤是分析问题并设计算法 算法描述了给定问题的解题步骤 流程图是一种算法描述方法 素性判别 素性判别就是给定一个正整数，判定其是否为素数 素性判别 求最大公约数 设有两个正整数m和n，如何求其最大公约数？ 求最大公约数流程图 这次课的主要内容 结构化方法的基本结构：顺序结构、选择结构、循环结构 其他算法描述方法 N-S盒图方法 伪代码方法 三种基本结构 1966年，Bohra和Jacopini提出了以下三种基本结构，作为构造算法的基本单元 顺序结构 选择结构 循环结构 顺序结构和选择结构的流程图如下图所示 三种基本结构 循环结构 当型循环结构(while型循环）如图循环结构1所示 直到型循环结构(Until型循环) 如图循环结构2所示 基本结构小结 只有一个入口 只有一个出口 结构中的每一部分都存在一条从入口到出口的路径 结构内不存在“死循环” 计算1+2+…+100的流程图 判断闰年的流程图 判断闰年的流程图 判断闰年的流程图 求最大公约数流程图 求最大公约数流程图 求最大公约数流程图 流程图的优缺点 优点 直观形象，比较清楚地表现了各个框图的逻辑关系 缺点 占用篇幅较多 对流程线的使用没有限制，允许随意转向可能造成流程混乱，理解困难 其他算法描述方法 用N-S盒图表示算法 用伪代码描述算法 用PAD图描述算法(略) 用计算机语言描述算法(程序) ... 用N-S盒图描述算法 N-S盒图的基本符号 用N-S盒图描述算法 N-S盒图的基本符号 求最大公约数流程图 N-S盒图表示法小结 与流程图相比，N-S盒图 保留了流程图方式直观、形象和易于理解的优点 去掉了流程线，形式上更紧凑 避免了流程的随意跳转，确保了结构化技术 规定一些基本符号 运算符号 简单算术运算符号： +、-、×、/、 mod(整除取余) 关系运算符号: ＞、≥、＜、≤、＝、≠ 逻辑运算符号: and 、or、not 括号: (、) 用于表示某种对象名字的符号 以英文字母开头的字母、数字符号串 例如：sum, price, i, m, k, n, a1, a2 其他(处理、语句) 赋值: ← ，例如 i ← 1 如果p成立则A否则B: if p then A else B 当p成立时，则A: while p do A do A while p 输入和输出(打印) ：input、print 基本块起、止符号: {、 } 算法开始和结束：BEGIN、END 伪代码算法中基本符号的使用 运算符号（a ← 5；b ← 3） 简单算术运算符号： +、-、×、/、 mod(整除取余) 例如：a+b、a-b、a×b、a/b、a mod b 关系运算符号: ＞、≥、＜、≤、＝、≠ 成立：true(Yes、Y) 不成立：false(No、N) 括号: (、) 伪代码算法中基本符号的使用 逻辑运算 逻辑运算符号: and 、or、not 并且：and 或者：or 非(不是)：not 伪代码算法中基本符号的使用 选择结构 如果p成立则A否则B: if p then A else B 伪代码算法中基本符号的使用 循环结构 当p成立时，则A: while p do A 伪代码描述计算1+2+…+100的算法 伪代码算法：求最大公约数 伪代码算法：求最大公约数 伪代码算法：素性判别 本次课程的内容提要 结构化方法的三种基本结构 顺序结构、选择结构、循环结构 如果一个算法不能分解为若干个基本结构，则不是一个结构化的算法 在计算机软件技术的发展过程中，结构化是一种重要的技术 流程图描述算法时直观形象，易于理解，但是不加限制地使用流线随意转向，可能使算法的逻辑难以理解 N-S盒图克服了流程图表示方法的缺点，能更好地体现结构化思想 伪代码表示算法时比较灵活，也易于修改，通常采用比较接近于计算机程序的符号 流程图、N-S盒图、伪代码都是常用的算法描述方法，必须掌握其中的一种或多种描述方法 下次课的主要内容 自顶向下、逐步求精方法 筛选法求素数 简单排序算法 分治法 作业 有两个杯子A和B，A中盛水，B中盛果汁，考虑一下如何能互换A和B中的内容。 输入10个整数，设计算法，找出其中最大的数并打印输出。 设计算法，找出2~255之间的所有素数。 算法1：计算1+2+…+100 BEGIN S ← 0; I ← 1; while (I ≤100)