計算機導論-第五章程序設(shè)計

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

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

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

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

不能稱為算法，因為它執(zhí)行有限步后仍不能結(jié)束

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

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

0個或多個輸入；

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

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

給出求1+2+3+4+5的一個算法．算法1

按照逐一相加的程序進行．第一步

計算1+2，得到3；第二步

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

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

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

自然語言示例算法2可以運用公式1+2+…+n=n(n+1)/2直接計算。第一步取n=5；第二步計算n(n+1)/2；第三步輸出運算結(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開始結(jié)束例4求兩個整數(shù)a和b的最大公約數(shù)——歐幾里得輾轉(zhuǎn)相除法。

問題背景與分析分析求出列數(shù)：a，b，r1，r2，…，rn–1，rn，0．這列數(shù)從第三項開始，每項都是前兩項相除所得的余數(shù)，余數(shù)為0的前一項rn即是a和b的最大公約數(shù)．這種方法稱為“歐幾里得輾轉(zhuǎn)相除法”．求68和32的最大公約數(shù)——歐幾里得輾轉(zhuǎn)相除法。68＝2×32＋432＝8×4＋0求66和23的最大公約數(shù)——歐幾里得輾轉(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)的一個近似解（誤差不超過0.001）。

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

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

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

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

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

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

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

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

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

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

最初被運用于自然語言等研究領(lǐng)域。現(xiàn)在它已廣泛的應(yīng)用在人工智能的研究中，它可以用來建造專家系統(tǒng)、自然語言理解、智能知識庫等。同時它對一些通常的應(yīng)用程序的編寫也很有幫助。使用它能夠比其他的語言更快速地開發(fā)程序，因為它的編程方法更象是使用邏輯的語言來描述程序。

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

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

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

A+|Ada|匯編語言|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腳本編程語言：

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

學術(shù)編程語言：

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

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

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