第3章 简单算法设计 3.1 结构化程序的算法设计 3.2 结构化算法的性质及结构 3.3 结构化算法的描述方法 自然语言 流程图 伪码

Presentation on theme: "第3章 简单算法设计 3.1 结构化程序的算法设计 3.2 结构化算法的性质及结构 3.3 结构化算法的描述方法 自然语言 流程图 伪码"— Presentation transcript:

1 第3章 简单算法设计 3.1 结构化程序的算法设计 3.2 结构化算法的性质及结构 3.3 结构化算法的描述方法 自然语言 流程图 伪码
3.1 结构化程序的算法设计 3.2 结构化算法的性质及结构 3.3 结构化算法的描述方法 自然语言 流程图 伪码 3.4 算法设计范例

2 3.1 结构化程序的算法设计 算法：解决问题的具体方法和步骤。 例1：从键盘输入三个数，找出其中最小的那个数。 算法：1.输入三个数
3.1 结构化程序的算法设计 算法：解决问题的具体方法和步骤。 例1：从键盘输入三个数，找出其中最小的那个数。 算法：1.输入三个数 2.找出三个数中的最小数 3.输出最小数

3 细化后的算法： 1.输入三个数，其值分别赋给三个变量a，b，c 2.比较a与b的值，如果a<b, 则min=a; 否则min=b。 3.比较c与min的值，如果c<min, 则min=c。 4.输出min的值 编程：根据算法，编写出计算机可执行的命令序列。

4 3.2 结构化算法的结构 按照结构化的观点，任何算法都可以用三种基本结构的组合来实现 顺序结构：语句按书写顺序顺次执行。
3.2 结构化算法的结构 按照结构化的观点，任何算法都可以用三种基本结构的组合来实现 顺序结构：语句按书写顺序顺次执行。 分支结构：根据条件成立与否有选择地执 行。 循环结构：根据条件的成立与否重复执行。

5 3.3 结构化程序算法描述 算法的描述方式 自然语言 流程图 N-S图 PAD图 伪代码

6 一、自然语言 例2：输入变量a和b，按由小到大顺序输出到屏幕 算法：1.输入变量a、b的值; 2.比较a与b，如果a<=b，则先输出a再输出b，否则先输出b再输出a; 3.算法结束。 优点：通俗易懂，简单明了 缺点：有歧义性，无法描述包含分支和循环的算法

7 例3：算术级数求和:sum=1+2+3+…+(n-1)+n
算法： 1.给定一个大于0的正整数n的值; 2.定义整型变量sum，设其初始值为0； 3.定义一个整型变量i，设其初始值为1; 4.如果i小于等于n，则转第5步，否则执行第8步； 5.将sum的值加上i的值后，重新赋值给sum; 6.将i的值加1，重新赋值给i; 7.执行第4步； 8.输出sum的值。

8 二、流程图 1.开始/结束框 2.处理框 3.连接符 4.输入输出框 5.判断框 6.流程线

9 顺序结构是一种简单的线性结构，根据流程线所示的方向，各矩形框按顺序执行。
1. 顺序结构 开始 结束 输入 输出 A B C 顺序结构是一种简单的线性结构，根据流程线所示的方向，各矩形框按顺序执行。

10 选择结构是对给定的条件进行判断，根据判断结果的真假而分别执行不同的处理框的内容。
2. 分支结构 选择结构是对给定的条件进行判断，根据判断结果的真假而分别执行不同的处理框的内容。 开始 B 输入 A 条件 结束 输出 不成立 成立 条件 结束 输出 开始 输入 A 不成立 成立

11 循环结构是在某个条件为真的情况下，重复执行某个框中的内容。循环结构有两种基本形态：while型循环和do_while型循环。
3. 循环结构 循环结构是在某个条件为真的情况下，重复执行某个框中的内容。循环结构有两种基本形态：while型循环和do_while型循环。 不成立 条件 输出 输入 语句 成立 While型循环 输出 输入 语句 条件 不成立 成立 Do-While型循环 循环控制条件 循环体

