計(jì)算機(jī)導(dǎo)論-第五章程序設(shè)計(jì)

第五章程序設(shè)計(jì)本章內(nèi)容5.1算法的定義與表示5.2簡(jiǎn)單的排序算法5.3程序設(shè)計(jì)語(yǔ)言簡(jiǎn)介5.4匯編語(yǔ)言5.1算法的定義和表示軟件開(kāi)發(fā)步入工程化階段大型軟件開(kāi)發(fā)一般要經(jīng)歷“規(guī)劃”、“需求分析”、“設(shè)計(jì)”、“編碼”、“測(cè)試”和“運(yùn)行維護(hù)”等階段5.1.1算法的定義正確的“需求分析”對(duì)程序設(shè)計(jì)是至關(guān)重要的“編碼”是對(duì)需求的實(shí)現(xiàn)。在“編碼”過(guò)程中，算法很重要，良好的算法決定了程序的質(zhì)量和性能軟件的開(kāi)發(fā)不僅需要處理大量的關(guān)系復(fù)雜的數(shù)據(jù)，這些數(shù)據(jù)通常都具有一定的結(jié)構(gòu)性。因此，軟件設(shè)計(jì)的實(shí)質(zhì)就是設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)和基于這個(gè)數(shù)據(jù)結(jié)構(gòu)的算法。于是N.沃恩提出了著名公式：

程序=數(shù)據(jù)結(jié)構(gòu)+算法程序設(shè)計(jì)＝程序＋程序設(shè)計(jì)方法學(xué)模塊化將復(fù)雜的算法(或程序)分解成若干個(gè)相對(duì)獨(dú)立、功能單一的模塊，利用這些模塊組合成全局算法(或)程序。自頂向下結(jié)構(gòu)設(shè)計(jì)方法從總體出發(fā)，居高臨下，逐層分解和逐步細(xì)化。結(jié)構(gòu)化程序設(shè)計(jì)方法：逐步求精結(jié)構(gòu)設(shè)計(jì)方法

實(shí)質(zhì)上也是一種自頂向下的設(shè)計(jì)方法。首先拋開(kāi)細(xì)節(jié)設(shè)計(jì)出抽象算法，然后把抽象數(shù)據(jù)和操作逐步具體化，直到可以由計(jì)算機(jī)具體實(shí)現(xiàn)為止。算法的定義：是指解題方案的準(zhǔn)確而完整的描述，也可以說(shuō)它是解決某一特定問(wèn)題的一組有窮規(guī)則的集合。（計(jì)算科學(xué)）可以用計(jì)算機(jī)來(lái)解決一類(lèi)問(wèn)題的程序和步驟算法特征：

有窮性：合理算法應(yīng)在執(zhí)行有限步后結(jié)束如：N!=1*2*3*…*(N-1)*N而式子：sum=1+2+3+…+N+…

不能稱(chēng)為算法，因?yàn)樗鼒?zhí)行有限步后仍不能結(jié)束

確定性：算法的每一步執(zhí)行，其順序和內(nèi)容都必須有確切的規(guī)定，不能模棱兩可

可執(zhí)行性：即算法的所有操作都是能通過(guò)計(jì)算機(jī)程序代碼實(shí)現(xiàn)，即可操作性

0個(gè)或多個(gè)輸入；

1個(gè)或多個(gè)輸出【例1】求解一元二次方程的算法方程a*x*x+b*x+c=0，其中a、b和c是不等于0的實(shí)數(shù)。具體參考步驟如下：p=b*b–4*a*cp≥0?計(jì)算實(shí)根計(jì)算復(fù)根輸出YN結(jié)構(gòu)化算法的屬性：1.僅有一個(gè)入口2.僅有一個(gè)出口3.無(wú)死塊4.無(wú)死循環(huán)塊5.1.2算法的類(lèi)型與結(jié)構(gòu)算法類(lèi)型數(shù)值算法非數(shù)值算法基本結(jié)構(gòu)順序結(jié)構(gòu)分支結(jié)構(gòu)循環(huán)結(jié)構(gòu)結(jié)構(gòu)化算法只能由三種控制結(jié)構(gòu)所構(gòu)成流程圖算法的描述算法自然語(yǔ)言順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)輸語(yǔ)句偽代碼循環(huán)語(yǔ)句賦值語(yǔ)句條件語(yǔ)句入出

