从程序设计语言到程序

《从程序设计语言到程序》由会员分享，可在线阅读，更多相关《从程序设计语言到程序（88页珍藏版）》请在金锄头文库上搜索。

1、C语言程序设计进阶 尹宝林,第一讲：从程序设计语言到程序,2005-1-2,C语言程序设计进阶,2,初学者的困难,写出符合要求的程序 不知如何下手 不知程序错在哪里 不知如何改正错误 不知如何检查程序是否符合要求 不知如何写出高质量的程序,2005-1-2,C语言程序设计进阶,3,感到困难的原因,对编程语言的掌握 对解题过程的掌握 对相关知识和技术的掌握 实践经验,2005-1-2,C语言程序设计进阶,4,解决问题的方法,掌握程序设计的基本过程 掌握程序设计各步骤的相关技术 加强练习 多做练习 阅读高水平的程序,2005-1-2,C语言程序设计进阶,5,程序设计的基本过程,明确任务要求 明确已

2、知条件 逐步分解、自顶向下的设计 提出解题思路 确定关键算法和数据结构 确定程序结构 编码实现可运行的程序 检验程序是否符合要求,2005-1-2,C语言程序设计进阶,6,程序设计的步骤,分析 明确程序设计的目标和要求 明确已知条件和约束 设计 描述问题求解的过程和步骤 逐步缩短出发点和目标间的距离 编码 从设计到程序的转换,2005-1-2,C语言程序设计进阶,7,程序设计的步骤(续),调试 发现和改正编码中的错误 语法错误 语义错误 逻辑错误 检查和保证编码的正确性,2005-1-2,C语言程序设计进阶,8,程序设计的步骤(续),测试 排除设计错误 检验程序的正确性和可靠性 保证程序的功能

3、和性能符合目标要求,2005-1-2,C语言程序设计进阶,9,不同规模程序的差异,设计目标不同 功能和性能要求 生命周期、可维护性、可扩展性 可靠性 程序复杂程度不同 结构 代码量 错误处理方式,2005-1-2,C语言程序设计进阶,10,不同规模程序的差异(续),使用环境和方式的差异 使用环境 单一平台 多种平台 网络环境 使用人员 自用 他人：专业人员 vs 一般用户 与其它程序的关系和交互方式,2005-1-2,C语言程序设计进阶,11,不同规模程序的差异(续),工作内容差异 主要体现在分析、设计和测试 重点随程序复杂性增加而逐渐前移 测试工作的重要性随程序复杂性增加而增加,2005-1

4、-2,C语言程序设计进阶,12,问题分析,分析的依据 明确的要求：问题描述 隐含的要求：规则、环境、常识 分析的方法 认真阅读题目，理解题目要点 认真思考，准确把握要求 记录关键点,2005-1-2,C语言程序设计进阶,13,问题分析(续),分析要点 明确问题的要求 功能：对环境及输入数据的处理过程及结果 性能：对系统资源的占用量 使用方式和环境 人机界面 输入/输出数据及格式 与其它系统的交互 理解问题的性质 把握所要解决的关键问题,2005-1-2,C语言程序设计进阶,14,分析结果的质量要求,具体、准确、完整 符合题目的各项要求：明确的和隐含的 后续工作的依据：可操作性 后续工作检查的标

5、准 必要的文档 记录需求要点 基本功能、输入数据的来源，数据格式、类型、数量和范围、需要处理的特殊情况 计算结果的输出格式和目标文件,2005-1-2,C语言程序设计进阶,15,问题分析的例,已知一元多项式A = anxn + + a1x + a0, B = bnxn + + b1x + b0 根据运算符+、-、*，分别计算A + B、A - B、A * B。 输入数据由三行组成。第一行是多项式A，第二行是多项式B，第三行是一个运算符，表示所要进行的运算。多项式中除常数项外的每一项的形式为AnXN，其中An是一个整数，表示该项的系数，X是变量名，N是该项的次数。各项与+之间可以有0个或多个空格

