计算机等级考试二级C语言常用的算法（2）

会计考友

　　经过研究，人们发现，任何复杂的算法，都可以由顺序结构、选择（分支）结构和循环结构这三种基本结构组成，因此，我们构造一个算法的时候，也仅以这三种基本结构作为“建筑单元”，遵守三种基本结构的规范，基本结构之间可以并列、可以相互包含，但不允许交叉，不允许从一个结构直接转到另一个结构的内部去。正因为整个算法都是由三种基本结构组成的，就像用模块构建的一样，所以结构清晰，易于正确性验证，易于纠错，这种方法，就是结构化方法。遵循这种方法的程序设计，就是结构化程序设计。
　　相应地，只要规定好三种基本结构的流程图的画法，就可以画出任何算法的流程图。
　　(1) 顺序结构
1 |9 P# t% L  u　　顺序结构是简单的线性结构，各框按顺序执行。其流程图的基本形态如图1 - 4所示，语句的执行顺序为：A→B→C。
　　(2) 选择（分支）结构
, C5 K. z. b- y　　这种结构是对某个给定条件进行判断，条件为真或假时分别执行不同的框的内容。其基本形状有两种，如图1-5 a）、b）所示。图1-5 a）的执行序列为：当条件为真时执行A，否则执行B；图1 - 5 b）的执行序列为：当条件为真时执行A，否则什么也不做。
! u8 Q. g  c$ n* X# Z6 ?- m! ~: ~　　1 、(3) 循环结构循环结构有两种基本形态：w h i l e型循环和d o - w h i l e型循环。
7 y: L1 o5 ~- o　　2、a. while 型循环如图1 - 6所示。其执行序列为：当条件为真时，反复执行A，一旦条件为假，跳出循环，执行循环紧后的
　　语句。
! _& S& H# W( A4 f5 N　　b. do-while型循环如图1 - 7所示。
2 t. E/ Y6 v- G6 T# U% K- e　　执行序列为：首先执行A，再判断条件，条件为真时，一直循环执行A，一旦条件为假，结束循环，执行循环紧后的下一条语句。
　　在图1 - 6、图1 - 7中，A被称为循环体，条件被称为循环控制条件。要注意的是：
　　1) 在循环体中，必然对条件要判断的值进行修改，使得经过有限次循环后，循环一定能结束，如图1 - 3中的i = i - 1。2) 当型循环中循环体可能一次都不执行，而直到型循环则至少执行一次循环体。3) 直到型循环可以很方便地转化为当型循环，而当型循环不一定能转化为直到型循环。
　　例如，图1 - 7可以转化为图1 - 8。
5 l3 V- B# I/ O! t! Q, y　　2 用N-S图描述算法
; K6 F  x/ V0 V　　N - S图是另一种算法表示法，是由美国人I . N a s s i和B . S h n e i d e r m a n共同提出的，其根据是：既然任何算法都是由前面介绍的三种结构组成，所以各基本结构之间的流程线就是多余的，因此，N - S图也是算法的一种结构化描述方法。
: }6 s( n& {) x1 z8 y　　N - S图中，一个算法就是一个大矩形框，框内又包含若干基本的框，三种基本结构的N - S 图描述如下所示：
- B: e9 v& H+ J. M# Q3 ~' W% T" {　　1. 顺序结构如图1 - 9所示，执行顺序先A后B。
# y0 O, o* }5 z9 I% H! ^4 R　　2. 选择结构
　　对应于图1 - 5的N - S图为图1 - 1 0。图1-10 a)条件为真时执行A，条件为假时执行B。图1 - 1 0 b )条件为真时执行A，为假时什么都不做。
! y$ ^" e4 M7 e, ~; a" S2 o* S　　3. 循环结构
　　1) while型循环的N - S图如图1 - 11所示，条件为真时一直循环执行循环体A，直到条件为假时才跳出循环。
　　2) do-while型循环的N - S图如图1 - 1 2，一直循环执行循环体A，直到条件为假时才跳出循环。
; r6 c% T& Z( |* c  Q　　本章例1 - 1的N - S图如图1 - 1 3，例1 - 2的N - S图如图1 - 1 4。应该说，N - S图比流程图更直观易懂，而且相对简练一些。
　　3 用PAD图描述算法
　　PA D（Problem Analysis Diagram），是近年来在软件开发中被广泛使用的一种算法的图形表示法，与前述的流程图、N - S图相比，流程图、N - S图都是自上而下的顺序描述，而PA D图除了自上而下以外，还有自左向右的展开，所以，如果说流程图、N - S图是一维的算法描述的话，则PA D图就是二维的，它能展现算法的层次结构，更直观易懂。
" [! x/ [( r4 D# a* E　　下面是PA D图的几种基本形态：
/ k7 P$ X3 R: ?2 i0 J　　1. 顺序结构：
　　如图1 - 1 5所示。
　　2. 选择结构
! I( p" |) Z( Z4 S! A　　(1) 单分支选择，条件为真执行A，如图1-16 a）。
　　(2) 两分支选择，如图1-16 b)，条件为真执行A，为假执行B。
, M3 W3 y, j- d8 C　　(3) 多分支选择，如图1-16 c)，当I = I1时执行A，Ｉ= I2时执行B，I = I3时执行C，I = I4时执行Ｄ。
　　3. 循环结构
　　如图1 - 1 7所示。图1-17 a)为w h i l e型循环，图1-17 b)为d o - w h i l e型循环。
& f, D1 N' s& F( N3 Q8 L6 ?) E　　本章例1 . 1的PA D图如图1 - 1 8，例1 - 2的PA D图如图1 - 1 9。