第3章程序结构



世界著名计算机科学家沃思提出： 程序=算法+数据结构。算法是程序设计的灵魂。
任何一个程序(或算法)都可以表示成三种基本结构： 顺序结构、选择结构(分支结构)和循环结构。
本章将介绍算法的基本知识和程序的三大基本结构。











第17课算法的概念






 
理解算法的含义。

算法就是解决一个实际问题的方案和具体步骤。生活中的算法比比皆是，不胜枚举。如去医院看病，通常分为三步： 一挂号、二排队、三看病。


 【例17.1】写出“求18和30的最大公因数”的算法。
算法一： 枚举法
第一步，分别求出18和30的所有因数，18的因数有1、2、3、6、9、18； 30的因数有1、2、3、5、6、10、15、30。
第二步，求出18和30的公因数有1、2、3、6。
第三步，得出18和30的最大公因数是6。

算法二： 分解质因数法
第一步，把18和30分解质因数，即18=2×3×3，30=2×3×5。
第二步，18和30的质因数都含有2和3。
第三步，得出18和30的最大公因数是2×3=6。

算法三： 短除法

第一步，用两个数的公因数2除。
第二步，用两个数的公因数3除。
第三步，除到两个数的公因数只有1为止。
第四步，把所有除数连乘起来，得出18和30的最大公因数是2×3=6。

算法四： 辗转相除法
辗转相除法就是用较大的数除以较小的数，再用除数除以出现的第一个余数。接着再用第一个余数除以出现的第二个余数……直到余数是0为止。最后的除数就是两个数的最大公因数。具体步骤如下。 
第一步，用30除以18，商1余12。
第二步，用18除以12，商1余6。
第三步，用12除以6，商2余0。
第四步，除数6就是18和30的最大公因数。
 【算法分析】
由例17.1可知，对于具体的某个问题，它的算法并不唯一，如果多种算法的效率相当，选择其中一种算法解决问题即可。通常情况下，算法有好有坏，所以在设计算法时，尽量设计并选取效率较高的算法解决问题。


 实践园
请尝试写出“求1+2+3+4+5+…+100的和”的算法。





第18课算法的特征






 
理解算法的四大特征。

算法的基本特征如下。
(1) 可行性： 算法中的每一条指令都能够被精确地执行。
(2) 确定性： 算法中的每一条指令都必须有明确的含义，无二义性。
(3) 有限性： 一个算法必须在执行有限步之后结束，且每一步都在有限的时间内完成。
(4) 输入、输出： 一个算法有0个或多个输入，有1个或多个输出。也就是说，一个算法可以没有输入，但必须要有输出。


 【例18.1】给定一个正数，求以这个数为半径的圆的面积。
【参考程序】


【运行结果】

  【程序分析】
该程序的算法分为如下三步。
（1） 输入一个正数r>0。
（2） 计算圆的面积s=πr2。
（3） 输出圆的面积。


 实践园
算法有哪些基本特征？





第19课算法的描述






 
学会使用流程图描述算法。

描述一个算法的方法很多，有自然语言、流程图等方式。由于人类的自然语言容易产生歧义，因此，在程序设计中，一般不建议使用。对于初学者而言，建议使用流程图的方式描述算法。
使用一组特定的图形符号加上简明扼要的文字说明来描述算法的图，称为流程图，即用图的形式描述算法。在流程图中，用带有箭头的流程线表示执行的先后顺序，用不同形状的符号表示具体含义。流程图的符号及其含义如表19.1所示。


表19.1




符号
名称
含义



开始/结束
表示流程的开始或结束

输入框/输出框
表示数据的输入或输出

具体语句
表示流程中单独的一个步骤

条件判断框
表示流程中的具体条件判断

流程线
表示流程执行的流向




 【例19.1】已知圆的半径为一个正数r(r>0)，求圆的面积s。画出它的流程图。
【流程图】
求圆的面积的流程图如图19.1所示。



图19.1


【例题分析】
该例题源自于例18.1，在开始编写程序前，应事先设计算法(画出流程图)，再开始编写程序。


 实践园
请根据流程图19.2编写程序。


图19.2












第20课程序基本结构






 
熟知程序的三大基本结构。

程序(或算法)一般可以表示为三种基本结构： 顺序结构、选择结构(也称分支结构)、循环结构。
1. 顺序结构
顺序结构是最简单的程序结构，表示程序自上而下，不遗漏、不重复地顺序执行每一条语句，直到程序结束。顺序结构的流程图如图20.1所示。
2. 选择结构
选择结构，也称分支结构，用于判断给定的条件，根据判断结果的成立与否，选择不同的分支路径，有单分支结构、双分支结构和多分支结构，其流程图分别如图20.2~图20.4所示。




图20.1





图20.2




图20.3





图20.4



3. 循环结构
循环结构又称重复结构，是指在程序中需要反复执行某一条或某一组语句的一种程序结构，其中“某一条或某一组语句”称为循环体。循环结构一般有两种类型： 当型循环和直到型循环，其流程图分别如图20.5和图20.6所示。





图20.5




图20.6


本节课介绍了程序的基本结构，在后面的学习中将依次详细介绍三种结构的使用和经典案例。

 实践园
程序的三大基本结构分别是什么？




第4章顺序结构



顺序结构是最简单的程序结构，表示程序自上而下，不遗漏、不重复地顺序执行每一条语句，直到程序结束。
C++语言在默认的情况下采取的是顺序结构。因此，前3章中学习的所有案例程序均属于顺序结构，本章将继续学习顺序结构的一些经典例题。










第21课数 位 之 和






 
掌握分离整数的各个数位的方法。


 【例21.1】输入一个三位数x，求出数x百位、十位、个位上的三个数之和。
【参考程序】


【运行结果】

  【程序分析】
程序中的第8~10行分别求出。这个三位数的百位上的数、十位上的数、个位上的数。


 实践园
反向输出一个三位数，即将一个三位数反向输出。
注： 题目出自http://noi.openjudge.cn中1.3编程基础之算术表达式与顺序执行/13。
输入： 一个三位数n。
输出： 反向输出n。
【样例输入】

100

【样例输出】

001