ch01_程序设计与算法

1.1.2
程序设计的过程与特性
• 程序设计过程，主要包括
–问题分析
• 解决什么问题,要完成那些功能，有哪 些数据要输入和输出哪些信息等
–确定算法
• 怎么解决这个问题
–编码实现
• 怎么样让计算机理解你的思路，就是具 体采用某种程序设计语言实现
–程序设计三个过程往往是循环的，反复多次的
否 是 是 算法错? 否 编码错?
面向对象程序设计中几个概念：
• 对象（任何一个实体都可以看做一个对象）
– 我们将现实世界中任何有明确意义的事物称为实体。实体既 可以是具体的事物，也可以是人为的概念。
• 例如，学校、学生、学生的学习成绩、贷款、债权等等，都是实体。
– 客观世界中的任何实体，通常都具有一些静态特性和动态行 为，而动态行为一般只有在发生了特定的事件时才会表现出 来。
• 方法
– 概念
• 对象中用以模拟实体动态行为的“对数据施加的操 作”称为（对象的）方法。它是附属于对象的行为 和动作的 • 它是对象本身内含的函数或过程，用于完成某种特 定的功能，可供用户直接调用。
– 在程序中，使某个方法执行称为调用该方法。调 用对象方法的一般形式为：
对象名.方法名 [参数表] • 例如，text1.setfocus ‘使text1控件获得焦点 • 又如：Form1.Cls ´消除窗体Form1上的内容
• 例如，小孩子玩的气球，颜色和大小是其静态特性，上升和爆炸是其 动态行为，动态行为的发生是有一定触发条件的，如：只有在断了线 的时侯气球才会上升，在被刺破时气球才会爆炸。
– 在面向对象程序设计方法中，我们将描述实体静态特性的数 据以及对这些数据施加的所有操作封装在一起而构成的统一 体称为对象。 容器对象：其他对象的载体或容器，如窗体
– 例如，窗口中有一个按钮对象，希望在用户单 击此按钮时显示一个信息框：“你刚才单击了 我！”，则应该为该按钮的Click（单击）事件 编写响应代码： • MsgBox “你刚才单击了我！”
• 注意触发的条件和完成的功能，这样决定了代码 应该放在哪和怎么写
• 类 – 概念：是对同种对象的抽象描述，是创 建对象的模板，对象是类的实例。例如， 人类是人的抽象，一个个不同的人是人 类的实例。 – 在VB中，工具箱上的可视图标是VB系统 设计好的标准控件类如命令按钮类，若 当在窗体上画一个控件时，就将类实例 化为对象，即创建了一个控件对象。
1.1.1
程序与程序设计
• 为了解决某个实际问题而编排的指令序列 称之为程序； • 编排指令序列的语言称为程序设计语言； • 编制让计算机完成某项任务要执行的指令 序列的工作称为程序设计。
例：让计算机从1加到10000：
• 你得发出如下指令序列（程序）
– – – – – S=0 “让s=0”； “让x=1”； X=1 “将x加到s上”； While x<=10000 “将x加1”； S=s+x “如果x没有超过10000，则回到 第三步，否则，执行下一个命令”； X=x+1 – “报告结果s”。 Wend Print s
第四代程序设计语言
• 第四代程序设计语言(4GL)是 20世纪80年代提出了的 概念。人们对4GL的期望是，只需描述要解决的问题， 计算机就能自动地生成求解程序，从而完成求解任务。 4GL是一种“面向问题”的语言。 • 4GL以数据库管理系统所提供的功能为核心，进一步 构造了开发高层软件系统的开发环境。例如，数据库 设计器、查询设计器、报表设计器、窗口设计器和菜 单设计器等等，都为用户提供了一个良好的应用开发 环境(Visual FoxPro，Visual Basic，Delphi， PowerBuilder等)。 • 4GL提供了功能强大的非过程化问题定义手段，用户 只需告知系统要做什么，而无需说明怎么做，因此可 大大提高软件生产效率。
i, j, k为非负整数。
• 程序设计： • Private Sub Command1_Click() – Dim i As Integer, j As Integer, k As Integer – For i = 0 To 20 – For j = 0 To 33 – k = 100 - i - j – If 5 * i + 3 * j + k / 3 = 100 Then – Print i, j, k – End If – Next j – Next I – End Sub
主讲：胡凌云 E-Mail：misshz@
引例——―字幕动画”
• 在电视、电影的片头、片尾中常见用字幕动 画来显示制片的相关信息，这可通过VB编 程来方便实现。 • 例：简单的字幕动画演示。一行文字“欢迎 使用VB”在具有背景图案的窗体内自上而下 移动。移动方法有两种： • 单击手动按钮一次，移动50个单位； • 单击自动按钮，按定时器触发频率连续移动。 当内容超出窗体底部时，又从顶部重新开始 往下移动。
问题分析
确定算法
编码、调试
结果正确? 是
否
图1.1 程序设计过程
• 程序设计的特性
– 构造性 • 程序员则通过编排一个个简单的操作而构造出 能使计算机具有天才般本领的程序 • 构造性决定了程序设计结果（即程序）的多样 性。 • 构造性决定了不能用统一的标准来衡量程序的 质量。 • 构造性还决定了难以用形式化的方法来证明程 序的正确性。
例、百钱百鸡问题：公鸡5元一只，母鸡3元一
只，小鸡一元3只。现有100元钱，买100只鸡， 则公鸡、母鸡和小鸡各几只？问题出自中国古代 数学家张丘建的《算经》
• 题目分析：
令公鸡、母鸡和小鸡分别是i、j和k只，则得到方程组
i j k 100 5i 3 j k / 3 100
高级语言
• 20世纪50年代中后期出现的高级语言是第三代程 序设计语言。 • 高级语言不依赖于具体的计算机，其语法非常接 近于自然语言，所以用高级语言编写程序比较容 易，写出的程序也有较好的通用性。 • 第三代程序设计语言是面向过程的语言。所谓面 向过程，是指程序员在程序中不但要说明解决什 x=3 y=9 么问题，还要告诉计算机如何去解决，即详细地 z=x+y 告诉计算机解决问题的每一个步骤。
– 严谨性 • 程序员编制的程序必须是非常严谨的，一 点点的差错都有可能带来严重的后果。 比
如美国在1963年用于控制火箭飞行的程序中，把 一个逗号误写成点号，导致飞往火星的火箭爆炸， 造成1000万美元的损失。
• 程序严谨性的要求，决定了不能用自然语 言来书写程序。 • 编制程序所使用的程序设计语言是上下文 无关的形式语言，而程序要解决的问题都 是用自然语言陈述的。
1.1.4
程序设计方法
• 60年代:手工作坊中师傅带徒弟式的方法。 – 应用领域单一（应用于科学计算），程序的规 模都很小。 • 70年代：结构化程序设计 – 核心思想：自顶向下，逐步求精、模块化 – 不足之处：数据和对数据处理过程独立；不能 准确地反映真实世界
• 80年代：面向对象程序设计 – 是一种以对象为基础，以事件或消息来驱动对 象执行相应处理的程序设计方法。 – 它将数据及对数据的操作封装在一起，作为一 个相互依存、不可分离的整体——对象 – 它采用数据抽象和信息隐蔽技术，将这个整体 抽象成一种新的数据类型——类 – 优点：非常适合大型应用程序与系统程序的开 发
1.1 程序设计的基本概念
1.2 算法及算法的描述工具
1.3 算法设计举例
本章重点内容
• • • • • 什么是程序？ 什么是程序设计？ 程序设计的一般过程 算法的概念 算法的描述工具
1.1 程序设计的基本概念
• 程序设计的目的是帮助人们解决问题 • 计算机本身是个傻瓜 • 只有编写相关程序并交给计算机执行，计 算机才能实现相关功能
•
汇编语言
• 汇编语言的指令由容易记忆助记符表示 （比如，ADD表示做加法，MOV表示传送 数据），程序中可以直接使用十进制数， 数据在内存中的位置不需要程序员安排。
x dw 3 y dw 9 z dw ? mov ax, x mov cx, y add ax,cx mov z, ax
汇编语言源程序的可读 性和通用性也很差（虽 然比机器语言程序有所 改善）。
– 抽象性 • 计算机中使用二进制代码来映射现实世界 中的事物及其数据、信息，就必须对数据 和信息进行抽象。 • 现实世界中对事物进行的加工处理是千变 万化的，就象我们眼中的世界一样绚丽多 彩。 • 要让计算机来求解现实世界中的某一实际 问题，程序员必须将该问题的求解方法和 步骤进行归纳和抽象，将一系列的解题步 骤编排成一组计算机能够执行的操作指令 （即程序）。
1.1.3
程序设计语言
通用语言(VB,Pascal)
• 1.程序设计语言的分类
机器语言 用根 特据 点应
汇编语言
高级语言
专用语言(Lisp,Prolog)
数据库管理系统( SQL Server,Oracle,VFP)
的到 按 翻目 照 译标 源 方程 程 式序 序
解释型语言 编译型语言
2.程序设计语言的发展
• 第一代程序设计语言——机器语言； • 第二代程序设计语言——汇编语言； • 第三代程序设计语言——面向过程的高级 语言； • 第四代程序设计语言——面向问题的语言。
机器语言:直接与机器打交道
•
10111000 00000011 00000000 10100011 00000000 00000010 机器语言的指令由二进制代码组成，程序 10111000 00001001 00000000 10100011 00000010 00000010 中使用的数据是二进制数，数据在内存中 10001011 00001110 00000000 00000010 的位置要由程序员负责安排。 00000001 11001000 例如，有这样一个任务：先将 3和9两个数 10100011 00000100 00000010 写成十六进制是： 保存在内存中，然后计算这两个数的和， B8 03 00 A3 00 02 B8 09 00 A3 02 02 8B 和也保存在内存中。若用 IBM PC型计算机 0E 00 02 01 C8 A3 04 02 可读性差 的机器语言编写完成该任务的程序，则程 可移植性差 序是这样的：