算法和程序設(shè)計

3.3算法和程序設(shè)計3.3.1

算法3.3.2

程序設(shè)計語言3.3.3程序設(shè)計語言處理器3.3.1算法計算機(jī)求解問題的步驟(1)確定并理解問題；(2)尋找解決問題的方法與步驟，并將其表示成算法(Algorithm)；(3)使用某種程序設(shè)計語言描述該算法(編程),并編譯成目標(biāo)程序和進(jìn)行調(diào)試；(4)運行程序，獲得問題的解答；(5)進(jìn)行評估，改進(jìn)算法和程序1.什么是算法？算法是解決問題的方法與步驟例：有三個硬幣，其中一個是偽造的，另兩個是真的，偽幣與真幣重量略有不同?，F(xiàn)在提供一座天平，如何找出偽幣呢？分析：方法明確而有序按提供的條件進(jìn)行操作任何人均可仿照進(jìn)行(共享智能)開始C是偽幣B是偽幣A是偽幣A＝B？A＝C？是否否是ABC關(guān)于算法的三方面問題如何確定算法（算法設(shè)計）？如何表示算法（算法表示）？如何使算法更有效（算法分析）？2.算法設(shè)計舉例典型問題：如何對數(shù)據(jù)進(jìn)行排序問題：任給一組(n個)整數(shù)，將它們從小到大進(jìn)行排序“選擇排序”算法的思路：①從所有整數(shù)中選一個最小數(shù)，作為已排序的第一個數(shù)②從剩下未排序整數(shù)中選最小的數(shù)，添加到已排序整數(shù)的后面③反復(fù)執(zhí)行步驟②，直到所有整數(shù)都處理完畢“選擇排序”算法舉例2345789第6次循環(huán)后，排序結(jié)束2937845與首元素交換，第1次循環(huán)結(jié)束4937825數(shù)組的初態(tài)，全部是未排序元素4937825在未排序元素中確定最小數(shù)位置2397845與首元素交換，第2次循環(huán)結(jié)束2937845在未排序元素中確定最小數(shù)位置2347895與首元素交換，第3次循環(huán)結(jié)束2397845在未排序元素中確定最小數(shù)位置3.算法的表示文字?jǐn)⑹隽鞒虉D表示偽代碼描述文字(自然語言)描述“比較Ａ與Ｂ的重量，若Ａ＝Ｂ，則Ｃ是偽造的；否則再比較Ａ與Ｃ的重量，若Ａ＝Ｃ，則Ｂ是偽造的；否則Ａ是偽造的。”缺點：容易產(chǎn)生歧義，很難“精確”地進(jìn)行表達(dá)敘述冗長，很難清楚地表達(dá)算法的邏輯流程算法的流程圖表示流程圖由結(jié)點和有向邊構(gòu)成，它描述了算法所執(zhí)行操作的順序及執(zhí)行操作的條件流程圖符號：比文字描述簡明，但當(dāng)算法比較復(fù)雜時，理解困難，容易產(chǎn)生錯誤端點符處理判斷預(yù)定義功能原始數(shù)據(jù)放在數(shù)組A中；令i=1確定A[i]到A[n]中最小整數(shù)的位置,設(shè)為jA[i]和A[j]交換位置i=i+1i=n?結(jié)束開始用流程圖表示選擇排序算法將原始數(shù)據(jù)放在數(shù)組A中；設(shè)置i的初值為1，循環(huán)執(zhí)行下列操作，直到i=n：{確定A[i]到A[n]中最小整數(shù)的位置，設(shè)為j；交換A[i]和[j]；i=i+1}使用偽代碼描述“選擇排序”算法使用偽代碼描述算法偽代碼(Pseudocode)是用來描述算法的一種語言，它既類似于自然語言，又使用與程序設(shè)計語言相似的方法描述算法優(yōu)點：結(jié)構(gòu)清晰，代碼簡單，可讀性好，可以容易地以任何一種編程語言(Pascal,C,Java等)實現(xiàn)每個整數(shù)是A的一個元素：A[1],A[2],···,A[n]4.算法的分析算法分析的基本內(nèi)容正確性：給定有效輸入后，經(jīng)過有限時間的計算，產(chǎn)生正確的輸出結(jié)果簡單性算法是否容易理解，是否容易驗證其正確性，程序是否容易調(diào)試簡單的算法效率不一定高，要在保證一定效率的前提下力求算法簡單時間復(fù)雜性(TimeComplexity)

