1、第第3 3章章 简单算法设简单算法设计计 第3章 程序的简单算法制定本章主要内容本章主要内容1.结构化程序的算法设计2.结构化算法的性质及结构3.结构化算法的描述方法4.结构化算法流程图第3章 程序的简单算法制定算法：算法：解决问题的方法和要遵循的步骤。解决问题的方法和要遵循的步骤。算法描述了程序要执行的操作及操作的步骤顺序。算法描述了程序要执行的操作及操作的步骤顺序。程序的功能是通过算法来描述程序的功能是通过算法来描述的。的。C C语言程序是一种语言程序是一种结构化结构化的程序。的程序。结构化结构化程序：程序：问题可以分解成相互问题可以分解成相互独立的几个部分独立的几个部分。每个独立部分每个
2、独立部分可以通过简单的可以通过简单的语句或结构来实现语句或结构来实现。分问题解的过程就是算法设计的过程。分问题解的过程就是算法设计的过程。3.1 结构化程序的算法设计【例例3-13-1】要求从键盘输入要求从键盘输入3 3个数，找出其中最小的那个数，个数，找出其中最小的那个数，将其输出到屏幕。请给出解决这个问题的算法。将其输出到屏幕。请给出解决这个问题的算法。分析：分析：程序对于从键盘输入的程序对于从键盘输入的3 3个数必须用个数必须用3 3个变量来保存，个变量来保存，分别为分别为a a，b b，c c代表输入的代表输入的3 3个数，另外，还需要一个变量个数，另外，还需要一个变量minmin来保
3、存最小的那个数。来保存最小的那个数。1.1.先比较先比较a a和和b b的值，把数值小的放入的值，把数值小的放入minmin中；中；2.2.再将再将minmin与与c c比较，又把数值小的放入比较，又把数值小的放入minmin中。中。3.3.经过两次比较，经过两次比较，minmin中已存放的是中已存放的是a a，b b，c 3c 3个数中最小的个数中最小的数。把数。把minmin的值输出就是所需结果。的值输出就是所需结果。3.1 结构化程序的算法设计算法步骤：算法步骤：1 1输入输入3 3个数，其值分别赋给个数，其值分别赋给3 3个变量个变量a a，b b，c c；2 2把把a a与与b b中
4、较小的那个数放入变量中较小的那个数放入变量minmin中；中；3 3把把c c与与minmin中较小的那个数放入变量中较小的那个数放入变量minmin中；中；4 4输出最后结果输出最后结果minmin的值。的值。改进上面的算法描述，将第改进上面的算法描述，将第2 2步和第步和第3 3步的算法具体化。步的算法具体化。1 1输入三个数，其值分别赋给三个变量输入三个数，其值分别赋给三个变量a a，b b，c c；2 2比较比较a a与与b b的值，如果的值，如果abab，则，则min=amin=a；否则；否则min=bmin=b；3 3比较比较c c与与minmin的值，如果的值，如果cmincmi
5、n，则，则min=cmin=c；4 4输出最后结果输出最后结果minmin的值。的值。通过算法描述的步骤，可以很方便地用程序语言来实现。通过算法描述的步骤，可以很方便地用程序语言来实现。3.2 结构化算法的性质及结构3.2.1 3.2.1 结构化算法性质结构化算法性质1 1算法名称算法名称给算法命名，是为了方便算法的描述，在给算法命名，是为了方便算法的描述，在C C语言中，算法的语言中，算法的名字通常就是函数名。名字通常就是函数名。2 2输入输入算法应有输入的数据或初始条件。算法应有输入的数据或初始条件。3 3输出输出算法通常会有一个或多个输出，是对输入数据加工后的结算法通常会有一个或多个输出
6、，是对输入数据加工后的结果。果。4 4有效性有效性算法的每一步都是可执行的，可通过人工计算的。算法的每一步都是可执行的，可通过人工计算的。5 5正确性正确性算法的结果必须是正确的，可验证的。算法的结果必须是正确的，可验证的。6 6有限性有限性任何算法必须在执行有限条指令后结束。任何算法必须在执行有限条指令后结束。3.2 结构化算法的性质及结构3.2.2 3.2.2 结构化算法的结构结构化算法的结构在在C C语言算法的主要结构有如下语言算法的主要结构有如下3 3种。种。1 1顺序结构顺序结构顺序结构的特点：顺序结构的特点：程序在执行过程中是按语句的程序在执行过程中是按语句的先后顺序先后顺序来执行
7、的，每一来执行的，每一条语句都代表着一个功能，条语句都代表着一个功能，2 2分支结构分支结构分支结构的特点：分支结构的特点：程序在执行过程中，会根据条件的不同程序在执行过程中，会根据条件的不同有选择的执行有选择的执行不不同的功能。同的功能。3 3循环结构循环结构循环结构的特点：循环结构的特点：程序在执行过程中，在一定的时间段内或一定的条件下，程序在执行过程中，在一定的时间段内或一定的条件下，重复地执行重复地执行某个功能，直到时间已到或条件不再满足。某个功能，直到时间已到或条件不再满足。3.2 结构化算法的性质及结构程序设计要解决的两个主要问题：程序设计要解决的两个主要问题：（1 1）按什么顺序
8、或步骤来执行；）按什么顺序或步骤来执行；（2 2）用什么语句来实现。）用什么语句来实现。算法设计是核心问题。算法设计是核心问题。提示提示3.3 结构化算法的描述方法常用的描述方法有自然语言、流程图、伪代码等。3.3.1 自然语言 用类自然语言表示算法。如：汉语、英语或其他语言。特点：通俗易懂，简单明了。3.3 结构化算法的描述方法【例例3-23-2】从键盘输入两个变量的值从键盘输入两个变量的值a a、b b，请按输入值从小，请按输入值从小到大的顺序将这两个变量的值输出到屏幕。请写出这个问到大的顺序将这两个变量的值输出到屏幕。请写出这个问题的算法描述。题的算法描述。算法描述：算法描述：第第1 1
9、步：输入变量步：输入变量a a和和b b的值；的值；第第2 2步：比较步：比较a a和和b b的值；的值；如果如果a a大于等于大于等于b b，则先输出，则先输出a a，再输出，再输出b b；否则，先输出否则，先输出b b，再输出，再输出a a；第第3 3步：算法结束。步：算法结束。3.3 结构化算法的描述方法【例例3-33-3】几何级数求和：几何级数求和：sum=1+2+3+4+5sum=1+2+3+4+5+(+(n n1)+1)+n n。请写。请写出该问题的算法。出该问题的算法。算法描述：算法描述：第第1 1步：给定一个大于步：给定一个大于0 0的正整数的正整数n n的值；的值；第第2 2
10、步：定义一个整型变量步：定义一个整型变量i i，设其初始值，设其初始值1 1；第第3 3步：定义整型变量步：定义整型变量sumsum，其初始值设置为，其初始值设置为0 0；第第4 4步：如果步：如果i i小于等于小于等于n n，则转第，则转第5 5步，否则执行第步，否则执行第8 8步；步；第第5 5步：将步：将sumsum的值加上的值加上i i的值后，重新赋值给的值后，重新赋值给sumsum；第第6 6步：将步：将i i的值加的值加1 1，重新赋值给，重新赋值给i i；第第7 7步：执行第步：执行第4 4步；步；第第8 8步：输出步：输出sum sum 的值；的值；第第9 9步：算法结束。步：
11、算法结束。3.3 结构化算法的描述方法3.3.2 3.3.2 流程图流程图流程图是一种算法的形象表示。流程图是一种算法的形象表示。流程图是由流程图是由流程线流程线和和几何图形框几何图形框连接而成的。连接而成的。算法流程图的符号采用美国国家标准化协会算法流程图的符号采用美国国家标准化协会(ANSI)(ANSI)规定的一些常用符号：规定的一些常用符号：开始框开始框判断框判断框结束框结束框执行框执行框数据框数据框连接符连接符流程线流程线算法流程图的算法流程图的3 3种基本结构：种基本结构：顺序结构、分支结构、循环结构顺序结构、分支结构、循环结构1.1.顺序结构顺序结构顺序结构顺序结构是一种简单的线性
12、结构，根据流程线所示的方向，按顺序执行是一种简单的线性结构，根据流程线所示的方向，按顺序执行各矩形框的指令。各矩形框的指令。基本流程图：基本流程图：A B C 注：注：指令A、指令B、指令C可以是一条或多条指令。执行顺序：ABC。3.3 结构化算法的描述方法3.3 结构化算法的描述方法2.2.分支结构分支结构分支分支结构结构要对给定的条件进行判断，看是否满足给定的条件，根据条件要对给定的条件进行判断，看是否满足给定的条件，根据条件结果的真假而分别执行不同的执行框。结果的真假而分别执行不同的执行框。基本流程图有两种：基本流程图有两种：注：注：(1)虚线框表示可将分支结构看成一个矩形框。(2)指令
13、A、指令B可以是一条或多条指令，也可以是分支结构。条件 A B T F（a）条件 A T F（b）3.3 结构化算法的描述方法3.3.循环结构循环结构分支分支结构结构是在条件为真的情况下，重复执行某个执行框中的内容。是在条件为真的情况下，重复执行某个执行框中的内容。基本流程图有两种：基本流程图有两种：注：注：(1)虚线框表示可将循环结构看成一个矩形框。(2)指令A称为循环体，可以是一条或多条指令，也可以是其 他分支或循环结构。(3)do_while结构可以转化成while结构。(1)while 循环：(2)do_ while 循环：3.3 结构化算法的描述方法循环结构的特点：循环结构的特点：在
14、循环体指令在循环体指令A A中必须要有对条件的值进行修改的语句，中必须要有对条件的值进行修改的语句，使得经过有限次循环后，循环一定能结束。使得经过有限次循环后，循环一定能结束。whilewhile型循环中循环体可能一次都不执行，而型循环中循环体可能一次都不执行，而do_whiledo_while型循环则至少执行一次循环。型循环则至少执行一次循环。do_whiledo_while型循环可以转化成为型循环可以转化成为whilewhile型循环结构，但型循环结构，但whilewhile型循环不一定能转化为型循环不一定能转化为do_whiledo_while型循环。型循环。3.3 结构化算法的描述方法
15、关于结构化流程图的规则：关于结构化流程图的规则：1.1.可分别将顺序结构、分支结构、循环结构的基本流程图看成可分别将顺序结构、分支结构、循环结构的基本流程图看成是一个执行框。是一个执行框。2.2.任何两个按顺序的执行框可以合并为一个执行框。任何两个按顺序的执行框可以合并为一个执行框。反复运用规则反复运用规则1 1和规则和规则2 2可得到结构化流程图的最简形式可得到结构化流程图的最简形式：特别提示 A 开始 结束 3.3 结构化算法的描述方法【例3-4】分析下面的流程图，是否符合结构化算法标准。F F T T 开始 结束 F F T T While 循环结构 判断分支结构 开始 结束 运用规则3
16、.3 结构化算法的描述方法【例3-5】将例3-1的算法用流程图表示，分析其是否符合结 构化的标准。从键盘输入3个数，找出其中最小的那个数，将其输出到屏幕。运用规则3.3 结构化算法的描述方法【例3-6】将例3-2所描述的问题用算法流程图来表示。从键盘输入两个整型变量a，b的值，按输入值从小到大的顺序输出到屏幕。算法流程图为：3.3 结构化算法的描述方法【例3-7】将例3-3所描述的问题用算法流程图来表示。计算几何级数的和：sum=1+2+3+4+5+(n1)+n。算法流程图为：3.3 结构化算法的描述方法3.3.3 3.3.3 伪代码伪代码伪代码是伪代码是一种接近于程序语言的算法描述方法。一种
17、接近于程序语言的算法描述方法。特点：特点：采用有限的英文单词作为伪代码的符号系统，按照采用有限的英文单词作为伪代码的符号系统，按照特定的格式来表达算法，可读性好，方便将算法改写成特定的格式来表达算法，可读性好，方便将算法改写成计算机的程序源代码。计算机的程序源代码。伪代码的伪代码的7 7个主要部分：个主要部分：(1)(1)算法名称算法名称(2)(2)指令序列指令序列(3)(3)输出输出/输出输出(4)(4)分支选择分支选择(5)(5)赋值赋值(6)(6)循环循环(7)(7)算法结束算法结束3.3 结构化算法的描述方法1 1算法名称算法名称 两种表示算法的伪代码：两种表示算法的伪代码：过程（过程
18、（ProcedureProcedure）函数（函数（FunctionFunction）过程和函数的区别是：过程和函数的区别是：过程过程是执行一系列的操作，不需要返回操作的结果，是执行一系列的操作，不需要返回操作的结果，无返回数据无返回数据；函数函数是执行一系列的操作后，要将操作的结果返回，是执行一系列的操作后，要将操作的结果返回，有返回数据有返回数据。算法伪代码的书写规则：算法伪代码的书写规则：Procedure Procedure ()Function Function ()如：如：Procedure Procedure Hanoi_TowerHanoi_Tower()()表示名为表示名为H
19、anoi_TowerHanoi_Tower的一个过程。的一个过程。Function Function Fac(xFac(x)表示名为表示名为FacFac的一个函数。的一个函数。Function Function ProgProg(n)(n)表示名为表示名为ProgProg的一个函数。的一个函数。3.4 算法设计范例【例例3-113-11】把从键盘输入的大写字母转换把从键盘输入的大写字母转换成小写字母输出，若为小写字母或其他成小写字母输出，若为小写字母或其他字符，则不作任何转换直接输出。字符，则不作任何转换直接输出。分析：分析：用字符变量用字符变量chch来接收从键盘输入的来接收从键盘输入的字符
20、。大、小写字母的字符。大、小写字母的ASCIIASCII码值相差码值相差3232，大写字母，大写字母A A的值为的值为6565，而小写字母，而小写字母a a的值为的值为9797。流程图描述的算法：流程图描述的算法：3.4 算法设计范例【例例3-123-12】已知实数已知实数a a，b b，计算，计算u u的值：的值：u u=(=(r r+s s)2 2，并将计算结果输出到屏幕。，并将计算结果输出到屏幕。当当a a b b时，时，r r=a a2 2b b2 2，s=a/b s=a/b。当当a ab b时，时，r r=b b2 2a a2 2，s=a/b+4 s=a/b+4。分析：分析：用用a a，b b，r r，s s，u u分别表示浮点分别表示浮点型变量。型变量。a a和和b b代表输入的原始数据；代表输入的原始数据；r r和和s s为计算的中间变量；为计算的中间变量；u u为最后的计算结果。为最后的计算结果。流程图描述的算法：流程图描述的算法：思考：怎样简化算法。思考：怎样简化算法。本章练习 用流程图描述下面问题的算法：【题3.1】【题3.2】【题3.3】【题3.4】
