从程序设计语言到程序.ppt

C语言程序设计进阶尹宝林,第一讲：从程序设计语言到程序,2005-1-2,C语言程序设计进阶,2,初学者的困难,写出符合要求的程序不知如何下手不知程序错在哪里不知如何改正错误不知如何检查程序是否符合要求不知如何写出高质量的程序,2005-1-2,C语言程序设计进阶,3,感到困难的原因,对编程语言的掌握对解题过程的掌握对相关知识和技术的掌握实践经验,2005-1-2,C语言程序设计进阶,4,解决问题的方法,掌握程序设计的基本过程掌握程序设计各步骤的相关技术加强练习多做练习阅读高水平的程序,2005-1-2,C语言程序设计进阶,5,程序设计的基本过程,明确任务要求明确已知条件逐步分解、自顶向下的设计提出解题思路确定关键算法和数据结构确定程序结构编码实现可运行的程序检验程序是否符合要求,2005-1-2,C语言程序设计进阶,6,程序设计的步骤,分析明确程序设计的目标和要求明确已知条件和约束设计描述问题求解的过程和步骤逐步缩短出发点和目标间的距离编码从设计到程序的转换,2005-1-2,C语言程序设计进阶,7,程序设计的步骤(续),调试发现和改正编码中的错误语法错误语义错误逻辑错误检查和保证编码的正确性,2005-1-2,C语言程序设计进阶,8,程序设计的步骤(续),测试排除设计错误检验程序的正确性和可靠性保证程序的功能和性能符合目标要求,2005-1-2,C语言程序设计进阶,9,不同规模程序的差异,设计目标不同功能和性能要求生命周期、可维护性、可扩展性可靠性程序复杂程度不同结构代码量错误处理方式,2005-1-2,C语言程序设计进阶,10,不同规模程序的差异(续),使用环境和方式的差异使用环境单一平台多种平台网络环境使用人员自用他人：专业人员vs一般用户与其它程序的关系和交互方式,2005-1-2,C语言程序设计进阶,11,不同规模程序的差异(续),工作内容差异主要体现在分析、设计和测试重点随程序复杂性增加而逐渐前移测试工作的重要性随程序复杂性增加而增加,2005-1-2,C语言程序设计进阶,12,问题分析,分析的依据明确的要求：问题描述隐含的要求：规则、环境、常识分析的方法认真阅读题目，理解题目要点认真思考，准确把握要求记录关键点,2005-1-2,C语言程序设计进阶,13,问题分析(续),分析要点明确问题的要求功能：对环境及输入数据的处理过程及结果性能：对系统资源的占用量使用方式和环境人机界面输入/输出数据及格式与其它系统的交互理解问题的性质把握所要解决的关键问题,2005-1-2,C语言程序设计进阶,14,分析结果的质量要求,具体、准确、完整符合题目的各项要求：明确的和隐含的后续工作的依据：可操作性后续工作检查的标准必要的文档记录需求要点基本功能、输入数据的来源，数据格式、类型、数量和范围、需要处理的特殊情况计算结果的输出格式和目标文件,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个或多个空格符。输入的多项式A和B的最高次数均不超过500，系数的绝对值不超过10000。输出结果写在标准输出上，占一行。结果多项式按降幂方式排列，各项的表示形式与输入形式相同，按常规的方式显示。例如，系数为0的项不输出；除常数项外，系数为1的项不显示系数。各项与运算符之间空一格。【输入样例】3x5+5x3+69x6+2x5+6x3+x2+6-【输出样例】-9x6+x5-x3-x2,2005-1-2,C语言程序设计进阶,16,多项式运算程序的功能,读入数据数据结构和存储空间完成计算数据结构和算法输出结果格式要求,2005-1-2,C语言程序设计进阶,17,输出结果的格式要求,对于一般项，输出结果占一行结果多项式按降幂方式排列如果系数为0，则不输出该项各项与运算符之间空一格除常数项外，如果系数为正负1，则不显示系数系数的正负号不直接输出，而是转化为该项前面的运算符：正号对应运算符+，负号对应运算符-如果指数为0，则不输出x0而只输出系数。这包括系数为1的情况,2005-1-2,C语言程序设计进阶,18,输出结果的格式要求(续),对于多项式的第一项的特殊规则：若第一项系数为正数，则在其前面不输出任何符号若第一项系数为负数，则在其前面输出符号-，且-与系数之间不留空格对于整个多项式的特殊规则：若多项式中所有项的系数均为0，即整个结果多项式为零，则输出0操作符+、-前后要留有空格末尾要输出换行符n,并且n与前面的可显示字符之间不留空格多项式中变元的名字：是一个字符，必须与输入多项式中的变元名字一致,2005-1-2,C语言程序设计进阶,19,设计,设计的依据对问题的分析计算环境的限制设计的内容建立计算模型提出解题思路确定计算方法确定基本数据结构,2005-1-2,C语言程序设计进阶,20,设计(续),设计的检验能否满足分析阶段所明确的需求能否作为编码的依据,2005-1-2,C语言程序设计进阶,21,设计要点,解题的步骤关键算法输入/输出信息和格式程序结构错误处理可能出现的错误处理方法,2005-1-2,C语言程序设计进阶,22,计算模型,适用于与具体应用领域相关的题目对所要求解的问题的一种抽象用计算过程中的元素描述问题计算过程中的元素:数据、公式、操作等把应用领域中的实体及其关系抽象成数学模型建立实体与计算对象的对应关系,2005-1-2,C语言程序设计进阶,23,计算模型的建立,分析题目中与计算相关的实体及其相互关系，以及所要求解的内容。细化实体、关系和求解要求，建立脱离具体应用领域的、比较抽象的问题描述及其与题目中实体的对应关系。根据这一模型确定计算步骤、算法及数据结构等后续工作。,2005-1-2,C语言程序设计进阶,24,计算模型的建立(续),计算模型不一定唯一在已知的计算模型中找出最为合适或接近的计算模型尽量简明、直观,2005-1-2,C语言程序设计进阶,25,计算模型的例,CallingCircles（1996ACMProgrammingContestFinals,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不在A、B、C、D的呼叫组中。数学模型有向图节点对应用户弧对应呼叫呼叫组对应互相连通的节点问题的求解计算有向图的连通性,2005-1-2,C语言程序设计进阶,26,计算模型的例(续),模型的表述邻接矩阵人名与节点对应表问题的求解计算连通矩阵节点根据连通性分组根据分组和对应表解释连通矩阵,2005-1-2,C语言程序设计进阶,27,解题思路,问题求解的步骤序列在问题描述的应用领域上进行在计算模型的基础上进行逐步探索、逐步细化分而治之，把大问题分解成小问题解题思路的可行性每一步都可以用已知的方法解决每一步都可以在限定条件下实际计算,2005-1-2,C语言程序设计进阶,28,解题思路(续),解题思路的描述自然语言解题思路的依据对问题的分析和理解经验、常识、解题步骤的粒度取决于问题的规模人员的能力和经验例：根据输入数据建立一个名字数值对照表,2005-1-2,C语言程序设计进阶,29,解题思路的例1：CallingCircles,计算步骤读入数据，生成内部表示形式生成用户人名表生成初始邻接矩阵计算图的连通性计算邻接矩阵的2n-1次幂计算可达性矩阵根据图的连通性产生输出结果根据各对节点间的可达性分组根据格式要求输出分组结果,2005-1-2,C语言程序设计进阶,30,解题思路的例2：N!的分解,将N！分解成质数幂的乘积从标准输入读取一个整数N(2N60000),将N！的质数幂的乘积分解式打印到标准输出上,分解式中的质数按从小到大输出。对重复出现的质因数，用指数形式表示。例输入:5输出:23*3*5,2005-1-2,C语言程序设计进阶,31,解题思路的例2(续),思路1计算N！分解质因数可行性问题：N！不可直接表示N的最大值为6000012！231-1，232-113！,2005-1-2,C语言程序设计进阶,32,解题思路的例2(续),思路2逐一地分解N以下所有的自然数累加每个质因子出现的次数依据乘法的交换律和结合律所需分解的最大的数为60000可行性：每一步都实际可计算其它思路？,2005-1-2,C语言程序设计进阶,33,计算方法(续),根据计算模型设计和选择算法算法应该满足的条件：每一步都应是含意确定、可以计算的应该在有限的步骤之内产生所需要的计算结果应该在有限的步骤内停止算法的选择不唯一算法评估和比较的主要考虑运行速度/资源消耗实现的复杂度,2005-1-2,C语言程序设计进阶,34,算法的基本要求,使用计算机求解问题的有限步骤表示为运算的序列算法的基本性质可操作性可终止性可达到预期的目标,2005-1-2,C语言程序设计进阶,35,算法分类,简单算法专用算法策略算法,2005-1-2,C语言程序设计进阶,36,简单算法,分析解决问题的常规思路使用已有的知识可以直观地描述描述应具体，具有可操作性例：编写一个函数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,简单算法的例(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开始的自然数逐一分解质因数将分解的结果累加到质数出现次数表中算法建立按从小到大排序的N以下的质数表将所有的质数出现次数表项清零遍历从2到N的自然数，对每一个数Ni进行下述操作3.1对Ni进行质因数分解并将Ni所包含的各个质因子的个数分别累加到相应的质数出现表项中,2005-1-2,C语言程序设计进阶,44,算法设计的例：N！的分解(续),算法步骤3.1的细化对每一个大于1的自然数ni进行操作如下1.将ni保存在单元A中，将质数2的序号保存在单元B中2.如果A中的数值等于1，则结束操作3.根据B中的序号取出质数，检查该数能否整除A中的数值4.如果可以整除，则将A被整除的结果保存到A，并根据B中的序号将质数出现表项的值加1，然后重复本步操作5.如果不能整除，则将B中的序号加1，转回2每一步都具有可以直接编码的可操作性具体编码取决于数据结构,2005-1-2,C语言程序设计进阶,45,数据结构,组织和保存数据与算法的设计相辅相成、互相协调算法描述对数据的操作不了解算法，无法决定如何构造数据算法的构造在很大程度上依赖于数据结构应该与算法同时考虑满足算法的要求数据的表示：类型、范围、精度可以在计算平台上方便地实现,2005-1-2,C语言程序设计进阶,46,数据结构的例：N！的分解,质数表以及质数出现次数表：一维数组质数表以及质数出现次数表中的表项数量：质数表中所需要的最大的质数的上限最大的质因子不应该超过N。题目中N的上限是60000，因此质数表中最大的质数小于60000。质数的分布随着数值期间向上增长而趋于稀疏保守估计，在60000以内，质数约占1/8，质数表和质数出现次数表只要7500项每项数据存储的类型最大的质数不超过60000，可以用16位二进制位的无符号整数一般情况下应该避免使用无符号整数来表示需要进行运算的数据因此质数表项的数据类型需要使用32位的有符号整数质数出现次数表项的数据类型需要估计在所有质因子中，出现次数最多的质因子的最大出现次数是多少2是最小的质数，在N！的各个质因子中，2出现的次数最多将N！按定义展开成为从1到N的连乘，并对这一由自然数构成的因子序列进行考察每21=2个就有一个数包含有一个2每22=4个就有一个数包含有两个2每2n=8个就有一个数包含有n个2N！中所包含的2的个数为N/21+N/22+N/23+N/2t，其中t为满足2t=N的最大值假设N的最大值为216=65536，则这时N！中所包含的2的个数为216-1=65535选择32位的有符号整数作为质数出现次数表项的数据类型。,2005-1-2,C语言程序设计进阶,47,数据结构的例：N！的分解(续),质数出现次数表项分析的推广对N以下的每一个质数，都可以直接计算出它在N！中出现的次数这个方法比对N以下的各个正整数进行质因子分解更简单新的解题思路：用N以下质数的各次幂分别整除N，并将结果直接累加，得到对N！的质因子分解结果,2005-1-2,C语言程序设计进阶,48,数据结构的例：N！的分解(续),与上述思路对应的算法描述1建立按从小到大排序的N以下的质数表2将所有的质数出现次数表项清零3对于所有的从2到小于等于N的最大质数进行遍历，并对每一个质数Pi进行：3.1将质数Pi放入存储单元A中3.2用A中的数整除N，将结果累加到相应的质数出现表项中3.3将A中的数乘以质数Pi，比较A中的数是否大于N3.4如果A中的数大于N，结束对质数Pi的处理3.5如果A中的数不大于N，则转到3.2,2005-1-2,C语言程序设计进阶,49,编码过程,程序的实现从自然语言到编程语言描述的进一步精确符合编程语言的语法和语义编码策略自顶向下(topdown)分而治之(divideandconquer)描述逐层细化独立的基本任务,2005-1-2,C语言程序设计进阶,50,编码过程(续),保持良好的程序结构对计算过程描述的层次性对程序的描述要自顶向下，逐步细化在每一个层面上只描述本层面直接使用到的计算步骤和控制机制各个计算步骤的细节，在下一层次再进行细化的描述自顶向下的层次性描述通过函数的调用和定义实现对于过于复杂，不便直接使用C语句描述细节的计算步骤用一个函数来表示这个计算步骤在对这个函数具体定义时再详细描述计算步骤的操作细节函数名说明所要完成的任务，参数传递计算所需要的数据逐级细化，直至所有的操作都转化为基本的C语言计算/控制语句,2005-1-2,C语言程序设计进阶,51,编码过程(续),保持良好的程序结构(续)在main()