：當(dāng)問題的規(guī)模n充分大時，運行該算法所需要的時間的數(shù)量級表示空間復(fù)雜性(SpaceComplexity)：除原始數(shù)據(jù)之外，額外占用的存儲空間的大小選講：

選擇排序算法的時間復(fù)雜性假設(shè)參加排序的整數(shù)有n個（1）比較操作的次數(shù)： 在第i趟排序中選出最小整數(shù)時，需做n-i次比較操作， 因此，總的比較操作次數(shù)為：n(n-1)/2=(n2-n)/2（2）移動操作的次數(shù)： 最好情況(原始數(shù)據(jù)已經(jīng)排序)時，移動次數(shù)為0

最壞情況(原始數(shù)據(jù)逆序排列)時，每趟均要執(zhí)行交換操作(3次傳送)，總的移動次數(shù)取最大值為：3(n-1)所以，直接選擇排序的時間復(fù)雜性為O(n2)設(shè)置i的初值為1，循環(huán)執(zhí)行下列操作，直到I=n：{確定A[i]到A[n]中最小的整數(shù)元素的位置，設(shè)為j；交換A[i]和[j]；i=i+1}關(guān)于算法的小結(jié)計算機(jī)中處處是算法！例1：Word程序如何在文檔中查找用戶指定的詞語？例2：在Word文檔的表格中如何將表格內(nèi)容排序？例3：如何把一幅彩色圖片轉(zhuǎn)換為灰度(黑白)圖片？例4：Windows如何在硬盤中找到用戶指定的文件？例5：媒體播放器如何把MP3文件轉(zhuǎn)換成動聽的音樂？例6：搜索引擎如何在WWW網(wǎng)中找到用戶需要的網(wǎng)頁？算法是計算機(jī)軟件的靈魂計算機(jī)的通用性是因為它能運行各種各樣的程序，而程序之所以能解決問題，是因為它所體現(xiàn)了正確的算法 算法所解決的是一類問題而不是一個特定的問題，例如排序(sort)可以是表格內(nèi)容的排序，也可以是文件夾中文件的排序，可以按數(shù)字或文字排序，也可以按日期排序，等等查找(search)，可以在文檔中查找某個單詞或在硬盤中查找某個文件，也可在Web上查找某個網(wǎng)頁，等等開發(fā)計算機(jī)應(yīng)用的核心是：根據(jù)實際問題給出解題的算法，然后再將該算法在計算機(jī)上實現(xiàn)(即開發(fā)成為軟件)計算機(jī)算法的4個特點目的：完成某個特定的信息處理任務(wù)必須滿足的性質(zhì)：①確定性：算法中每一步操作的含義必須清楚明確，無二義性②能行性：算法中有待實現(xiàn)的操作都是計算機(jī)可執(zhí)行的，即必須在計算機(jī)的能力范圍之內(nèi)③有窮性：算法在執(zhí)行了有限步操作后必須結(jié)束④算法結(jié)束后至少產(chǎn)生一個輸出（包括參量或狀態(tài)的變化）3.3.2程序設(shè)計語言機(jī)器語言匯編語言高級程序設(shè)計語言什么是程序設(shè)計語言？什么是程序？程序是為了用計算機(jī)解決某個問題而采用程序設(shè)計語言編寫的一個指令序列什么是程序設(shè)計語言？語言的目的是用于通信程序設(shè)計語言用于人與計算機(jī)之間的通信程序設(shè)計語言是由人使用但計算機(jī)可以理解的一種語言程序設(shè)計語言用于編制程序，表達(dá)需要計算機(jī)完成什么任務(wù)和怎樣完成任務(wù)，然后交給計算機(jī)去完成程序設(shè)計語言填補了