算法的描述算法的描述還有計(jì)算機(jī)語(yǔ)言改進(jìn)N-S四種圖框類(lèi)型輸入、輸出框處理框判斷框起止框●N-S結(jié)構(gòu)化流程圖（1973年由美國(guó)學(xué)者I．Nassi和B．Shneiderman提出，N和S是這兩位學(xué)者英文姓名的第一個(gè)字母）程序基本控制結(jié)構(gòu)AB順序分支?ABTFT?AF當(dāng)循環(huán)循環(huán)FT?A直到型例2

給出求1+2+3+4+5的一個(gè)算法．算法1

按照逐一相加的程序進(jìn)行．第一步

計(jì)算1+2，得到3；第二步

將第一步中的運(yùn)算結(jié)果3與3相加，得到6；第三步

將第二步中的運(yùn)算結(jié)果6與4相加，得到10；第四步

將第三步中的運(yùn)算結(jié)果10與5相加，得到15．

自然語(yǔ)言示例算法2可以運(yùn)用公式1+2+…+n=n(n+1)/2直接計(jì)算。第一步取n=5；第二步計(jì)算n(n+1)/2；第三步輸出運(yùn)算結(jié)果。循環(huán)結(jié)構(gòu)例3求1×2×3×4×5。算法2S1T←1；S2I←2；S3T←T×I；S4I←I+1．S5如果I不大于5，重新執(zhí)行

S3、S4、S5；否則算法結(jié)束．I>5NYT←1輸出TI←2T←T×II←I+1開(kāi)始結(jié)束例4求兩個(gè)整數(shù)a和b的最大公約數(shù)——?dú)W幾里得輾轉(zhuǎn)相除法。

問(wèn)題背景與分析分析求出列數(shù)：a，b，r1，r2，…，rn–1，rn，0．這列數(shù)從第三項(xiàng)開(kāi)始，每項(xiàng)都是前兩項(xiàng)相除所得的余數(shù)，余數(shù)為0的前一項(xiàng)rn即是a和b的最大公約數(shù)．這種方法稱(chēng)為“歐幾里得輾轉(zhuǎn)相除法”．求68和32的最大公約數(shù)——?dú)W幾里得輾轉(zhuǎn)相除法。68＝2×32＋432＝8×4＋0求66和23的最大公約數(shù)——?dú)W幾里得輾轉(zhuǎn)相除法。66＝23×2＋2023＝20×1＋320＝3×6＋23＝2×1＋12＝1×2＋0輸出ba←bYN輸入a,br←Mod(a,b)b←rMod(a,b)≠0

流程圖例5用二分法求方程x3

-

x

-1=0在區(qū)間[1,1.5]內(nèi)的一個(gè)近似解（誤差不超過(guò)0.001）。

問(wèn)題背景與分析第一步確定有解區(qū)間[a,b]第二步取[a,b]的中點(diǎn)第三步計(jì)算函數(shù)在中點(diǎn)處的函數(shù)值第四步判斷中點(diǎn)處函數(shù)值是否為0第五步判斷新的有解區(qū)間的長(zhǎng)度是否小于

給定的誤差N輸出x0x0←(a+b)f(x0)=0輸入a,b,cb←x0f(a)f(x0)<0|a–b|<ca←x0f(a)←a3-a-1f(x0)←x03–x0–1YNYYN

