程序设计方法学第2-补章2009.ppt

程序设计方法学 贵州师大数学与计算机科学学院 贵州师大多媒体CAI所 张仁津 2009年 第二讲 程序设计方法学基础 1、计算机语言作用及工作原理 2、算法及描述算法的方法 3、程序设计语言结构 4、常用程序设计方法 5、结构化程序设计与GOTO 6、程序好坏的标准与技巧 7、结构化程序设计与模块 程序设计网站 中国软件： UML软件工程组织： 第三讲 复习 2．1 结构化定理 2．1．1 结构化程序 一、基本概念 结构化程序设计方法的研究包括了四个紧密相关的课题。 课题1：程序设计方法。指在用计算机程序解决问题过程中比较有效的一般性的方法，如抽象的层次观念，逐步求精，自顶向下等。 课题2：程序标记法。任何一个语言都是使用符号标记的，它的意思及其阐述形式对理解和维护程序都是十分重要的。一个凌乱的程序设计语言显然有碍设计思路的清晰。结构化程序设计方法学帮助我们简化程序设计过程，确保适合的控制结构和清晰的数据结构。 课题3：程序正确性。程序的正确性是指一个程序和它预期的功能之间是否一致，结构化程序设计方法试图通过证明的方法来达到这个目的，因此数学归纳法、形式逻辑、公理化证明等数学工具都能够应用到结构化程序的证明当中。 课题4：程序验证。程序验证是将程序正确性证明的理论应用到实际环境中去的过程。一个程序的正确不只是语法正确，同时也要语义正确，还与特定的运行环境相关。即通过程序正确性证明理论的应用，确定当输入之前满足某些前提的程序，在执行之后是否能达到我们预计的结果。 算法计算机解决问题的核心 算法，是对特定问题的求解步骤。描述算法的方式一般有3种： 自然语言叙述， 流程图， 计算机语言（或指令）。 理论上 任何一个程序都可以用流程图描述，换句话说，我们可以同一种图形语言来写程序，这样的程序称为流程图程序。它是一种程序比较直观的表现形式。 一个流程图程序由以下图形符号组成。 1．处理单元（Process Box） 2．判断单元（Decision Box） 3．连接单元（Junction Box） 4．流线（Flow Lines） 5．开始单元（Start Box） 6．结束单元 7．输入、输出单元（Input／Output Box） 正规程序 一个流程图程序如果满足以下两个条件，称为正规程序： （1）只有一个入口线和一个出口线； （2）对每一个结点，都有一条从入口线到出口线的通路。 正规程序只有一个入口线和一个出口线，因此正规程序可以概括为一个函数结点。 一个正规程序的某些部分仍然是正规程序，这些部分称为正规子程序。 一个正规程序，如果不包含多于一个结点的正规子程序，称为基本程序。即基本程序是正规程序的一种，且其正规子程序不多于一个结点。 复合程序 把从7种基本程序挑出的这部分叫做基本程序的基集合。反复应用基集合构造出来的程序称为基集合的复合程序。 结构化程序 早在1966年Bohm等人就证明了任何一个程序只要具备三种基本程序：顺序、if－then－else和while－do就足以表示出所有形式的程序。 如果一个基本程序的函数结点用另外一个基本程序替换，则产生一个新的正规程序，称为复合程序。 由基本程序的定义，我们可以引出结构化程序的定义：由基本程序的一个固定的基集合构造出来的复合程序称为结构化程序。 结构程序设计概念cont’d 早在1966年， Bohm和Jacopini就证明了程序中只要有三种基本形式（顺序、选取和重复）控制结构就足以表示出其它各式各样形式的结构。那就是结构程序有顺序、选取、重复三种基本控制结构和程序块只具有“一个入口和一个出口”的原则。 M．H．Williams把非结构归纳为五种基本的成分，即： （1）异常的选择通路； （2）循环多出口点； （3）循环多入口点； （4）重叠的循环； （5）并行的循环。 这五种非结构是不能分解到基本程序的。可以证明，如果一个流程图是非结构化的，则它至少包含这五种非结构成分中的一种。 结构程序设计概念cont’d 1974年，D.Gries教授将已有的对结构程序设计的不同解释归纳为13种。其中，比较有代表性的是： （1）结构程序设计是避免用GOTO 语句的一种程序设计， （2）结构程序设计是自顶向下的程序设计。 （3）结构程序设计是—种组织和编制程序的方法，利用它编制的程序是容易理解和容易修改的。 （4）程序结构化的一个主要功能是使得正确性的证明容易实现。 （5）结构程序设计允许在设计过程中的每一步验证其正确性，即自动导致自我说明与自我捍卫的程序风格。 （6）结构程序设计讨论了如何将任何大规模的和复杂的流程图转换成一种标准的形式，使得它们能够用几种标