6、符。输入的多项式A和B的最高次数均不超过500，系数的绝对值不超过10000。 输出结果写在标准输出上，占一行。结果多项式按降幂方式排列，各项的表示形式与输入形式相同，按常规的方式显示。例如，系数为0的项不输出；除常数项外，系数为1的项不显示系数。各项与运算符之间空一格。 【输入样例】 3x5 + 5x3 + 6 9x6 + 2x5 + 6x3 + x2 + 6 - 【输出样例】 -9x6 + x5 - x3 - x2,2005-1-2,C语言程序设计进阶,16,多项式运算程序的功能,读入数据 数据结构和存储空间 完成计算 数据结构和算法 输出结果 格式要求,2005-1-2,C语言程序设计进

7、阶,17,输出结果的格式要求,对于一般项， 输出结果占一行 结果多项式按降幂方式排列 如果系数为0，则不输出该项 各项与运算符之间空一格 除常数项外，如果系数为正负1，则不显示系数 系数的正负号不直接输出，而是转化为该项前面的运算符：正号对应运算符+， 负号对应运算符- 如果指数为0，则不输出x0而只输出系数。这包括系数为1的情况,2005-1-2,C语言程序设计进阶,18,输出结果的格式要求(续),对于多项式的第一项的特殊规则： 若第一项系数为正数，则在其前面不输出任何符号 若第一项系数为负数，则在其前面输出符号“-“，且“-“与系数之间不留空格 对于整个多项式的特殊规则： 若多项式中所有项

8、的系数均为0，即整个结果多项式为零，则输出0 操作符+、-前后要留有空格 末尾要输出换行符n, 并且n与前面的可显示字符之间不留空格 多项式中变元的名字： 是一个字符，必须与输入多项式中的变元名字一致,2005-1-2,C语言程序设计进阶,19,设计,设计的依据 对问题的分析 计算环境的限制 设计的内容 建立计算模型 提出解题思路 确定计算方法 确定基本数据结构,2005-1-2,C语言程序设计进阶,20,设计(续),设计的检验 能否满足分析阶段所明确的需求 能否作为编码的依据,2005-1-2,C语言程序设计进阶,21,设计要点,解题的步骤 关键算法 输入/输出信息和格式 程序结构 错误处理

9、 可能出现的错误 处理方法,2005-1-2,C语言程序设计进阶,22,计算模型,适用于与具体应用领域相关的题目 对所要求解的问题的一种抽象 用计算过程中的元素描述问题 计算过程中的元素: 数据、公式、操作等 把应用领域中的实体及其关系抽象成数学模型 建立实体与计算对象的对应关系,2005-1-2,C语言程序设计进阶,23,计算模型的建立,分析题目中与计算相关的实体及其相互关系，以及所要求解的内容。 细化实体、关系和求解要求，建立脱离具体应用领域的、比较抽象的问题描述及其与题目中实体的对应关系。 根据这一模型确定计算步骤、算法及数据结构等后续工作。,2005-1-2,C语言程序设计进阶,24,

10、计算模型的建立(续),计算模型不一定唯一 在已知的计算模型中找出最为合适或接近的计算模型 尽量简明、直观,2005-1-2,C语言程序设计进阶,25,计算模型的例,Calling Circles（1996 ACM Programming Contest Finals,B） 题目大意：如果A呼叫过B，B又直接或间接地呼叫过A，则A和B同在一个呼叫组中。给出一组电话呼叫记录，计算出各个呼叫组及其中的人员。例如，A呼叫过B，B呼叫过C，C呼叫过A，则A、B、C在一个呼叫组中。同时，C又呼叫过D，D也呼叫过C，则D也与A、B、C同在一个组中。B又呼叫过E，但E没有呼叫过A、B、C、D中的任何一位，则E

11、不在A、B、C、D的呼叫组中。 数学模型 有向图 节点对应用户 弧对应呼叫 呼叫组对应互相连通的节点 问题的求解 计算有向图的连通性,2005-1-2,C语言程序设计进阶,26,计算模型的例(续),模型的表述 邻接矩阵 人名与节点对应表 问题的求解 计算连通矩阵 节点根据连通性分组 根据分组和对应表解释连通矩阵,2005-1-2,C语言程序设计进阶,27,解题思路,问题求解的步骤序列 在问题描述的应用领域上进行 在计算模型的基础上进行 逐步探索、逐步细化 分而治之，把大问题分解成小问题 解题思路的可行性 每一步都可以用已知的方法解决 每一步都可以在限定条件下实际计算,2005-1-2,C语言程