流程圖5.2簡(jiǎn)單的排序算法⑴冒泡排序法:⑵選擇排序算法:⑶插入排序算法:5.3程序設(shè)計(jì)語(yǔ)言簡(jiǎn)介計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言的發(fā)展，經(jīng)歷了從機(jī)器語(yǔ)言、匯編語(yǔ)言到高級(jí)語(yǔ)言的歷程。5.3.1機(jī)器語(yǔ)言電子計(jì)算機(jī)所使用的是由“0”和“1”組成的二進(jìn)制數(shù)，二進(jìn)制是計(jì)算機(jī)的語(yǔ)言的基礎(chǔ)。也就是說(shuō)，寫(xiě)出一串串由“0”和“1”組成的指令序列交由計(jì)算機(jī)執(zhí)行，這種語(yǔ)言，就是機(jī)器語(yǔ)言。優(yōu)點(diǎn)：由于使用的是針對(duì)特定型號(hào)計(jì)算機(jī)的語(yǔ)言，故而運(yùn)算效率是所有語(yǔ)言中最高的；缺點(diǎn)：在一臺(tái)計(jì)算機(jī)上執(zhí)行的程序，要想在另一臺(tái)計(jì)算機(jī)上執(zhí)行，必須另編程序，造成了重復(fù)工作。5.3.2匯編語(yǔ)言用一些簡(jiǎn)潔的英文字母、符號(hào)串來(lái)替代一個(gè)特定的指令的二進(jìn)制串，比如，用“ADD”代表加法，“MOV”代表數(shù)據(jù)傳遞等等。缺點(diǎn)：匯編語(yǔ)言同樣十分依賴(lài)于機(jī)器硬件，移植性不好；優(yōu)點(diǎn)：效率仍十分高，針對(duì)計(jì)算機(jī)特定硬件而編制的匯編語(yǔ)言程序，能準(zhǔn)確發(fā)揮計(jì)算機(jī)硬件的功能和特長(zhǎng)，程序精煉而質(zhì)量高，所以至今仍是一種常用而強(qiáng)有力的軟件開(kāi)發(fā)工具。5.3.3高級(jí)語(yǔ)言這種語(yǔ)言接近于數(shù)學(xué)語(yǔ)言或人的自然語(yǔ)言，同時(shí)又不依賴(lài)于計(jì)算機(jī)硬件，編出的程序能在所有機(jī)器上通用。影響較大、使用較普遍的有FORTRAN、ALGOL、COBOL、BASIC、LISP、SNOBOL、PL/1、Pascal、C、PROLOG、Ada、C++、VC、VB、Delphi、JAVA

等。高級(jí)語(yǔ)言的發(fā)展也經(jīng)歷了從早期語(yǔ)言到結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言，從面向過(guò)程到非過(guò)程化程序語(yǔ)言的過(guò)程。相應(yīng)地，軟件的開(kāi)發(fā)也由最初的個(gè)體手工作坊式的封閉式生產(chǎn)，發(fā)展為產(chǎn)業(yè)化、流水線(xiàn)式的工業(yè)化生產(chǎn)。FORTRAN語(yǔ)言FORTRAN是英文FORMULATRANSLATION的縮寫(xiě)，其含義是"公式翻譯"。它是一種分塊并列結(jié)構(gòu)的面向過(guò)程的高級(jí)語(yǔ)言。

FORTRAN語(yǔ)言開(kāi)始是為解決數(shù)學(xué)問(wèn)題和科學(xué)計(jì)算而提出的，多年來(lái)的應(yīng)用表明：由于FORTRAN本身具有標(biāo)準(zhǔn)化程度高，便于程序互換，較易優(yōu)化，計(jì)算速度快；因此這種高級(jí)語(yǔ)言目前己廣泛流行。國(guó)外幾乎所有的計(jì)算機(jī)廠(chǎng)商都能向用戶(hù)提供FORTRAN的編譯程序和應(yīng)用程序的版本。從使用的角度來(lái)看，目前FOBTBAN也不再是專(zhuān)用于科學(xué)計(jì)算(數(shù)值計(jì)算)中進(jìn)行程序編制的語(yǔ)言了。越來(lái)越多的商業(yè)系統(tǒng)、企業(yè)單位也采用FORTRAN語(yǔ)言來(lái)編制商業(yè)和企業(yè)的管理程序。ALGOLALGOL:國(guó)際代數(shù)語(yǔ)言

ALGOL是計(jì)算機(jī)發(fā)展史上首批產(chǎn)生的高級(jí)語(yǔ)言，當(dāng)時(shí)還是晶體管計(jì)算機(jī)流行的時(shí)代，由于ALGOL語(yǔ)句和普通語(yǔ)言表達(dá)式接近，更適于數(shù)值計(jì)算，所以ALGOL多用于科學(xué)計(jì)算機(jī)。

