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

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

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

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

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

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

例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的值。

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

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

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

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

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

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

例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 伪码

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

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

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

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

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

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

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

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

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

例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

例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

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

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

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

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

作业： 题3.1，题3.2