开通VIP，畅享免费电子书等14项超值服
首页
好书
留言交流
下载APP
联系客服
2013.12.08
第十三章算法初步
§13.1流程图
一、知识导学
1.流程图：是由一些图框和带箭头的流线组成的，其中图框表示各种操作的类型，图框中的文字和符号表示操作的内容，带箭头的流线表示操作的先后次序.
2．算法的三种基本的逻辑结构：顺序结构、条件结构、循环结构.
3．根据对条件的不同处理，循环结构又分为两种：
直到型(until型)循环：在执行了一次循环体之后，对控制循环条件进行判断，当条件不满足时执行循环体.满足则停止.如图13-1-3，先执行A框，再判断给定的条件是否为“假”，若为“假”，则再执行A，如此反复，直到为“真”为止.
当型（while型）循环：在每次执行循环体前对控制循环条件进行判断，当条件满足时执行循环体，不满足则停止.如图13-1-4，当给定的条件成立（“真”）时，反复执行A框操作，直到条件为“假”时才停止循环.
图13-1-1图13-1-2
二、疑难知识导析
1.“算法“没有一个精确化的定义，教科书只对它作了描述性说明，算法具有如下特点：
（1）有限性：一个算法的步骤是有限的，必须在有限操作之后停止，不能是无限的.
（2）确定性：算法的每一步骤和次序应当是确定的.
（3）有效性：算法的每一步骤都必须是有效的.
2.画流程图时必须注意以下几方面：
（1）使用标准的图形符号.
（2）流程图一般按从上到下、从左到右的方向画.
（3）除判断框外，大多数流程图符号只有一个进入点和一个退出点.判断框具有超过一个退出点的唯一符号.
（4）判断框分两大类，一类判断框“是”与“否”两分支的判断，而且有且仅有两个结果；另一类是多分支判断，有几种不同的结果.
（5）在图形符号内描述的语言要非常简练清楚.
3.算法三种逻辑结构的几点说明：
（1）顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的.在流程图中的体现就是用流程线自上而下地连接起来，按顺序执行算法步骤.（2）一个条件结构可以有多个判断框.
（3）循环结构要在某个条件下终止循环，这就需要条件结构来判断.在循环结构中都有一个计数变量和累加变量.计数变量用于记录循环次数，累加变量用语输出结果，计数变量和累加变量一般是同步执行的，累加一次，计数一次.
三、经典例题导讲
流程图为
图13-1-3
举一形象的例子：有蓝和黑两个墨水瓶，但现在却把蓝墨水装在了黑墨水瓶中，黑墨水错装在了蓝墨水瓶中，要求将其互换，请你设计算法解决这一问题.对于这种非数值性问题的算法设计问题，应当首先建立过程模型，根据过程设计步骤完成算法.我们不可将两个墨水瓶中的墨水直接交换，因为两个墨水瓶都装有墨水，不可能进行直接交换.正确的解法应为：
S1取一只空的墨水瓶，设其为白色；
S2将黑墨水瓶中的蓝墨水装入白瓶中；
S3将蓝墨水瓶中的黑墨水装入黑瓶中；
S4将白瓶中的蓝墨水装入蓝瓶中；
S5交换结束.
图13-1-4
解：流程图为
图13-1-5
点评：条件结构可含有多个判断框，判断框内的内容要简明、准确、清晰.此题也可将第一个判断框中的两个条件分别用两个判断框表示，两两比较也很清晰.若改为求100个数中的最大数或最小数的问题则选择此法较繁琐，可采用假设第一数最大（最小）将第一个数与后面的数依依比较，若后面的数较大（较小），则进行交换，最终第一个数即为最大（最小）值.
点评：求和时根据过程的类同性可用循环结构来实现，而不用顺序结构.
解：这是一个求和问题，可采用循环结构实现设计算法，但要注意奇数项为正号，偶数项为负号.
思路一：采用-1的奇偶次方（利用循环变量）来解决正负符号问题；
图13-1-6图13-1-7
思路二：采用选择结构分奇偶项求和；
图13-1-8
图13-1-9
[例5]任意给定一个大于1的整数n，试设计一个程序或步骤对n是否为质数做出判断.
解：算法为：
S2依次从2～n-1检验是不是的因数，即整除n的数，若有这样的数，则n不是质数；若没有这样的数，则n是质数.
点评：要验证是否为质数首先必须对质数的本质含义作深入分析：
（1）质数是只能被1和自身整除的大于1的整数.
（2）要判断一个大于1的整数n是否为质数，只要根据定义，用比这个整数小的数去除n.如果它只能被1和本身整除，而不能被其它整数整除，则这个数便是质数.
图13-1-10
解：设所求近似根与精确解的差的绝对值不超过0.005,算法:
点评：二分法求方程近似解的算法是一个重要的算法案例，将在第三节中详细阐述.
四、典型习题导练
2.下面流程图中的错误是（）
图13-1-11
C．S的计算不对D．判断条件不成立
的流程图中，判断框中应填入的内容是
5.3个正实数，设计一个算法，判断分别以这3个数为三边边长的三角形是否存在，画
出这个算法的流程图.
6.一队士兵来到一条有鳄鱼的深河的左岸.只有一条小船和两个小孩，这条船只能承载两个小孩或一个士兵.试设计一个算法，将这队士兵渡到对岸，并将这个算法用流程图表示.