12、序设计进阶,28,解题思路(续),解题思路的描述 自然语言 解题思路的依据 对问题的分析和理解 经验、常识、 解题步骤的粒度取决于 问题的规模 人员的能力和经验 例：根据输入数据建立一个名字数值对照表,2005-1-2,C语言程序设计进阶,29,解题思路的例1：Calling Circles,计算步骤 读入数据，生成内部表示形式 生成用户人名表 生成初始邻接矩阵 计算图的连通性 计算邻接矩阵的2 n-1次幂 计算可达性矩阵 根据图的连通性产生输出结果 根据各对节点间的可达性分组 根据格式要求输出分组结果,2005-1-2,C语言程序设计进阶,30,解题思路的例2：N!的分解,将N！分解成质数幂

13、的乘积 从标准输入读取一个整数N(2N60000),将N！的质数幂的乘积分解式打印到标准输出上,分解式中的质数按从小到大输出。对重复出现的质因数，用指数形式表示。 例 输入: 5 输出: 23*3*5,2005-1-2,C语言程序设计进阶,31,解题思路的例2(续),思路1 计算N！ 分解质因数 可行性问题：N！不可直接表示 N的最大值为60000 12！ 231-1，232-1 13！,2005-1-2,C语言程序设计进阶,32,解题思路的例2(续),思路2 逐一地分解N以下所有的自然数 累加每个质因子出现的次数 依据 乘法的交换律和结合律 所需分解的最大的数为60000 可行性：每一步都实

14、际可计算 其它思路？,2005-1-2,C语言程序设计进阶,33,计算方法(续),根据计算模型设计和选择算法 算法应该满足的条件： 每一步都应是含意确定、可以计算的 应该在有限的步骤之内产生所需要的计算结果 应该在有限的步骤内停止 算法的选择不唯一 算法评估和比较的主要考虑 运行速度/资源消耗 实现的复杂度,2005-1-2,C语言程序设计进阶,34,算法的基本要求,使用计算机求解问题的有限步骤 表示为运算的序列 算法的基本性质 可操作性 可终止性 可达到预期的目标,2005-1-2,C语言程序设计进阶,35,算法分类,简单算法 专用算法 策略算法,2005-1-2,C语言程序设计进阶,36,

15、简单算法,分析解决问题的常规思路 使用已有的知识可以直观地描述 描述应具体，具有可操作性 例： 编写一个函数setbits(x,p,n,y), 对x从右数第p位开始，向左连续n位(含第p位)置为y的最右边n位的值,其余各位保持不变。,2005-1-2,C语言程序设计进阶,37,函数setbits的算法,取出y的最右边n位的值 生成最右n位为全1其余为全0的掩模 将y的值和掩模“按位与” 左移p-1位 取代x从右数第p位开始向左连续的n位 x从右数第p位开始向左连续n位置为0 将y的最右边n位的值左移p-1位 将上述结果和被处理后的x “按位或”,2005-1-2,C语言程序设计进阶,38,简单

16、算法的例(2),计算N(1 = N =1000)元人民币兑换成1分、2分和5分的硬币，有多少种可能的组合 算法 枚举 部分枚举公式 公式 分析的难度、实现的难度、计算复杂度不同,2005-1-2,C语言程序设计进阶,39,专用算法,数值算法，例： 高斯消元法、FFT、插值算法、龙格-库塔法 . . 非数值算法，例： 排序算法 图形操作 代码优化、垃圾收集 . .,2005-1-2,C语言程序设计进阶,40,策略算法,搜索 递归 动态规划 贪心法 . .,2005-1-2,C语言程序设计进阶,41,算法的评价,对计算资源的占用 时间效率（CPU） 空间效率（内存） 绝对值/变化的量级 理解和实现的难易程度 性能和适用范围,2005-1-2,C语言程序设计进阶,42,算法的设计和选择,算法不唯一 最优算法也不一定唯一 算法设计和选择的依据 算法优缺点的比较 待解问题的复杂程度 计算环境的限制 速度 内存 实现的难易程度,2005-1-2,C语言程序设计进阶,43,算法设计的例：N！的分解,解题思路 对从2开始的自然数逐一分解质因数 将分解的结果累