1、 第二章第二章 算法算法 2 2.1 .1 算法的概念算法的概念 要利用计算机处理问题,光学习语言要利用计算机处理问题,光学习语言的语法规则还不够,最重要的是要学会的语法规则还不够,最重要的是要学会针对各类型的问题,拟定出有效的解题针对各类型的问题,拟定出有效的解题方法和步骤。方法和步骤。解题方法和步骤就是算法解题方法和步骤就是算法。算法算法: 为了解决一个问题而采取的有限步骤。为了解决一个问题而采取的有限步骤。 计算机算法计算机算法: 如何使计算机一步一步地工作的具体过程。如何使计算机一步一步地工作的具体过程。 利用计算机处理问题的步骤: 1)设计好算法算法设计; 2)用计算机语言实现算法程
2、序设计。 算法必须是“有效”的。 算法设计还要充分考虑算法的好坏。 衡量算法好坏的主要标准: 程序简练。 执行速度快。 占空间少。 例:考虑 的算法。算法:直接表达。直接用语句 s=1+2+3+4+5+6+7+8+9+10当项数较多时该算法不适用s=i110算法:迭代法(累加求和法) s=1+2+3+4+5+6+7+8+9+10 算法步骤: s i 使s=0 + 使i=1 累加器 记数器 s+is i+1i 若i10转,否则转 输出s01123364105该算法通用,是好算法2.2 2.2 算法的表示算法的表示 算法需要有统一的表示方法算法需要有统一的表示方法 常用的表示方法有:常用的表示方法
3、有: 自然语言自然语言 流程图流程图 结构化流程图结构化流程图 N-SN-S流程图流程图. . 1、自然语言自然语言 对于计算对于计算 s=1+2+3+4+5+6+7+8+9+10s=1+2+3+4+5+6+7+8+9+10 用自然语言表示为:用自然语言表示为: 使使s=0s=0 (s s为累加器)为累加器) 使使i=1i=1 (i i为计数器)为计数器) s+iss+is (累加求和公式)(累加求和公式) i+1ii+1i (计数器加(计数器加1 1) 若若i10i10转转, ,否则转否则转 输出输出s s的值的值 特点:通俗易懂、文字冗长、含义不大严格。 2、流程图流程图 用流程图符号表示
4、算法。 常用的流程图符号 起止框 输入输出框 处理框 流程线 判断框 对于计算 s=1+2+3+4+5+6+7+8+9+10 用流程图表示为:s+i s i+1 i S+i s S+i s i10 输出s 0 s 1 i 直观形象,易于理解,次序清楚YN3、结构化流程图结构化流程图 传统的流程图有一个弊端:对流程线没有严格的限制,对于较复杂的算法可能会变成乱麻一般(BS型算法)。 为克服这一弊端,提出了由三个基本结构组成算法流程图的思想: 结构化流程图 三个基本结构: 顺序结构 按固定顺序(从上到下或从左到右)执行的结构。 ABab 选择结构 根据条件P选择执行哪一个分支。 成立 不成立 pA
5、Bab成立不成立例:计算 y= 1/x 当x0时 y= 10000 当x=0时 的算法流程图图: 选择结构 输入x X=0? 10000y 1/xy 输出y YN 循环结构 重复执行某些操作的结构。 分为两种: 当型循环和直到型循环。 当型循环 直到型循环 P1AAP2aabbYYNN 可以看出,每个基本结构都只有一个入口和一个出口,因此,用三个基本结构构成的流程图不会象乱麻一般,用三个基本结构构成的流程图就成为结构化流程图,用结构化流程图描述的算法称为结构化算法,相应的程序设计就称为结构化程序设计。 观察前例: 0 s 1 i S+i s i+1 i i10 输出s 顺序结构循环结构yn4 N-SN-S流程图流程图N-S流程图的三个基本结构: ABP成立不成立ABAB当P1直到P2顺序结构选择结构循环结构例:计算 y= 1/x 当x0时 y= 10000 当x=0时 的N-S流程图:输入x X=0?是否10000y 1/xy 输出y 例: 计算 s=1+2+3+4+5+6+7+8+9+10 的N-S流程图: i10 直到i10 直到型 当型 0 s 1 i 输出s 1 i 0 s s+i s i+1 i s+i s i+1 i 输出s