算法和程序設(shè)計(jì)

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

算法3.3.2

程序設(shè)計(jì)語(yǔ)言3.3.3程序設(shè)計(jì)語(yǔ)言處理器3.3.1算法計(jì)算機(jī)求解問(wèn)題的步驟(1)確定并理解問(wèn)題；(2)尋找解決問(wèn)題的方法與步驟，并將其表示成算法(Algorithm)；(3)使用某種程序設(shè)計(jì)語(yǔ)言描述該算法(編程),并編譯成目標(biāo)程序和進(jìn)行調(diào)試；(4)運(yùn)行程序，獲得問(wèn)題的解答；(5)進(jìn)行評(píng)估，改進(jìn)算法和程序1.什么是算法？算法是解決問(wèn)題的方法與步驟例：有三個(gè)硬幣，其中一個(gè)是偽造的，另兩個(gè)是真的，偽幣與真幣重量略有不同?，F(xiàn)在提供一座天平，如何找出偽幣呢？分析：方法明確而有序按提供的條件進(jìn)行操作任何人均可仿照進(jìn)行(共享智能)開始C是偽幣B是偽幣A是偽幣A＝B？A＝C？是否否是ABC關(guān)于算法的三方面問(wèn)題如何確定算法（算法設(shè)計(jì)）？如何表示算法（算法表示）？如何使算法更有效（算法分析）？2.算法設(shè)計(jì)舉例典型問(wèn)題：如何對(duì)數(shù)據(jù)進(jìn)行排序問(wèn)題：任給一組(n個(gè))整數(shù)，將它們從小到大進(jìn)行排序“選擇排序”算法的思路：①?gòu)乃姓麛?shù)中選一個(gè)最小數(shù)，作為已排序的第一個(gè)數(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表示偽代碼描述文字(自然語(yǔ)言)描述“比較Ａ與Ｂ的重量，若Ａ＝Ｂ，則Ｃ是偽造的；否則再比較Ａ與Ｃ的重量，若Ａ＝Ｃ，則Ｂ是偽造的；否則Ａ是偽造的?！比秉c(diǎn)：容易產(chǎn)生歧義，很難“精確”地進(jìn)行表達(dá)敘述冗長(zhǎng)，很難清楚地表達(dá)算法的邏輯流程算法的流程圖表示流程圖由結(jié)點(diǎn)和有向邊構(gòu)成，它描述了算法所執(zhí)行操作的順序及執(zhí)行操作的條件流程圖符號(hào)：比文字描述簡(jiǎn)明，但當(dāng)算法比較復(fù)雜時(shí)，理解困難，容易產(chǎn)生錯(cuò)誤端點(diǎ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)是用來(lái)描述算法的一種語(yǔ)言，它既類似于自然語(yǔ)言，又使用與程序設(shè)計(jì)語(yǔ)言相似的方法描述算法優(yōu)點(diǎn)：結(jié)構(gòu)清晰，代碼簡(jiǎn)單，可讀性好，可以容易地以任何一種編程語(yǔ)言(Pascal,C,Java等)實(shí)現(xiàn)每個(gè)整數(shù)是A的一個(gè)元素：A[1],A[2],···,A[n]4.算法的分析算法分析的基本內(nèi)容正確性：給定有效輸入后，經(jīng)過(guò)有限時(shí)間的計(jì)算，產(chǎn)生正確的輸出結(jié)果簡(jiǎn)單性算法是否容易理解，是否容易驗(yàn)證其正確性，程序是否容易調(diào)試簡(jiǎn)單的算法效率不一定高，要在保證一定效率的前提下力求算法簡(jiǎn)單時(shí)間復(fù)雜性(TimeComplexity)

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

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

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

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

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

TRANslation

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

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