人與計算機(jī)交流的鴻溝計算機(jī)硬件僅僅知道0和1有問題需要計算機(jī)解決的人交流的鴻溝計算機(jī)硬件僅僅知道0和1有問題需要計算機(jī)解決的人程序設(shè)計語言計算機(jī)中使用多種“語言”程序設(shè)計語言：主要用于描述算法機(jī)器語言、匯編語言、高級語言數(shù)據(jù)描述語言：主要用于描述數(shù)據(jù)（文檔、音樂、圖形、圖像、視頻等）的規(guī)范、結(jié)構(gòu)和文件格式HTML、XML、MIDI、MP3、OpenGL、JPEG、MPEG、······腳本語言：用于編寫嵌入在文檔中的程序的程序設(shè)計語言VBA、VBScript、JavaScript計算機(jī)通信語言（通信協(xié)議）：用于描述計算機(jī)-計算機(jī)之間的會話（請求-應(yīng)答）的語法和語義HTTP、POP3、SMTP、FTP、Telnet、TCP、IP、······數(shù)據(jù)庫語言：用于數(shù)據(jù)操作，如SQL語言······B87F01BB210203D8B81F042BC3（計算1055-(383+545)的5條機(jī)器指令）機(jī)器語言

機(jī)器語言就是計算機(jī)的指令系統(tǒng)指令是使用二進(jìn)制編碼表示的用機(jī)器語言編程序,也就是直接使用二進(jìn)制代碼編寫程序優(yōu)點：可以直接被計算機(jī)執(zhí)行缺點：記不住、難理解、效率低、不易維護(hù)不同的機(jī)器語言程序，相互不兼容現(xiàn)在已不直接用機(jī)器語言編制程序！操作碼操作數(shù)(或操作數(shù)的地址)1條機(jī)器指令操作數(shù)地址操作碼例：機(jī)器語言程序在MIPS計算機(jī)上求最大公約數(shù)（GCD）的機(jī)器程序（16進(jìn)制表示）MISP計算機(jī)的每條機(jī)器指令均為32個二進(jìn)位，用8個16進(jìn)制數(shù)表示匯編語言用助記符號來表示機(jī)器指令中的操作符與操作數(shù)優(yōu)點：操作數(shù)直接使用十進(jìn)制程序相對容易理解缺點：大型程序難以開發(fā)依賴于具體計算機(jī)將383傳送到AX寄存器將545傳送到BX寄存器將BX內(nèi)容加AX內(nèi)容，結(jié)果在BX中將1055傳送到AX寄存器將AX內(nèi)容減BX內(nèi)容，結(jié)果在AX寄存器中B87F01BB210203D8B81F042BC3（計算1055-(383+545)的5條機(jī)器指令）機(jī)器語言程序?qū)?yīng)的匯編語言程序MOVAX383MOVBX545ADDBXAXMOVAX1055SUBAXBX匯編語言程序高級程序設(shè)計語言目的：克服匯編語言的缺陷，提高編程和維護(hù)的效率特點：接近人們?nèi)粘Ｊ褂玫淖匀徽Z言（主要是英語）容易理解、記憶和使用可在不同計算機(jī)上通用對使用的符號、詞匯、語法和語義等各種語言成分都有嚴(yán)格的規(guī)定意義：使程序設(shè)計的難度降低，導(dǎo)致了計算機(jī)的發(fā)展進(jìn)入新的階段MOVAX383MOVBX545ADDBXAXMOVAX1055SUBAXBX匯編語言程序S=1055-(383+545)選擇排序的C語言程序voidsort(intA[],intn)/*sort函數(shù)有2個參數(shù):整型數(shù)組A和數(shù)組元素個數(shù)n*/{inti,j,t,k;/*定義4個整型變量*/for(i=0;i<n-1;i++){/*重復(fù)執(zhí)行n-1次，每次增加1個已排序的數(shù)*/

j=i;for(k=i+1;k<n;k++)if(A[k]<A[j])j=k;/*在未排序整數(shù)中確定最小數(shù)的位置*/

t=A[i];A[i]=A[j];A[j]=t;/*把未排序數(shù)中的最小數(shù)交換到未排序數(shù)的首位*/}}數(shù)據(jù)成份運算成份控制成份傳輸成份高級程序設(shè)計語言的發(fā)展50年代：Fortran，ALGOL60年代：COBOL語言，BASIC語言70年代：Pascal語言，C語言80年代：Ada語言，PROLOG語言，LISP語言90年代起：面向?qū)ο笳Z言C++、JAVA、C#等FORTRAN語言FORTRAN是FORmula

