第3章 银行常用程序设计语言顾浩 胡乃静 董建寅等编著2006.3.31主要内容 3.1 结构化程序设计基本原理 程序设计基本要素 算法设计初步 数据结构初步 程序设计方法初步 3.2 银行常用程序设计语言 程序设计方法初步 C语言概述 面向对象程序语言概述 Date2序算法是一个很古老的数学概念,最基本的算法就 是加、减、乘、除。 计算机程序设计=算法+数据结构+程序设计方法+计算机语言 其中的核心是算法。 程序是算法的具体表现形式之一 ; 程序编码是算法设计的最终表现形式, 而瑞士 计算机科学家Niklaus Wirth是提出数据结构+算法=程序 Algorithms +Data Structure=Programming 的第一人。 程序设计设计的实质是:确定数据的结构, 再加 上一个好算法。尼克劳斯.沃思 (Niklaus Wirth) PASCAL之父及 结构化程序设计首创者 1984年图灵奖荣获者Date3程序、算法和进程 算法是一组明确的、可执行的步骤的有序集合。是指令的有 限序列, 其中每条指令表示一个或多个操作。 如算法：F=（9/5）C+32 算法的含义与程序十分相似，但又有区别： 一个程序不一定满足有穷性, 如OS只要系统不遭破坏, 它永远 不会停止工作, OS不是一个算法; 程序中的指令必须是计算机可执行的, 而算法中的指令无此 限制; 算法代表了对问题的解, 而程序是算法在计算机上特定的实 现, 程序是一个算法的表达； 一个算法若用程序设计语言来表达, 它就是一个程序。 Date4程序、算法和进程 算法与数据结构相辅相成： 解决某一特定类型的问题的算法可选定不同的数据 结构, 而选择恰当与否将直接影响算法的效率;反之, 一种数据结构的优劣由各种算法的执行来体现。 进程是执行一个算法的活动。Date5结构化程序设计 (structured programmingSP） 概念：结构化程序设计(SP)是由E.Dijkstra(戴文斯特拉)于上 世纪70年代提出,它主张用顺序、选择和重复三种基本控制结 构来嵌套连接成具有复杂层次的“结构化程序”，每种基本结构只有一个出口和一个入口，并完成单一操作。 基本思想：支持自顶向下，逐步求精的设计思想。 优点：清晰（最大优点）、生产率高、具有固定风格、易维 护并可重新设计。 对于大多数程序语言来讲，只要保持固定的风格和使用预处 理技术，便可执行结构化程序。Date6关于SP结构化程序设计方法(SP)可归纳为三点： 1、由顶向下(Top Down)逐步精细的程序设计方法。 2、使用三种基本控制结构(顺序、选择、循环)来 构造单入口单出口的程序。 3、采用主程序员组的开发人员的组织方式。 5个子系统SS1S2S3S4S5S4.1S4.2S4.3S5.1S5.2S5.3S5.4 Date73.1 结构化程序设计基本原理3.1.1 程序设计基本要素 1.解题的基本模式 人解题的基本模式计算机解题的基本模式 以人为主导, 计算机为主体 计算机只部分替代人脑的功能Date82.问题分析 问题分析的诸环节 精确描述问题:力求考虑周密,分析详尽,描述精确。 识别数据输入:识别哪些数据需从外部提供(输入),如何提供. 判定信息输出:从计算机输出必要的信息,如何传送。 正确设置变量:用于输入数据、处理、输出等。数据输入（原始数据）数据处理（中间结果）信息输出（最终结果）计算机内存单元以变量形式提供描述、处理和存储如:求解ax2+bx+c=0的实根, 要用系数a, b, c和x1, x2变量Date9 建立数学模型:对给定问题抽象出数学描述形式。是问题分 析的核心。数值型问题易建立数学模型(如F=（9/5）C+32) ,而 非数值型问题则较难。 数学解析表达式仅仅是数学模型的主要形式之一，而切不可 误以为“数学模型就是数学解析表达式”。 决定处理方式:决定用人工还是计算机处理。 采用计算机处理方式的判定条件如下： 当人工处理方式所需时间和费用比计算机处理方式代价高时； 当解决所给定问题的数值计算或数据处理工作量非常大，难于用人工 处理方式来进行时； 当同一性质的给定问题重复出现率高，要求多次作类似处理，而且每 次解决有关问题的处理过程基本上大向小异； 当要求解决所给问题的响应速度快、信息可靠性好、数据精度高、自 动化程度高时。 选择计算方法:精心选择最佳的计算方法. 结论:问题分析事关重大, 必须高度重视.Date10例3-11 求一元五次方程x5+7x-60的实根（绝对误差精确到0.000001）的计算方法，可 有如下两种迭代法，但其结果却截然不同。 先看计算方法1：x2= 其迭代计算过程及结果如下： 迭代次数 x1 x2 绝对误差 |x1-x2| 1 0.000000 1.430970 1.430970 2 1.430970 - 1.320610 2.751580 10 1.742900 - 1.440400 3.183300 11 - 1.440400 1.742900 3.183300 显然，计算方法1无论迭代计算多少次，永远不可能求得合乎要求的原方程的实根。 再看计算方法2：x2=6(x14+7)，其迭代计算过程及结果如下： 迭代次数 x1 x2 绝对误差 |x1-x2| 1 0.000000 0.857143 0.857143 2 0.857143 0.795780 0.061363 3 0.795780 0.810699 0.014919 9 0.807955 0.807957 0.000002 10 0.807957 0.807957 0.000000结论:结果发散算法失败结论:结果收敛看法成功Date113.1.2 算法设计初步 继问题分析阶段之后，就进入应用计算机解决问题 的关键性阶段算法设计（algorithm design），即 设计算法的全过程。算法是计算机程序设计的核心 ，是计算机科学中最基本的重要概念之一。 Date123.1.2 算法设计初步1.系统与算法 可控系统与非控系统 可控系统:与人类关系密切相关. 即系统运行全过程中施 控子系统与受控子系统彼此响应、协同工作的行为方式 。其根本模式可抽象为系统算法(system a1gorithm)，简 称算法 非控系统:如地震,海啸,台风等. 当且仅当系统目标、操作执行者、操作对象、操作方式 、控制方式都相同的算法，才是相同的算法。 算法公式五大要素：算法=系统目标+操作执行者+操作对 象+操作方式+控制方式 Date13算法、程序和进程 算法的定义: 算法是一组明确的, 可执行的步骤的有 序集合。 程序: 是一个算法的表达。 进程: 是执行程序的活动, 因此一个进程可等价地定 义为执行算法的活动. 结论: 程序、算法和进程是不同的, 但也是有联系的, 一个程序是一个算法的表示, 而一个进程又是执行一 个算法的活动。Date142.计算机与算法 算法:是解题过程的精确描述,由有限条可完全机械执行的,有确定结果的 指令(或命令,语句)构成. 所谓计算机算法,是指: “人计算机”系统为解决给定问题, 需要以“人为 主导、计算机为主体”, 对所论问题的数据, 采取所设定的顺序结构、选择 结构、循环结构、并行结构、子算法结构及其结构化组合的控制方式, 来 组织和控制所认定的操作方式, 并一步一步具体实施的有穷操作过程的描 述。 人的主导作用:算法设计程序编码结果分析。 计算机的主体作用:计算机按好算法编写的程序执行并出结果 借助计算机来解决给定的问题，其热点、重点、难点都是算法设汁，而 绝不是人们常常误认为的程序编码。因此循着“对好巧妙绝”的 算法设计发展轨迹，努力探索和追求解决同一问题的算法族中佼佼者 最优算法，是算法设计人员应有的宝贵品质和良好习惯。 Date153.算法的系统目标 算法之所以特别重要和有用，并不是算法本身，而是算法 被执行（即其操作被一步一步具体施行）后所输出的信息 执行结果。因为执行结果不仅是算法的系统目标的具体 实现，尤其是人们所关心结果的具体兑现。因此，凡能正 确实现系统目标的算法，即能向人们提供正确及时、清晰 直观、简明易懂、信息完备的执行结果的算法，都是应当 提倡的良好算法；反之，则是应该防止的病态算法甚至错 误算法 。 例3-13：试设计并比较“求最小1、2、3位数的算术平均数” 的良好算法和病态算法。Date164.算法的操作执行者与操作对象 算法的操作执行者，其主导是人，其主体是计算机，要妥然 处理好两者关系； 算法的操作对象必然是解决给定问题所涉及到的数据； 避免出现脱离数据的算法和脱离算法的数据； 优先使用最基础的数据类型, 特别是整型、实型、字符（串 ）型和逻辑型。Date175.算法的操作方式与控制方式操作方式：分成数据运算和职能操作 职能操作:是数据输入、内部处理和数据输出操作的总称。 三大基本职能操作：输入操作、赋值操作与输出操作, 是算法设计的基础. 算法的流程控制与控制结构 ： 顺序:最简单 选择:最常用结构之一 循环:也是最常用结构之一 并行: 子算法: 上述前三种统称为算法基本结构 共性:一个入口.一个出口,无死程序 (永远执行不到),无死循环块Date18举例 设计一算法，求S=12+23+34+910 算法1： 算法：开始S0；k 1K10?Ss+k*(k+1)k k+1“S= ”,s结束开始S0；k 1Ss+k*(k+1)k k+1K10?“S= ”,s结束先判后运算先运算后判Date196.算法的基本特征 有穷性:有始有终是算法的最基本特征, 即算法必须由有 限步组成（P53中的例3-16不是算法）。 确定性:算法的每步操作必须唯一确定, 无歧义性。 数据输入:有零个或多个输入项。 信息输出:一个算法至少有一个已获得有效信息的输出操 作。 可执行 性:各步操作均能由计算机执行有穷次完成。Date203.1.3 数据结构初步 结构:可认为是特定元素间的关系 数据结构: 即数据间的关系. 一般说来，数据的组织和构造方式称为数据结构( Data structure）,且可概述为: 数据结构=系统目标+操作执行者+数据性质+数据组织。 也可简单理解为数据结构=数据+关系 数据结构=（D，R） 其中，D是数据元素的有限集，R是D上关系的有限集。 研究数据的性质、规律及其组织和构造方式