12 循环结构注意： 1、在循环体中，必须对条件要判断的值进行修改，使得经过有限次循环后，循环一定能结束。 2、while型循环中循环体可能一次都不执行，而do_while型循环则至少执行一次循体。 3、do_while型循环可以很方便地转化为while型循环，而while型循环不一定能转化为do_while型循环。

13 例1：从键盘输入三个数，找出其中最小的那个数。
start 输入a,b,c T F a<b min=a min=b F c<min min=c 输出min end

14 例3：算术级数求和:sum=1+2+3+…+(n-1)+n
start 输入n i=1,sum=0 F i<=n T sum=sum+i i=i+1 输出sum end 伪码

15 二、N—S 图（由I . Nassi和B . Shneiderman提出）
1. 顺序结构 A B 2. 分支结构 B F A T 条件 F A T 条件

16 例3：输入整数，并且累加，直到sum>=100为止，输出sum
3. 循环结构 当（条件）为真 A 当（条件）为真 A 例3：输入整数，并且累加，直到sum>=100为止，输出sum

17 三、PAD图（Problem Analysis Diagram）
C 1. 顺序结构 2. 分支结构 B A 条件 A 条件

18 3. 循环结构 While型 A WHILE（条件） Do-While型 A UNTIL（条件）

19 流程图、N-S图、PAD图比较： 1. 流程图 优点：简单直观 缺点：大且混乱 2. N-S图 优点：精简 缺点：不便修改 3. PAD图 优点：层次清晰，二维的算法描述

20 三、伪代码 伪代码是一种接近于程序语言的算法描述方法，它用一些特定的符号来表示算法结构，具有较好的可读性。常用的伪代码符号如下7种： 1.算法名称 伪代码算法有两种：过程和函数。区别：过程不需要返回数据，而函数需要返回数据。 如：Procedure Hanoi_Tower()、Function Fac(x)

21 2.指令序列 算法名之后就是伪代码的指令序列 Begin 指令序列； End 或者： { /}

22 3.输入/输出 输入：Input 如：Input x; 输出：Output 或者Return 如：Output x; 4.分支选择 (1)If<条件>Then { 指令； /} (2)If <条件>Then else { 指令；/}

23 5.赋值 用:=或<-表示，如x:=x+1；y<-x*x； 6.循环 (1)计数式循环：For 变量:=初值 To 终值 { 指令； /} (2)条件式循环：While (条件) do 7.算法结束 End后面加上算法名称，如 End Hanoi_Tower、End Fac

24 例1：从键盘输入三个数，找出其中最小的那个数。
Procedure Minimal() Begin Input a,b,c; If(a<b)Then min:=a; Else min:=b; If(c<min)Then min:=c; Output min; End Minimal

25 例3：算术级数求和:sum=1+2+3+…+(n-1)+n
Function Total(n) Begin i:=1; sum:=0; While(i<=n)do { sum:=sum+i; i:=i+1; /} Return sum; End Total

26 流程图与自然语言、伪码比较： 1. 流程图 优点：直观 缺点：不够灵活 2. 自然语言 优点：灵活自由 缺点：有歧义性 3. 伪码 优点：很容易转换成程序代码 缺点：有专门的符号体系，较难掌握

27 3.4 算法设计范例 例4：把从键盘输入的大写字母转换成小写字母输出，若为小写字母或其他字符，则不作任何转换直接输出。一直输入至按下Ctrl＋Z为止。 1.用自然语言描述算法: 从键盘输入一个字符赋给字符变量ch; 如果（ch!=EOF） 则:如果（ch>=‘A’ && ch<=‘Z’） 则：ch=ch+_32 否则：程序结束 转①

28 2.用流程图描述算法: start 输入ch ch!=EOF ch>=65&&ch<=90 ch=ch+32 输出sum end

29 3.用伪码描述算法: Procedure CapToLow() Begin Input ch; While(ch!=EOF)do { If(ch>=65 && ch<=90)Then ch:=ch+32; Output ch; /} End CapToLow

30 作业： 题3.1，题3.2