ALGOL這個(gè)名稱(chēng)是算法語(yǔ)言的簡(jiǎn)稱(chēng)，這種語(yǔ)言不是計(jì)算機(jī)制造公司為某種特定機(jī)器設(shè)計(jì)的，而是純粹面向描述計(jì)算過(guò)程的，也就是所謂面向算法描述的。ALGOL是第一個(gè)清晰定義的語(yǔ)言，其語(yǔ)法是用嚴(yán)格公式化的方法說(shuō)明的。ALGOL語(yǔ)言并沒(méi)有被廣泛的使用，但它是許多現(xiàn)代程序語(yǔ)言的概念基礎(chǔ)。COBOL英文縮寫(xiě):COBOL(CommonbusinessOrientedLanguage)解釋:一種適合于商業(yè)及數(shù)據(jù)處理的類(lèi)似英語(yǔ)的程序設(shè)計(jì)語(yǔ)言。這種語(yǔ)言可使商業(yè)數(shù)據(jù)處理過(guò)程精確表達(dá)。

COBOL（面向商業(yè)的通用語(yǔ)言，又稱(chēng)為企業(yè)管理語(yǔ)言、數(shù)據(jù)處理語(yǔ)言等，CommonBusinessOrientedLangauge）是最早的高級(jí)編程語(yǔ)言之一，是世界上第一個(gè)商用語(yǔ)言。BASICBASIC（Beginners‘All-purposeSymbolicInstructionCode，又譯培基），意思就是“初學(xué)者的全方位符式指令代碼”，是一種設(shè)計(jì)給初學(xué)者使用的程序設(shè)計(jì)語(yǔ)言。BASIC是一種直譯式的編程語(yǔ)言，在完成編寫(xiě)后不須經(jīng)由編譯及連結(jié)等手續(xù)即可執(zhí)行，但如果需要單獨(dú)執(zhí)行時(shí)仍然需要將其建立成執(zhí)行檔。

PascalPascal是一種計(jì)算機(jī)通用的高級(jí)程序設(shè)計(jì)語(yǔ)言?；贒OS的語(yǔ)言之一.Pascal語(yǔ)言可以被方便地用于描述各種算法與數(shù)據(jù)結(jié)構(gòu)。是第一個(gè)結(jié)構(gòu)化的編程語(yǔ)言CC語(yǔ)言是一種計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言。它既有高級(jí)語(yǔ)言的特點(diǎn)，又具有匯編語(yǔ)言的特點(diǎn)。它可以作為系統(tǒng)設(shè)計(jì)語(yǔ)言，編寫(xiě)工作系統(tǒng)應(yīng)用程序，也可以作為應(yīng)用程序設(shè)計(jì)語(yǔ)言，編寫(xiě)不依賴(lài)計(jì)算機(jī)硬件的應(yīng)用程序。因此，它的應(yīng)用范圍廣泛。

C語(yǔ)言對(duì)操作系統(tǒng)和系統(tǒng)使用程序以及需要對(duì)硬件進(jìn)行操作的場(chǎng)合，用C語(yǔ)言明顯優(yōu)于其它解釋型高級(jí)語(yǔ)言，一些大型應(yīng)用軟件也是用C語(yǔ)言編寫(xiě)的。

C語(yǔ)言具有繪圖能力強(qiáng)，可移植性，并具備很強(qiáng)的數(shù)據(jù)處理能力，因此適于編寫(xiě)系統(tǒng)軟件，三維，二維圖形和動(dòng)畫(huà)。它是數(shù)值計(jì)算的高級(jí)語(yǔ)言。PROLOGProlog（ProgramminginLogic的縮寫(xiě)）是一種邏輯編程語(yǔ)言。它建立在邏輯學(xué)的理論基礎(chǔ)之上。

最初被運(yùn)用于自然語(yǔ)言等研究領(lǐng)域?，F(xiàn)在它已廣泛的應(yīng)用在人工智能的研究中，它可以用來(lái)建造專(zhuān)家系統(tǒng)、自然語(yǔ)言理解、智能知識(shí)庫(kù)等。同時(shí)它對(duì)一些通常的應(yīng)用程序的編寫(xiě)也很有幫助。使用它能夠比其他的語(yǔ)言更快速地開(kāi)發(fā)程序，因?yàn)樗木幊谭椒ǜ笫鞘褂眠壿嫷恼Z(yǔ)言來(lái)描述程序。

