签到

05月06日
尚未签到

共有回帖数 0 个

    幸福没有捷径

    等级：
    什么是程序？程序= 数据结构+ 算法。  
    对于面向对象程序设计，强调的是数据结构，而对于面向过程的程序设计语言如C、P a s c a l、F O RT R A N等语言，主要关注的是算法。掌握算法，也是为面向对象程序设计打下一个扎实的基础。那么，什么是算法呢？

    人们使用计算机，就是要利用计算机处理各种不同的问题，而要做到这一点，人们就必须事先对各类问题进行分析，确定解决问题的具体方法和步骤，再编制好一组让计算机执行的指令即程序，交给计算机，让计算机按人们指定的步骤有效地工作。这些具体的方法和步骤，其实就是解决一个问题的算法。根据算法，依据某种规则编写计算机执行的命令序列，就是编制程序，而书写时所应遵守的规则，即为某种语言的语法。

    由此可见，程序设计的关键之一，是解题的方法与步骤，是算法。学习高级语言的重点，就是掌握分析问题、解决问题的方法，就是锻炼分析、分解，最终归纳整理出算法的能力。与之相对应，具体语言，如C语言的语法是工具，是算法的一个具体实现。所以在高级语言的学习中，一方面应熟练掌握该语言的语法，因为它是算法实现的基础，另一方面必须认识到算法的重要性，加强思维训练，以写出高质量的程序。

    下面通过例子来介绍如何设计一个算法：

    [例1-4] 输入三个数，然后输出其中最大的数。

    首先，得先有个地方装这三个数，我们定义三个变量A、B、C，将三个数依次输入到Ａ、B、C中，另外，再准备一个M A X装最大数。由于计算机一次只能比较两个数，我们首先把A与B比，大的数放入M A X中，再把M A X 与C比，又把大的数放入M A X中。最后，把M A X输出，此时M A X中装的就是Ａ、Ｂ、C三数中最大的一个数。算法可以表

    示如下：

    1) 输入A、B、C。

    2) A与B中大的一个放入M A X中。

    3) 把C与M A X中大的一个放入M A X中。

    4) 输出M A X，M A X即为最大数。

    其中的2 )、3 )两步仍不明确，无法直接转化为程序语句，可以继续细化：

    2) 把A与B中大的一个放入M A X中，若A  B，则MAX ←A；否则MAX ←B。

    3) 把C与M A X中大的一个放入M A X中，若C  M A X，则M A X←C。

    于是算法最后可以写成：

    1) 输入A，B，C。

    2) 若A  B，则MAX ←A；

    否则M A X←B。

    3) 若C  M A X，则M A X←C。

    4) 输出M A X，M A X即为最大数。
    这样的算法已经可以很方便地转化为相应的程序语句了。

    [例1-5] 猴子吃桃问题：有一堆桃子不知数目，猴子第一天吃掉一半，觉得不过瘾，又多吃了一只，第二天照此办理，吃掉剩下桃子的一半另加一个，天天如此，到第十天早上，猴子发现只剩一只桃子了，问这堆桃子原来有多少个？

    此题粗看起来有些无从着手的感觉，那么怎样开始呢？假设第一天开始时有a1只桃子，第二天有a2只，. . .，第9天有a9只，第1 0天是a1 0只，在a1, a2, . . .，a1 0中，只有a1 0= 1是知道的，现要求a1，而我们可以看出，a1, a2, . .，a1 0之间存在一个简单的关系：

    a9= 2 * ( a1 0+ 1 )  

    a8= 2 * ( a9+ 1 )  

    ┇  

    a1= 2 * ( a2+ 1 )  

    也就是：ai= 2 * ( ai + 1+1) i=9,8,7,6,...,1  

    这就是此题的数学模型。

    再考察上面从a9，a8直至a1的计算过程，这其实是一个递推过程，这种递推的方法在计算机解题中经常用到。另一方面，这九步运算从形式上完全一样，不同的只是ai的下标而已。由此，我们引入循环的处理方法，并统一用a0表示前一天的桃子数，a1表示后一天的桃子数，将算法改写如下：

    1) a1=1; ｛第1 0天的桃子数，a1的初值｝

    i = 9。｛计数器初值为9｝

    2) a0= 2 * ( a1+ 1 )。｛计算当天的桃子数｝

    3) a1= a0。｛将当天的桃子数作为下一次计算的初值｝

    4) i=i-1。

    5) 若i  = 1，转2 )。

    6) 输出a0的值。

    其中2 )～5 )步为循环。
    这就是一个从具体到抽象的过程，具体方法是：

    1) 弄清如果由人来做，应该采取哪些步骤。

    2) 对这些步骤进行归纳整理，抽象出数学模型。

    3) 对其中的重复步骤，通过使用相同变量等方式求得形式的统一，然后简练地用循环解决。

    算法的描述方法有自然语言描述、伪代码、流程图、N - S图、PA D 图等。

    1.4.1 流程图与算法的结构化描述

    1. 流程图

    流程图是一种传统的算法表示法，它利用几何图形的框来代表各种不同性质的操作，用流程线来指示算法的执行方向。由于它简单直观，所以应用广泛，特别是在早期语言阶段，只有通过流程图才能简明地表述算法，流程图成为程序员们交流的重要手段，直到结构化的程序设计语言出现，对流程图的依赖才有所降低。

    下面介绍常见的流程图符号及流程图的例子。
    本章例1 - 1的算法的流程图如图1 - 2所示。本章例1 - 2的算法的流程图如图1 - 3所示。在流程图中，判断框左边的流程线表示判断条件为真时的流程，右边的流程线表示条件为假时的流程，有时就在其左、右流程线的上方分别标注“真”、“假”或“T”、“F”或“Y”、“N”��


    另外还规定，流程线是从下往上或从右向左时，必须带箭头，除此以外，都不画箭头，流程线的走向总是从上向下或从左向右。

    2. 算法的结构化描述

    早期的非结构化语言中都有g o t o语句，它允许程序从一个地方直接跳转到另一个地方去。执行这样做的好处是程序设计十分方便灵活，减少了人工复杂度，但其缺点也是十分突出的，一大堆跳转语句使得程序的流程十分复杂紊乱，难以看懂也难以验证程序的正确性，如果有错，排起错来更是十分困难。这种转来转去的流程图所表达的混乱与复杂，正是软件危机中程序人员处境的一个生动写照。而结构化程序设计，就是要把这团乱麻理清。

    经过研究，人们发现，任何复杂的算法，都可以由顺序结构、选择（分支）结构和循环结构这三种基本结构组成，因此，我们构造一个算法的时候，也仅以这三种基本结构作为“建筑单元”，遵守三种基本结构的规范，基本结构之间可以并列、可以相互包含，但不允许交叉，不允许从一个结构直接转到另一个结构的内部去。正因为整个算法都是由三种基本结构组成的，就像用模块构建的一样，所以结构清晰，易于正确性验证，易于纠错，这种方法，就是结构化方法。遵循这种方法的程序设计，就是结构化程序设计。

    相应地，只要规定好三种基本结构的流程图的画法，就可以画出任何算法的流程图。

    (1) 顺序结构

    顺序结构是简单的线性结构，各框按顺序执行。其流程图的基本形态如图1 - 4所示，语句的执行顺序为：A→B→C。

    (2) 选择（分支）结构

    这种结构是对某个给定条件进行判断，条件为真或假时分别执行不同的框的内容。其基本形状有两种，如图1-5 a）、b）所示。图1-5 a）的执行序列为：当条件为真时执行A，否则执行B；图1 - 5 b）的执行序列为：当条件为真时执行A，否则什么也不做��




    执行序列为：首先执行A，再判断条件，条件为真时，一直循环执行A，一旦条件为假，结束循环，执行循环紧后的下一条语句。

    在图1 - 6、图1 - 7中，A被称为循环体，条件被称为循环控制条件。要注意的是：

    1) 在循环体中，必然对条件要判断的值进行修改，使得经过有限次循环后，循环一定能结束，如图1 - 3中的i = i - 1。2) 当型循环中循环体可能一次都不执行，而直到型循环则至少执行一次循环体。3) 直到型循环可以很方便地转化为当型循环，而当型循环不一定能转化为直到型循环。

    例如，图1 - 7可以转化为图1 - 8。

    2 用N-S图描述算法

    N - S图是另一种算法表示法，是由美国人I . N a s s i和B . S h n e i d e r m a n共同提出的，其根据是：既然任何算法都是由前面介绍的三种结构组成，所以各基本结构之间的流程线就是多余的，因此，N - S图也是算法的一种结构化描述方法。

    N - S图中，一个算法就是一个大矩形框，框内又包含若干基本的框，三种基本结构的N - S 图描述如下所示：

    1. 顺序结构如图1 - 9所示，执行顺序先A后B。  
    2. 选择结构  
    对应于图1 - 5的N - S图为图1 - 1 0。图1-10 a)条件为真时执行A，条件为假时执行B。图1 - 1 0 b )条件为真时执行A，为假时什么都不做��






    3 用PAD图描述算法
    PA D（Problem Analysis Diagram），是近年来在软件开发中被广泛使用的一种算法的图形表示法，与前述的流程图、N - S图相比，流程图、N - S图都是自上而下的顺序描述，而PA D图除了自上而下以外，还有自左向右的展开，所以，如果说流程图、N - S图是一维的算法描述的话，则PA D图就是二维的，它能展现算法的层次结构，更直观易懂。
    下面是PA D图的几种基本形态：
    1. 顺序结构：
    如图1 - 1 5所示。
    2. 选择结构
    (1) 单分支选择，条件为真执行A，如图1-16 a）。
    (2) 两分支选择，如图1-16 b)，条件为真执行A，为假执行B。
    (3) 多分支选择，如图1-16 c)，当I = I1时执行A，Ｉ= I2时执行B，I = I3时执行C，I = I4时执行Ｄ��

    楼主 2016-05-19 11:23 回复

共有回帖数 0 个
  • 回 帖
  • 表情 图片 视频
  • 发表

登录直线网账号

Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号 意见反馈 | 关于直线 | 版权声明 | 会员须知