算法設(shè)計(jì)與分析第1章

11程序設(shè)計(jì)方法學(xué)主講老師陳菲教材程序設(shè)計(jì)方法學(xué)，胡正國、吳健、鄧正宏編著，國防工業(yè)出版社12課程目標(biāo)N設(shè)計(jì)方法學(xué)講述程序的性質(zhì)以及程序設(shè)計(jì)的理論、方法和實(shí)現(xiàn)技術(shù)的一門學(xué)科。V主要介紹程序設(shè)計(jì)方法學(xué)這一新興學(xué)科的主要內(nèi)容，即結(jié)構(gòu)化程序設(shè)計(jì)、程序正確性證明、結(jié)構(gòu)化程序的正確性證明、遞歸程序及其正確性證明、程序的形式說明和推導(dǎo)、程序變換技術(shù)、程序綜合技術(shù)、面向?qū)ο蟮脑O(shè)計(jì)方法和大型程序設(shè)計(jì)方法學(xué)基礎(chǔ)等。N培養(yǎng)學(xué)生運(yùn)用這些理論和方法，從認(rèn)識規(guī)律出發(fā)訓(xùn)練各種良好的程序設(shè)計(jì)習(xí)慣，掌握到成熟的有實(shí)用價(jià)值的具有完整科學(xué)理論和與之相關(guān)的技術(shù)方法作指導(dǎo)的軟件設(shè)計(jì)和開發(fā)技術(shù)。13主要內(nèi)容N程序設(shè)計(jì)方法產(chǎn)生與發(fā)展N程序設(shè)計(jì)方法學(xué)的定義與意義N結(jié)構(gòu)化程序設(shè)計(jì)及其討論的主要問題第1章程序設(shè)計(jì)方法學(xué)簡介14背景N程序設(shè)計(jì)的發(fā)展過程N(yùn)50年代后60年代初程序設(shè)計(jì)方法的重點(diǎn)是如何盡可能多地使用一些技巧，以節(jié)省內(nèi)存空間，提高運(yùn)算速度。N本世紀(jì)60年代以來程序設(shè)計(jì)主要問題是如何寫出結(jié)構(gòu)清晰、容易閱讀、容易修改、容易驗(yàn)證即好結(jié)構(gòu)的程序。V手工藝式的設(shè)計(jì)方法工程化的設(shè)計(jì)方法15問題1966年，BOHM,JACOPINI證明只要三種基本控制結(jié)構(gòu)就能表達(dá)用一個(gè)入口、一個(gè)出口的框圖（流程圖）所能表達(dá)的任何程序邏輯1968年DIJKSTRACOMMUNICATIONOFACM“GOTO有害論”打響了第一炮NATO在德國軟件工程會議建議GOTO語句太易把程序弄亂，應(yīng)從一切高級語言中去掉；只用三種基本控制結(jié)構(gòu)就可以寫各種程序，而這樣的程序可以自頂向下閱讀而不會返回。引入一種新的程序設(shè)計(jì)思想、方法和風(fēng)格結(jié)構(gòu)化程序設(shè)計(jì)思想與概念，以期提高軟件生產(chǎn)率和降低軟件維護(hù)代價(jià)七十年代初期，大型系統(tǒng)軟件，操作系統(tǒng)，數(shù)據(jù)庫出現(xiàn)，給程序設(shè)計(jì)帶來新的問題“軟件危機(jī)”16N軟件危機(jī)V對成本、進(jìn)度的估算難以準(zhǔn)確V用戶對已完成的軟件系統(tǒng)常常不滿意V軟件產(chǎn)品質(zhì)量不可靠V軟件常常難以維護(hù)V軟件成本的上升V缺少文檔資料V軟件生產(chǎn)速度跟不上實(shí)際需要17程序設(shè)計(jì)方法學(xué)的產(chǎn)生和發(fā)展N七十年代現(xiàn)在結(jié)構(gòu)化程序設(shè)計(jì)程序正確性證明的研究V1972年，MILLS進(jìn)一步提出程序應(yīng)該只有一個(gè)入口和出口，補(bǔ)充了結(jié)構(gòu)程序的規(guī)則。V1974年，DEKNUTH對GOTO爭論進(jìn)行了總結(jié)“有些情形，主張廢除；另一些情況，主張引進(jìn)”。V1980年，GRIES綜合了以謂詞演算為基礎(chǔ)的證明系統(tǒng)，稱為“程序設(shè)計(jì)科學(xué)”。首次把程序設(shè)計(jì)從經(jīng)驗(yàn)、技術(shù)上升為“科學(xué)”。18內(nèi)容線索程序設(shè)計(jì)方法產(chǎn)生與發(fā)展N程序設(shè)計(jì)方法學(xué)的定義與意義N結(jié)構(gòu)化程序設(shè)計(jì)及其討論的主要問題19程序設(shè)計(jì)方法學(xué)定義N討論程序的性質(zhì)以及程序設(shè)計(jì)的理論和方法的一門學(xué)科。V包括結(jié)構(gòu)程序設(shè)計(jì)數(shù)據(jù)抽象與模塊化程序設(shè)計(jì)程序正確性證明程序變換程序的形式證明與推導(dǎo)程序綜合技術(shù)面向?qū)ο蟮某绦蛟O(shè)計(jì)等等110程序設(shè)計(jì)的一般途徑程序設(shè)計(jì)的一般途徑111內(nèi)容線索程序設(shè)計(jì)方法產(chǎn)生與發(fā)展程序設(shè)計(jì)方法學(xué)的定義與意義N結(jié)構(gòu)化程序設(shè)計(jì)及其討論的主要問題112結(jié)構(gòu)化程序設(shè)計(jì)及其討論的主要問題N什么是結(jié)構(gòu)程序設(shè)計(jì)V結(jié)構(gòu)程序設(shè)計(jì)是避免用GOTO語句的一種程序設(shè)計(jì)V結(jié)構(gòu)程序設(shè)計(jì)是自頂向下的程序設(shè)計(jì)V結(jié)構(gòu)程序設(shè)計(jì)是一種組織和編制程序的方法,利用它編制的程序是容易理解和容易修改的V程序結(jié)構(gòu)化的一個(gè)主要功能是使得正確性的證明容易實(shí)現(xiàn)V結(jié)構(gòu)程序設(shè)計(jì)允許在設(shè)計(jì)過程中的每一步驗(yàn)證其正確性,即自動(dòng)導(dǎo)致自我說明與自我捍衛(wèi)的程序風(fēng)格V結(jié)構(gòu)程序設(shè)計(jì)討論了如何將任何大規(guī)模的和復(fù)雜的流程圖轉(zhuǎn)換成一種標(biāo)準(zhǔn)的形式,使得它們能夠用幾種標(biāo)準(zhǔn)的控制結(jié)構(gòu)通常是順序、分支和重復(fù)通過重復(fù)和嵌套來表示113結(jié)構(gòu)程序設(shè)計(jì)Q結(jié)構(gòu)程序設(shè)計(jì)是一種進(jìn)行程序設(shè)計(jì)的原則和方法，按照這種原則和方法設(shè)計(jì)出的程序的特點(diǎn)是結(jié)構(gòu)清晰容易閱讀容易修改容易驗(yàn)證Q按照結(jié)構(gòu)程序設(shè)計(jì)的要求設(shè)計(jì)出的程序設(shè)計(jì)語言稱為結(jié)構(gòu)程序設(shè)計(jì)語言Q利用程序設(shè)計(jì)語言或者說按照結(jié)構(gòu)程序設(shè)計(jì)的思想編制出的程序稱為結(jié)構(gòu)化程序，或者好結(jié)構(gòu)的程序Q結(jié)構(gòu)化程序V順序、分支和循環(huán)三種基本控制結(jié)構(gòu)和程序塊只有“一個(gè)入口和一個(gè)出口”的原則114結(jié)構(gòu)化程序設(shè)計(jì)討論的主要問題V（1）GOTO語句V（2）程序的結(jié)構(gòu)V（3）逐步求精程序設(shè)計(jì)V（4）自頂向下的設(shè)計(jì)、編碼和調(diào)試V（5）主程序員組的組織形式115關(guān)于GOTO語句N1、用“允許使用GOTO語句”的高級語言設(shè)計(jì)程序盡量避免使用GOTO語句N2、語言提供了多種控制結(jié)構(gòu)，為避免使用GOTO語句創(chuàng)造條件N3、消除GOTO語句的通常方法有V增加輔助變量V改變程序執(zhí)行順序116關(guān)于GOTO語句N例1L1IFB1THENGOTOL2FIS1IFB2THENGOTOL2FIS2GOTOL1L2S3PTRUEWHILEPDOIFB1THENPFALSEELSES1IFB2THENPFALSEELSES2FIFIS3引入邏輯變量P117關(guān)于GOTO語句N例2查表程序V在一個(gè)表中有M個(gè)不同的數(shù)A1,A2,AM,在該表中查找數(shù)X，若找到則打印，否則將該數(shù)添加到表中FORI1TOMDOIFAIXTHENGOTO1FIMM1AMXGOTO21WIRTEI,X2PFALSEFORI1TOMDOIFAIXTHENPTRUEYIBREAKFIIFPTHENWIRTEY,XELSEMM1AMXFI引入邏輯變量P118關(guān)于GOTO語句N例2FORI1TOMDOIFAIXTHENGOTO1FIMM1AMXGOTO21WIRTEI,X2I1WHILEAIXAMXELSEWRITEI,XFI改變程序執(zhí)行順序119程序的結(jié)構(gòu)N好結(jié)構(gòu)V結(jié)構(gòu)清晰、易于讀寫、易于驗(yàn)證、可靠性好、可維護(hù)性高的程序N結(jié)構(gòu)程序V只包含三種基本控制結(jié)構(gòu)，且程序塊均只有一個(gè)入口和一個(gè)出口V序列結(jié)構(gòu)（開型結(jié)構(gòu)）AB120程序的結(jié)構(gòu)V選擇結(jié)構(gòu)（開型結(jié)構(gòu)）PAPABA1LA2ANCASE開型結(jié)構(gòu)沒有出現(xiàn)將控制轉(zhuǎn)移到本結(jié)構(gòu)入口的情形121程序的結(jié)構(gòu)V循環(huán)結(jié)構(gòu)（閉型結(jié)構(gòu)）PAPAPABWHILEREPEATN1/2閉型結(jié)構(gòu)在一定的條件下，將控制轉(zhuǎn)移到本結(jié)構(gòu)的入口處122逐步求精的程序設(shè)計(jì)方法簡介NWIRTHN抽象程序?qū)Τ橄蟮臄?shù)據(jù)進(jìn)行某些特定的運(yùn)算，并用某些合適的記號（可能是自然語言）來表示N對抽象程序作進(jìn)一步的分解，并進(jìn)入下一層的抽象N這樣，精細(xì)化過程一直進(jìn)行下去，直到程序能被計(jì)算機(jī)接受為止。此時(shí)的程序可能是用某種高級語言或及其指令書寫的我們對付復(fù)雜問題的最重要的辦法是抽象。所以對于一個(gè)復(fù)雜問題，不應(yīng)馬上用計(jì)算機(jī)指令、數(shù)字與邏輯字來表達(dá)，而應(yīng)該用較為自然的抽象語句來表示，從而得出抽象程序123逐步求精的程序設(shè)計(jì)方法簡介N逐步求精的方法V在編制一個(gè)程序時(shí)，首先考慮程序的整體結(jié)構(gòu)而忽視一些細(xì)節(jié)問題，然后逐步地、一層一層地細(xì)化程序直至用所選的語言完全描述每一個(gè)細(xì)節(jié)，即得到所期望的程序?yàn)橹埂?24例1N編寫一個(gè)程序，打印出前N個(gè)素?cái)?shù)V第一步根據(jù)所提出問題，程序的結(jié)構(gòu)可以寫成PROGRAMEX1OUTPUTVARI,XINTEGERBEGINX1FORI1TONDOBEGINX“下一個(gè)素?cái)?shù)”WRITEXENDEND125例1V第二步對語句“X“下一個(gè)素?cái)?shù)”進(jìn)一步求精PROGRAMEX1OUTPUTVARI,XINTEGERBEGINX1FORI1TONDOBEGINWRITEXENDENDX“下一個(gè)素?cái)?shù)”2REPEATXX1UNTILPRIMPRIM“X是一個(gè)素?cái)?shù)”3126例1REPEATXX1UNTILPRIMPRIM“X是一個(gè)素?cái)?shù)”3K2PRIMTRUEWHILEPRIMANDKX而PLIM1X或者PLIM2X而PLIM12X這樣，對所有滿足KLIM的K，均有PKX130例1N綜上所述，得到求解這個(gè)問題的一個(gè)完整的程序PROGRAMEX1OUTPUTTYPEINDEX1NVARXINTEGERI,K,LIMINDEXPRIMBOOLEANPARRAYINDEXOFINTEGERBEGINP12WRITE2X1LIM1FORI2TONDOBEGINREPEATXX2IFSQRPLIMXTHENLIMLIM1K2PRIMTRUEWHILEPRIMANDKLIMDOBEGINPRIMXMODPK0KK1ENDUNTILPRIMPIXWRITEXENDEND131自頂向下的設(shè)計(jì)、編碼和調(diào)試Q先從該模塊的功能描述出發(fā)，一層層地逐步細(xì)化，直到最后分解、細(xì)化成高級語言語句為止V一個(gè)大而完成的程序設(shè)計(jì)分解細(xì)化成一個(gè)個(gè)程序模塊，每個(gè)模塊一般是幾十行至上百行，框圖只占一頁。程序只有一個(gè)入口、一個(gè)出口，只用了36種基本控制結(jié)構(gòu)，所完成功能較明確獨(dú)立。V這樣，模塊易于閱讀理解，也便于檢查其正確性。V在這種分解中，主程序引用下層模塊或一個(gè)模塊引用再下一層模塊，都通過“子程序調(diào)用”或“空功能”實(shí)現(xiàn)。Q調(diào)試“假模塊”（DUMMYMODULE）（驅(qū)動(dòng)模塊）,存根（SUB）（樁模塊）V上層模塊調(diào)用下層模塊，編一個(gè)很簡單的模塊作為代用132被測模塊測試用例接口局部數(shù)據(jù)結(jié)構(gòu)路徑錯(cuò)誤處理邊界條件驅(qū)動(dòng)模塊樁模塊樁模塊測試結(jié)果驅(qū)動(dòng)模塊DRIVER相當(dāng)于所測模塊的主程序。它接收測試數(shù)據(jù)，把這些數(shù)據(jù)傳送給所測模塊，最后再輸出實(shí)際測試結(jié)果樁模塊STUB用于代替所測模塊調(diào)用的子模塊。樁模塊可以做少量的數(shù)據(jù)操作。目的是為了檢驗(yàn)入口，輸