TRANslation

（公式翻譯）的縮寫詞，它是一種主要用于數(shù)值計算的面向過程的程序設(shè)計語言。FORTRAN語言的特點是接近數(shù)學(xué)公式，簡單易用目前最新的國際標(biāo)準(zhǔn)是FORTRAN2008BASIC和VisualBasic語言BASIC語言的特點是簡單易學(xué)VisualBASIC(VB)語言是微軟公司基于BASIC發(fā)展而來的一種程序設(shè)計語言，特點是：是一種可視化的、面向?qū)ο蟮?、采用事件?qū)動方式的結(jié)構(gòu)化高級程序設(shè)計語言具有高效率、簡單易學(xué)及功能強(qiáng)大的特點可以高效、快速地開發(fā)Windows環(huán)境下功能強(qiáng)大、圖形界面豐富的應(yīng)用軟件資料：VBA和VBScriptVBA（VisualBasicforApplication）VB的子集，包含在Office軟件（如Word、Excel、Access、PowerPoint）中用途：擴(kuò)展Office軟件的功能特點：寄生于已有的應(yīng)用程序（如Word），不需要另外的開發(fā)環(huán)境，也不能生成.exe文件，所開發(fā)出來的程序（稱為“宏”）必須由它的宿主程序調(diào)用才能運行VBScript語言也是VB的子集，嵌入在HTML文檔中使用所編寫的腳本程序可以擴(kuò)充網(wǎng)頁的功能，例如：動態(tài)修改網(wǎng)頁的內(nèi)容和控制文檔的展現(xiàn)檢驗用戶的輸入信息是否正確等Java語言由SUNMicrosystem公司于1995年發(fā)布的一種面向?qū)ο蟮?、用于網(wǎng)絡(luò)環(huán)境的程序設(shè)計語言基本特征：適用于網(wǎng)絡(luò)分布環(huán)境具有一定的平臺獨立性安全性和穩(wěn)定性好應(yīng)用舉例： 從網(wǎng)絡(luò)下載到瀏覽器中運行的跨平臺小程序JavaappletsAndroid手機(jī)中運行的應(yīng)用程序大多是Java程序C語言和C++語言C語言是1972～1973年間由AT＆T公司Bell實驗室開發(fā)而成C語言兼有高級語言的優(yōu)點和匯編語言的效率，有效地處理了簡潔性和實用性、可移植性和高效性之間的矛盾C++語言以C語言為基礎(chǔ)發(fā)展而成，既有數(shù)據(jù)抽象和面向?qū)ο竽芰Γ\行性能高，又能與C語言兼容，因而C++語言迅速流行，成為當(dāng)前面向?qū)ο蟪绦蛟O(shè)計的主流語言iOS操作系統(tǒng)運行的應(yīng)用程序大多是C++編寫的程序3.3.3程序設(shè)計語言

處理系統(tǒng)程序設(shè)計語言的翻譯程序把甲語言編寫的程序翻譯為等價的乙語言編寫的程序。其中甲語言程序稱為源程序，乙語言程序稱為目標(biāo)程序翻譯程序源程序目標(biāo)程序常用的有下列幾種：匯編程序(匯編器)匯編語言源程序機(jī)器語言目標(biāo)程序編譯程序(編譯器)高級語言源程序機(jī)器語言或匯編語言目標(biāo)程序解釋程序(解釋器)高級語言源程序邊解釋邊執(zhí)行，不產(chǎn)生目標(biāo)程序編譯程序與解釋程序的區(qū)別解釋：解釋器直接解釋并且執(zhí)行源語言程序，不產(chǎn)生目標(biāo)程序（相當(dāng)于“口譯”）編譯：把源程序編譯為機(jī)器語言目標(biāo)程序后，再由計算機(jī)運行（相當(dāng)于“筆譯”）源程序目標(biāo)程序編譯器計算機(jī)編譯方式