AdaAda是一種表現(xiàn)能力很強(qiáng)的通用程序設(shè)計(jì)語(yǔ)言，它是美國(guó)國(guó)防部為克服軟件開(kāi)發(fā)危機(jī)，耗費(fèi)巨資，歷時(shí)近20年研制成功的。它被譽(yù)為第四代計(jì)算機(jī)語(yǔ)言的成功代表。Ada語(yǔ)言是美國(guó)國(guó)防部指定的唯一的一種可用于軍用系統(tǒng)開(kāi)發(fā)的語(yǔ)言，我國(guó)軍方也將Ada作為軍內(nèi)開(kāi)發(fā)標(biāo)準(zhǔn)（GJB1383《程序設(shè)計(jì)語(yǔ)言Ada》）。

C++C++語(yǔ)言是一種優(yōu)秀的面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言，它在C語(yǔ)言的基礎(chǔ)上發(fā)展而來(lái)，但它比C語(yǔ)言更容易為人們學(xué)習(xí)和掌握。

Delphi由Borland公司推出的Delphi是全新的可視化編程環(huán)境，為我們提供了一種方便、快捷的Windows應(yīng)用程序開(kāi)發(fā)工具。它使用了MicrosoftWindows圖形用戶(hù)界面的許多先進(jìn)特性和設(shè)計(jì)思想;采用了彈性可重復(fù)利用的完整的面向?qū)ο蟪绦蛘Z(yǔ)言(Object-OrientedLanguage)、當(dāng)今世界上最快的編輯器、最為領(lǐng)先的數(shù)據(jù)庫(kù)技術(shù)。對(duì)于廣大的程序開(kāi)發(fā)人員來(lái)講，使用Delphi開(kāi)發(fā)應(yīng)用軟件，無(wú)疑會(huì)大大地提高編程效率，Java跨平臺(tái)、動(dòng)態(tài)的Web、Internet計(jì)算;Java語(yǔ)言是一個(gè)支持網(wǎng)絡(luò)計(jì)算的面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言.J2ME主要應(yīng)用于嵌入式系統(tǒng)開(kāi)發(fā)，如手機(jī)和PDA的編程(小型電子設(shè)備的系統(tǒng))；J2EE主要用于分布式的網(wǎng)絡(luò)程序的開(kāi)發(fā)，如電子商務(wù)網(wǎng)站和ERP系統(tǒng)；J2SE開(kāi)發(fā)桌面應(yīng)用軟件（單機(jī)軟件）。工業(yè)編程語(yǔ)言：

A+|Ada|匯編語(yǔ)言|B|Brainfuck|C|C++|C++/CLI|Cg|COBOL|Eiffel|Erlang|FORTRAN|IronPython|Java|JRuby|Jython|LISP|Lua|Nuva|Oberon|Objective-C|Ocaml|Pascal|Perl|Powerbuilder|Python|QBASIC|R|REXX|Ruby|Self|Smalltalk|SQL|Tcl/Tk|VisualBasic|PHP|Lua|C#|F#|J#|VisualBasic.NET腳本編程語(yǔ)言：

ActionScript|JavaScript|JScript|Nuva|PostScript|VBScript|lua

學(xué)術(shù)編程語(yǔ)言：

APL/J|Haskell|Logo|ML|Prolog|Scheme|SAC其他編程語(yǔ)言：

ALGOL|BASIC|Clipper|Forth|Modula-2/Modula-3|MUMPS|PL/I|Simula

高級(jí)語(yǔ)言的下一個(gè)發(fā)展目標(biāo)是面向應(yīng)用，也就是說(shuō)：只需要告訴程序你要干什么，程序就能自動(dòng)生成算法，自動(dòng)進(jìn)行處理，這就是非過(guò)程化的程序語(yǔ)言。5.4匯編語(yǔ)言匯編語(yǔ)言(AssemblyLanguage)是面向機(jī)器的程序設(shè)計(jì)語(yǔ)言.匯編語(yǔ)言是一種功能很強(qiáng)的程序設(shè)計(jì)語(yǔ)言,也是利用計(jì)算機(jī)所有硬件特性并能直接控制硬件的語(yǔ)言。匯編語(yǔ)言”作為一門(mén)語(yǔ)言，對(duì)應(yīng)于高級(jí)語(yǔ)言的編譯器，需要一個(gè)“匯編器”來(lái)把匯編語(yǔ)言原文件匯編成機(jī)器可執(zhí)行的代碼。高級(jí)的匯編器如MASM,TASM等等為我們寫(xiě)匯編程序提供了很多類(lèi)似于高級(jí)語(yǔ)言的特征，比如結(jié)構(gòu)化、抽象等。在這樣的