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

C语言程序设计进阶尹宝林第一讲：从程序设计语言到程序2005-1-2C语言程序设计进阶2初学者的困难初学者的困难n写出符合要求的程序n不知如何下手n不知程序错在哪里n不知如何改正错误n不知如何检查程序是否符合要求n不知如何写出高质量的程序2005-1-2C语言程序设计进阶3感到困难的原因感到困难的原因n对编程语言的掌握n对解题过程的掌握n对相关知识和技术的掌握n实践经验2005-1-2C语言程序设计进阶4解决问题的方法解决问题的方法n掌握程序设计的基本过程n掌握程序设计各步骤的相关技术n加强练习n多做练习n阅读高水平的程序2005-1-2C语言程序设计进阶5程序设计的基本过程程序设计的基本过程n明确任务要求n明确已知条件n逐步分解、自顶向下的设计n提出解题思路n确定关键算法和数据结构n确定程序结构n编码实现可运行的程序n检验程序是否符合要求2005-1-2C语言程序设计进阶6程序设计的步骤程序设计的步骤n分析n明确程序设计的目标和要求n明确已知条件和约束n设计n描述问题求解的过程和步骤n逐步缩短出发点和目标间的距离n编码n从设计到程序的转换2005-1-2C语言程序设计进阶7程序设计的步骤程序设计的步骤(续续)n调试n发现和改正编码中的错误n语法错误n语义错误n逻辑错误n检查和保证编码的正确性2005-1-2C语言程序设计进阶8程序设计的步骤程序设计的步骤(续续)n测试n排除设计错误n检验程序的正确性和可靠性n保证程序的功能和性能符合目标要求2005-1-2C语言程序设计进阶9不同规模程序的差异不同规模程序的差异n设计目标不同n功能和性能要求n生命周期、可维护性、可扩展性n可靠性n程序复杂程度不同n结构n代码量n错误处理方式2005-1-2C语言程序设计进阶10不同规模程序的差异不同规模程序的差异(续续)n使用环境和方式的差异n使用环境n单一平台n多种平台n网络环境n使用人员n自用n他人：专业人员 vs 一般用户n与其它程序的关系和交互方式2005-1-2C语言程序设计进阶11不同规模程序的差异不同规模程序的差异(续续)n工作内容差异n主要体现在分析、设计和测试n重点随程序复杂性增加而逐渐前移n测试工作的重要性随程序复杂性增加而增加2005-1-2C语言程序设计进阶12问题分析问题分析n分析的依据n明确的要求：问题描述n隐含的要求：规则、环境、常识n分析的方法n认真阅读题目，理解题目要点n认真思考，准确把握要求n记录关键点2005-1-2C语言程序设计进阶13问题分析问题分析(续续)n分析要点n明确问题的要求n功能：对环境及输入数据的处理过程及结果n性能：对系统资源的占用量n使用方式和环境 n人机界面n输入/输出数据及格式n与其它系统的交互 n理解问题的性质n把握所要解决的关键问题2005-1-2C语言程序设计进阶14分析结果的质量要求分析结果的质量要求n具体、准确、完整n符合题目的各项要求：明确的和隐含的n后续工作的依据：可操作性n后续工作检查的标准n必要的文档n记录需求要点n基本功能、输入数据的来源，数据格式、类型、数量和范围、需要处理的特殊情况n计算结果的输出格式和目标文件 2005-1-2C语言程序设计进阶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-x22005-1-2C语言程序设计进阶16多项式运算程序的功能多项式运算程序的功能n读入数据n数据结构和存储空间n完成计算n数据结构和算法n输出结果n格式要求2005-1-2C语言程序设计进阶17输出结果的格式要求输出结果的格式要求n对于一般项，n输出结果占一行n结果多项式按降幂方式排列n如果系数为0，则不输出该项 n各项与运算符之间空一格n除常数项外，如果系数为正负1，则不显示系数 n系数的正负号不直接输出，而是转化为该项前面的运算符：正号对应运算符+，负号对应运算符-n如果指数为0，则不输出x0而只输出系数。这包括系数为1的情况2005-1-2C语言程序设计进阶18输出结果的格式要求输出结果的格式要求(续续)n对于多项式的第一项的特殊规则：n若第一项系数为正数，则在其前面不输出任何符号n若第一项系数为负数，则在其前面输出符号-，且-与系数之间不留空格n对于整个多项式的特殊规则：n若多项式中所有项的系数均为0，即整个结果多项式为零，则输出0n操作符+、-前后要留有空格n末尾要输出换行符n,并且n与前面的可显示字符之间不留空格n多项式中变元的名字：n是一个字符，必须与输入多项式中的变元名字一致2005-1-2C语言程序设计进阶19设计设计n设计的依据n对问题的分析n计算环境的限制n设计的内容n建立计算模型n提出解题思路n确定计算方法n确定基本数据结构2005-1-2C语言程序设计进阶20设计设计(续续)n设计的检验n能否满足分析阶段所明确的需求n能否作为编码的依据2005-1-2C语言程序设计进阶21设计要点设计要点n解题的步骤n关键算法n输入/输出信息和格式n程序结构n错误处理n可能出现的错误n处理方法2005-1-2C语言程序设计进阶22计算模型计算模型n适用于与具体应用领域相关的题目n对所要求解的问题的一种抽象n用计算过程中的元素描述问题n计算过程中的元素:数据、公式、操作等n把应用领域中的实体及其关系抽象成数学模型n建立实体与计算对象的对应关系2005-1-2C语言程序设计进阶23计算模型的建立计算模型的建立n分析题目中与计算相关的实体及其相互关系，以及所要求解的内容。n细化实体、关系和求解要求，建立脱离具体应用领域的、比较抽象的问题描述及其与题目中实体的对应关系。n根据这一模型确定计算步骤、算法及数据结构等后续工作。2005-1-2C语言程序设计进阶24计算计算模型的建立模型的建立(续续)n计算模型不一定唯一n在已知的计算模型中找出最为合适或接近的计算模型n尽量简明、直观2005-1-2C语言程序设计进阶25计算模型的例计算模型的例nCalling CirclesCalling 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不在A、B、C、D的呼叫组中。n数学模型n有向图n节点对应用户n弧对应呼叫n呼叫组对应互相连通的节点n问题的求解n计算有向图的连通性2005-1-2C语言程序设计进阶26计算模型的例计算模型的例(续续)n模型的表述n邻接矩阵n人名与节点对应表n问题的求解n计算连通矩阵n节点根据连通性分组n根据分组和对应表解释连通矩阵2005-1-2C语言程序设计进阶27解题思路解题思路n问题求解的步骤序列n在问题描述的应用领域上进行n在计算模型的基础上进行n逐步探索、逐步细化n分而治之，把大问题分解成小问题n解题思路的可行性n每一步都可以用已知的方法解决n每一步都可以在限定条件下实际计算2005-1-2C语言程序设计进阶28解题思路解题思路(续续)n解题思路的描述n自然语言n解题思路的依据n对问题的分析和理解n经验、常识、n解题步骤的粒度取决于n问题的规模n人员的能力和经验n例：根据输入数据建立一个名字数值对照表 2005-1-2C语言程序设计进阶29解题思路的例解题思路的例1 1：Calling CirclesCalling Circlesn计算步骤 n读入数据，生成内部表示形式n生成用户人名表n生成初始邻接矩阵n计算图的连通性n计算邻接矩阵的2 n-1次幂n计算可达性矩阵n根据图的连通性产生输出结果n根据各对节点间的可达性分组n根据格式要求输出分组结果2005-1-2C语言程序设计进阶30解题思路的例解题思路的例2 2：N!的分解的分解n将N！分解成质数幂的乘积从标准输入读取一个整数N(2N60000),将N！的质数幂的乘积分解式打印到标准输出上,分解式中的质数按从小到大输出。对重复出 现 的 质 因 数，用 指 数 形 式 表 示。n例输入:5输出:23*3*52005-1-2C语言程序设计进阶31解题思路的例解题思路的例2(2(续续)n思路1n计算N！n分解质因数n可行性问题：N！不可直接表示nN的最大值为60000n12！231-1，232-1 13！2005-1-2C语言程序设计进阶32解题思路的例解题思路的例2(2(续续)n思路2n逐一地分解N以下所有的自然数n累加每个质因子出现的次数n依据n乘法的交换律和结合律n所需分解的最大的数为60000n可行性：每一步都实际可计算 n其它思路？2005-1-2C语言程序设计进阶33计算方法计算方法(续续)n根据计算模型设计和选择算法n算法应该满足的条件：1.每一步都应是含意确定、可以计算的2.应该在有限的步骤之内产生所需要的计算结果3.应该在有限的步骤内停止n算法的选择不唯一n算法评估和比较的主要考虑n运行速度/资源消耗n实现的复杂度2005-1-2C语言程序设计进阶34算法的基本要求算法的基本要求n使用计算机求解问题的有限步骤n表示为运算的序列n算法的基本性质n可操作性n可终止性n可达到预期的目标2005-1-2C语言程序设计进阶35算法分类算法分类n简单算法n专用算法n策略算法2005-1-2C语言程序设计进阶36简单算法简单算法n分析解决问题的常规思路n使用已有的知识可以直观地描述n描述应具体，具有可操作性n例：编写一个函数setbits(x,p,n,y),对x从右数第p位开始，向左向左连续n位(含第p位)置为y的最右边n位的值,其余各位保持不变。2005-1-2C语言程序设计进阶37函数函数setbitssetbits的算法的算法n取出y的最右边n位的值n生成最右n位为全1其余为全0的掩模n将y的值和掩模“按位与”n左移p-1位n取代x从右数第p位开始向左向左连续的n位nx从右数第p位开始向左向左连续n位置为0n将y的最右边n位的值左移p-1位n将上述结果和被处理后的x“按位或”2005-1-2C语言程序设计进阶38简单算法的例简单算法的例(2)(2)n计算N(1=N=1000)元人民币兑换成1分、2分和5分的硬币，有多少种可能的组合n算法n枚举n部分枚举公式n公式n分析的难度、实现的难度、计算复杂度不同2005-1-2C语言程序设计进阶39专用算法专用算法n数值算法，例：n高斯消元法、FFT、插值算法、龙格-库塔法n.n非数值算法，例：n排序算法n图形操作n代码优化、垃圾收集.2005-1-2C语言程序设计进阶40策略算法策略算法n搜索n递归n动态规划n贪心法n.2005-1-2C语言程序设计进阶41算法的评价算法的评价n对计算资源的占用n时间效率（CPU）n空间效率（内存）n绝对值/变化的量级n理解和实现的难易程度n性能和适用范围2005-1-2C语言程序设计进阶42算法的设计和选择算法的设计和选择n算法不唯一n最优算法也不一定唯一n算法设计和选择的依据n算法优缺点的比较n待解问题的复杂程度n计算环境的限制n速度n内存n实现的难易程度2005-1-2C语言程序设计进阶43算法设计的例：算法设计的例：N！的分解！的分解 n解题思路n对从2开始的自然数逐一分解质因数n将分解的结果累加到质数出现次数表中n算法1.建立按从小到大排序的N以下的质数表2.将所有的质数出现次数表项清零3.遍历从2到N的自然数，对每一个数Ni进行下述操作3.1 对Ni进行质因数分解并将Ni所包含的各个质因子的个数分别累加到相应的质数出现表项中2005-1-2C语言程序设计进阶44算法设计的例：算法设计的例：N！的分解！的分解(续续)n算法步骤3.1的细化n对每一个大于1的自然数ni进行操作如下1.将ni保存在单元A中，将质数2的序号保存在单元B中2.如果A中的数值等于1，则结束操作3.根据B中的序号取出质数，检查该数能否整除A中的数值4.如果可以整除，则将A被整除的结果保存到A，并根据B中的序号将质数出现表项的值加1，然后重复本步操作5.如果不能整除，则将B中的序号加1，转回2n每一步都具有可以直接编码的可操作性n具体编码取决于数据结构2005-1-2C语言程序设计进阶45数据结构数据结构n组织和保存数据n与算法的设计相辅相成、互相协调n算法描述对数据的操作n不了解算法，无法决定如何构造数据n算法的构造在很大程度上依赖于数据结构n应该与算法同时考虑n满足算法的要求n数据的表示：类型、范围、精度n可以在计算平台上方便地实现2005-1-2C语言程序设计进阶46数据结构的例数据结构的例：N！的分解！的分解 n质数表以及质数出现次数表：一维数组n质数表以及质数出现次数表中的表项数量：质数表中所需要的最大的质数的上限n最大的质因子不应该超过N。题目中N的上限是60000，因此质数表中最大的质数小于60000。n质数的分布随着数值期间向上增长而趋于稀疏n保守估计，在60000以内，质数约占1/8，质数表和质数出现次数表只要7500项n每项数据存储的类型n最大的质数不超过60000，可以用16位二进制位的无符号整数n一般情况下应该避免使用无符号整数来表示需要进行运算的数据n因此质数表项的数据类型需要使用32位的有符号整数n质数出现次数表项的数据类型n需要估计在所有质因子中，出现次数最多的质因子的最大出现次数是多少n2是最小的质数，在N！的各个质因子中，2出现的次数最多n将N！按定义展开成为从1到N的连乘，并对这一由自然数构成的因子序列进行考察n每21=2个就有一个数包含有一个2n每22=4个就有一个数包含有两个2n每2n=8个就有一个数包含有n个2nN！中所包含的2的个数为N/21+N/22+N/23+N/2 t，其中t为满足2 t=N的最大值n假设N的最大值为216=65536，则这时N！中所包含的2的个数为216-1=65535n选择32位的有符号整数作为质数出现次数表项的数据类型。10 100 200 500 1000 5000 600004254695168669 60572005-1-2C语言程序设计进阶47数据结构的例数据结构的例：N！的分解！的分解(续续)n质数出现次数表项分析的推广n对N以下的每一个质数，都可以直接计算出它在N！中出现的次数n这个方法比对N以下的各个正整数进行质因子分解更简单n新的解题思路：n用N以下质数的各次幂分别整除N，并将结果直接累加，得到对N！的质因子分解结果2005-1-2C语言程序设计进阶48数据结构的例数据结构的例：N！的分解！的分解(续续)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.22005-1-2C语言程序设计进阶49编码过程编码过程n程序的实现n从自然语言到编程语言n描述的进一步精确n符合编程语言的语法和语义n编码策略n自顶向下(top down)n分而治之(divide and conquer)n描述逐层细化n独立的基本任务2005-1-2C语言程序设计进阶50编码过程编码过程(续续)n保持良好的程序结构n对计算过程描述的层次性n对程序的描述要自顶向下，逐步细化n在每一个层面上只描述本层面直接使用到的计算步骤和控制机制n各个计算步骤的细节，在下一层次再进行细化的描述n自顶向下的层次性描述通过函数的调用和定义实现n对于过于复杂，不便直接使用C语句描述细节的计算步骤n用一个函数来表示这个计算步骤n在对这个函数具体定义时再详细描述计算步骤的操作细节n函数名说明所要完成的任务，参数传递计算所需要的数据n逐级细化，直至所有的操作都转化为基本的C语言计算/控制语句2005-1-2C语言程序设计进阶51编码过程编码过程(续续)n保持良好的程序结构(续续)n在main()中，只描述计算的基本步骤n对程序调用参数的错误处理n对大的计算过程的控制n各个计算步骤的细节，留待下面的层次逐步展开n函数的长度n一般不超过显示器一屏所能显示的长度n表达独立的操作步骤 2005-1-2C语言程序设计进阶52编码的例编码的例：N！的分解！的分解#define MAX_N60000#define MAX_ITEMMAX_N/8int primeMAX_ITEM,f_num_tabMAX_ITEM;int main(int c,char*v)int m,n;if(c 2)fprintf(stderr,Usage:%s Nn,v0);return 1;n=atoi(v1);if(n MAX_N)fprintf(stderr,N must be between 2 and%dn,MAX_N);return 2;m=gen_primes(n,prime);gen_factors(n,m,prime,f_num_tab);print(m,f_num_tab);return 0;2005-1-2C语言程序设计进阶53编码的例编码的例：N！的分解！的分解(续续)void gen_factors(int max,int p_no,int prime,int f_tab)int i,n;for(i=0;i p_no;i+)for(n=primei;n=max;n*=primei)f_tabi+=max/n;2005-1-2C语言程序设计进阶54编码的其它要点编码的其它要点n代码的描述应当完整简洁n语句的使用应当准确n代码应该容易阅读、理解和修改n代码应当便于重用n代码中应有适当的注释2005-1-2C语言程序设计进阶55代码描述的完整和简洁代码描述的完整和简洁n应该严格地根据解题步骤和算法的规定n完整地描述具体的计算过程n代码的描述应该直截了当，避免不必要的语句 n检查n解题步骤和算法的每一步是否都在代码中得到正确的描述n各个计算步骤的前后顺序是否正确n条件判断的内容和位置是否恰当2005-1-2C语言程序设计进阶56语语句的句的准确准确性性n避免由于疏忽或误解而产生编码错误 n常见的错误n=与=混淆nif else if else if 的嵌套：意图与描述不符nswitch case 语句中缺少必要的breakn变量未赋值即引用n字符与字符串混淆n按位与(&)与逻辑与(&)混淆，按位或(|)与逻辑或(|)混淆n运算符优先级和结合方式错误n例：1 a+b 1 0)还是大于等于0(n=0)n是i n还是i=n 还是 i name!=NULL;p+)if(strcmp(ext,p-name)=0)return p-func;return NULL;void error(int no,char*fmt,)va_list list;va_start(list,fmt);vfprintf(stderr,fmt,list);exit(no);2005-1-2C语言程序设计进阶88常见的错误常见的错误n对题目要求未能准确理解n对题目要求未能全面满足n算法和数据结构选择不当n语言成分选择不当n语言使用有误n对程序未进行充分的测试n我的程序没错，为什么结果不对？