算法设计与分析第1章

11程序设计方法学主讲老师陈菲教材程序设计方法学，胡正国、吴健、邓正宏编著，国防工业出版社12课程目标N设计方法学讲述程序的性质以及程序设计的理论、方法和实现技术的一门学科。V主要介绍程序设计方法学这一新兴学科的主要内容，即结构化程序设计、程序正确性证明、结构化程序的正确性证明、递归程序及其正确性证明、程序的形式说明和推导、程序变换技术、程序综合技术、面向对象的设计方法和大型程序设计方法学基础等。N培养学生运用这些理论和方法，从认识规律出发训练各种良好的程序设计习惯，掌握到成熟的有实用价值的具有完整科学理论和与之相关的技术方法作指导的软件设计和开发技术。13主要内容N程序设计方法产生与发展N程序设计方法学的定义与意义N结构化程序设计及其讨论的主要问题第1章程序设计方法学简介14背景N程序设计的发展过程N50年代后60年代初程序设计方法的重点是如何尽可能多地使用一些技巧，以节省内存空间，提高运算速度。N本世纪60年代以来程序设计主要问题是如何写出结构清晰、容易阅读、容易修改、容易验证即好结构的程序。V手工艺式的设计方法工程化的设计方法15问题1966年，BOHM,JACOPINI证明只要三种基本控制结构就能表达用一个入口、一个出口的框图（流程图）所能表达的任何程序逻辑1968年DIJKSTRACOMMUNICATIONOFACM“GOTO有害论”打响了第一炮NATO在德国软件工程会议建议GOTO语句太易把程序弄乱，应从一切高级语言中去掉；只用三种基本控制结构就可以写各种程序，而这样的程序可以自顶向下阅读而不会返回。引入一种新的程序设计思想、方法和风格结构化程序设计思想与概念，以期提高软件生产率和降低软件维护代价七十年代初期，大型系统软件，操作系统，数据库出现，给程序设计带来新的问题“软件危机”16N软件危机V对成本、进度的估算难以准确V用户对已完成的软件系统常常不满意V软件产品质量不可靠V软件常常难以维护V软件成本的上升V缺少文档资料V软件生产速度跟不上实际需要17程序设计方法学的产生和发展N七十年代现在结构化程序设计程序正确性证明的研究V1972年，MILLS进一步提出程序应该只有一个入口和出口，补充了结构程序的规则。V1974年，DEKNUTH对GOTO争论进行了总结“有些情形，主张废除；另一些情况，主张引进”。V1980年，GRIES综合了以谓词演算为基础的证明系统，称为“程序设计科学”。首次把程序设计从经验、技术上升为“科学”。18内容线索程序设计方法产生与发展N程序设计方法学的定义与意义N结构化程序设计及其讨论的主要问题19程序设计方法学定义N讨论程序的性质以及程序设计的理论和方法的一门学科。V包括结构程序设计数据抽象与模块化程序设计程序正确性证明程序变换程序的形式证明与推导程序综合技术面向对象的程序设计等等110程序设计的一般途径程序设计的一般途径111内容线索程序设计方法产生与发展程序设计方法学的定义与意义N结构化程序设计及其讨论的主要问题112结构化程序设计及其讨论的主要问题N什么是结构程序设计V结构程序设计是避免用GOTO语句的一种程序设计V结构程序设计是自顶向下的程序设计V结构程序设计是一种组织和编制程序的方法,利用它编制的程序是容易理解和容易修改的V程序结构化的一个主要功能是使得正确性的证明容易实现V结构程序设计允许在设计过程中的每一步验证其正确性,即自动导致自我说明与自我捍卫的程序风格V结构程序设计讨论了如何将任何大规模的和复杂的流程图转换成一种标准的形式,使得它们能够用几种标准的控制结构通常是顺序、分支和重复通过重复和嵌套来表示113结构程序设计Q结构程序设计是一种进行程序设计的原则和方法，按照这种原则和方法设计出的程序的特点是结构清晰容易阅读容易修改容易验证Q按照结构程序设计的要求设计出的程序设计语言称为结构程序设计语言Q利用程序设计语言或者说按照结构程序设计的思想编制出的程序称为结构化程序，或者好结构的程序Q结构化程序V顺序、分支和循环三种基本控制结构和程序块只有“一个入口和一个出口”的原则114结构化程序设计讨论的主要问题V（1）GOTO语句V（2）程序的结构V（3）逐步求精程序设计V（4）自顶向下的设计、编码和调试V（5）主程序员组的组织形式115关于GOTO语句N1、用“允许使用GOTO语句”的高级语言设计程序尽量避免使用GOTO语句N2、语言提供了多种控制结构，为避免使用GOTO语句创造条件N3、消除GOTO语句的通常方法有V增加辅助变量V改变程序执行顺序116关于GOTO语句N例1L1IFB1THENGOTOL2FIS1IFB2THENGOTOL2FIS2GOTOL1L2S3PTRUEWHILEPDOIFB1THENPFALSEELSES1IFB2THENPFALSEELSES2FIFIS3引入逻辑变量P117关于GOTO语句N例2查表程序V在一个表中有M个不同的数A1,A2,AM,在该表中查找数X，若找到则打印，否则将该数添加到表中FORI1TOMDOIFAIXTHENGOTO1FIMM1AMXGOTO21WIRTEI,X2PFALSEFORI1TOMDOIFAIXTHENPTRUEYIBREAKFIIFPTHENWIRTEY,XELSEMM1AMXFI引入逻辑变量P118关于GOTO语句N例2FORI1TOMDOIFAIXTHENGOTO1FIMM1AMXGOTO21WIRTEI,X2I1WHILEAIXAMXELSEWRITEI,XFI改变程序执行顺序119程序的结构N好结构V结构清晰、易于读写、易于验证、可靠性好、可维护性高的程序N结构程序V只包含三种基本控制结构，且程序块均只有一个入口和一个出口V序列结构（开型结构）AB120程序的结构V选择结构（开型结构）PAPABA1LA2ANCASE开型结构没有出现将控制转移到本结构入口的情形121程序的结构V循环结构（闭型结构）PAPAPABWHILEREPEATN1/2闭型结构在一定的条件下，将控制转移到本结构的入口处122逐步求精的程序设计方法简介NWIRTHN抽象程序对抽象的数据进行某些特定的运算，并用某些合适的记号（可能是自然语言）来表示N对抽象程序作进一步的分解，并进入下一层的抽象N这样，精细化过程一直进行下去，直到程序能被计算机接受为止。此时的程序可能是用某种高级语言或及其指令书写的我们对付复杂问题的最重要的办法是抽象。所以对于一个复杂问题，不应马上用计算机指令、数字与逻辑字来表达，而应该用较为自然的抽象语句来表示，从而得出抽象程序123逐步求精的程序设计方法简介N逐步求精的方法V在编制一个程序时，首先考虑程序的整体结构而忽视一些细节问题，然后逐步地、一层一层地细化程序直至用所选的语言完全描述每一个细节，即得到所期望的程序为止。124例1N编写一个程序，打印出前N个素数V第一步根据所提出问题，程序的结构可以写成PROGRAMEX1OUTPUTVARI,XINTEGERBEGINX1FORI1TONDOBEGINX“下一个素数”WRITEXENDEND125例1V第二步对语句“X“下一个素数”进一步求精PROGRAMEX1OUTPUTVARI,XINTEGERBEGINX1FORI1TONDOBEGINWRITEXENDENDX“下一个素数”2REPEATXX1UNTILPRIMPRIM“X是一个素数”3126例1REPEATXX1UNTILPRIMPRIM“X是一个素数”3K2PRIMTRUEWHILEPRIMANDKX而PLIM1X或者PLIM2X而PLIM12X这样，对所有满足KLIM的K，均有PKX130例1N综上所述，得到求解这个问题的一个完整的程序PROGRAMEX1OUTPUTTYPEINDEX1NVARXINTEGERI,K,LIMINDEXPRIMBOOLEANPARRAYINDEXOFINTEGERBEGINP12WRITE2X1LIM1FORI2TONDOBEGINREPEATXX2IFSQRPLIMXTHENLIMLIM1K2PRIMTRUEWHILEPRIMANDKLIMDOBEGINPRIMXMODPK0KK1ENDUNTILPRIMPIXWRITEXENDEND131自顶向下的设计、编码和调试Q先从该模块的功能描述出发，一层层地逐步细化，直到最后分解、细化成高级语言语句为止V一个大而完成的程序设计分解细化成一个个程序模块，每个模块一般是几十行至上百行，框图只占一页。程序只有一个入口、一个出口，只用了36种基本控制结构，所完成功能较明确独立。V这样，模块易于阅读理解，也便于检查其正确性。V在这种分解中，主程序引用下层模块或一个模块引用再下一层模块，都通过“子程序调用”或“空功能”实现。Q调试“假模块”（DUMMYMODULE）（驱动模块）,存根（SUB）（桩模块）V上层模块调用下层模块，编一个很简单的模块作为代用132被测模块测试用例接口局部数据结构路径错误处理边界条件驱动模块桩模块桩模块测试结果驱动模块DRIVER相当于所测模块的主程序。它接收测试数据，把这些数据传送给所测模块，最后再输出实际测试结果桩模块STUB用于代替所测模块调用的子模块。桩模块可以做少量的数据操作。目的是为了检验入口，输