大學(xué)計算機基礎(chǔ)PPT第6章.pptx

第六章 程序設(shè)計基礎(chǔ),主要內(nèi)容,計算機程序與程序設(shè)計,計算機程序是指示計算機如何去解決某個問題或完成某項任務(wù)的一組指令。,【實例1】計算給定半徑的圓面積。,其計算步驟可以如下編排： (1)說明在計算過程中要用到的常量和變量； (2)給定圓半徑； (3)計算圓面積； (4)將結(jié)果輸出到屏幕上。,概 念,#define PI 3.1415926 /* 定義符號常量 */ void main() /* 定義主函數(shù) */ /* 開始 */ float r, circle_area; /* 定義變量r和circle_area */ scanf(“%f“, /* 輸出圓面積 */ /* 結(jié)束 */,用C語言編寫的求圓面積的程序,計算機程序與程序設(shè)計,#define PI 3.1415926 void main() float r, circle_area; scanf(“%f“, ,程序的組成,程序由兩部分組成：說明部分和執(zhí)行部分。 說明部分主要包括程序名、參數(shù)（常量、變量）及其參數(shù)類型的說明； 執(zhí)行部分是程序的主體，完成具體的計算和處理任務(wù)。,主要內(nèi)容,程序設(shè)計語言,低級語言,機器語言和匯編語言屬于低級語言，是面向機器的語言。,機器語言 機器語言被稱為第一代程序設(shè)計語言。它是由二進制代碼按照一定規(guī)則組成、能被計算機直接識別和執(zhí)行的指令集合。 每一條指令包括兩部分：,操作碼域中的數(shù)據(jù)表明要進行的操作；操作數(shù)域中的數(shù)據(jù)為特定的操作提供具體的數(shù)據(jù)或數(shù)據(jù)存放在內(nèi)存中的地址。,低級語言,【實例2】計算A=15+10 的機器語言程序,10110000 00001111 : 把15放入累加器A中 00101100 00001010 : 10與累加器A的值相加， 結(jié)果仍放入A中 11110100 : 結(jié)束，停機,機器語言,低級語言,機器語言,缺 點,需要記住大量用二進制表示的指令代碼和代碼的含義，難記憶、難理解、難修改、易錯。用機器語言編寫程序是很繁瑣的一件工作，只適合專業(yè)人員使用；依賴于機器，可移植性差，是面向機器的語言。,優(yōu) 點,可以直接被計算機所識別，不需要翻譯，因此占用計算機存儲空間少，執(zhí)行速度快。,低級語言,匯編語言,【實例3】計算A=15+10 的匯編語言程序,MOV A,15 ：把15放入累加器A中 ADD A,10 ：10與累加器A中的值相加， 結(jié)果仍然放在A中 HLT ：結(jié)束，停機,匯編語言或符號語言被稱為第二代程序設(shè)計語言。它是將機器語言符號化，即用英文助記符來代替機器語言中的指令和數(shù)據(jù), 比用機器語言編寫的程序簡單，容易理解和掌握。,低級語言,匯編語言,缺 點,仍然是面向機器的，可維護性和可移植性差；要求編程者熟悉計算機的硬件結(jié)構(gòu)及其原理，這對大量的非計算機專業(yè)人員是很難做到的。,優(yōu) 點,克服了機器語言難讀、難理解等缺點，保持了機器語言占用存儲空間少，執(zhí)行速度快的優(yōu)點。常用于過程控制等編程。,用匯編語言編寫的程序必須通過“匯編程序”的加工和翻譯，才能生存能夠被計算機識別和處理的二進制代碼程序。,高級語言,高級語言被稱為第三代程序設(shè)計語言，它與機器獨立。 1954年，世界上誕生了第一種高級語言，即用于科學(xué)計算的FORTRAN語言。,機器語言,匯編語言,高級語言,高級語言,高級語言,它是傳統(tǒng)的程序設(shè)計語言，其目的在于高效地實現(xiàn)各種算法，需要詳細描述“怎樣做”。常見的面向過程語言有FORTRAN、BASIC、C、 PASCAL等。 用高級語言編程時的主要工作是圍繞著設(shè)計解題過程來進行的，程序設(shè)計基本上還是從語句一級開始，需要詳細描述解題的過程和細節(jié)。編程時，程序不僅要說明做什么，還要告訴計算機如何做，程序需要詳細描述解題的過程和細節(jié)。,面向過程的語言,面向過程面向過程,高級語言,面向?qū)ο笳Z言是20世紀80年代推出的。它能夠更好地描述客觀事物及其相互聯(lián)系，能夠比較直接地反映客觀世界的本來面目。 面向?qū)ο笳Z言將客觀事物看作具有屬性和行為的對象，通過抽象找出同類對象的共同屬性和行為，形成類。通過類的繼承與多態(tài)可以很方便地實現(xiàn)代碼重用，從而大大提高了程序的復(fù)用能力和程序開發(fā)效率。面向?qū)ο蟮恼Z言有C+、Java、Visual Basic等。,面向?qū)ο蟮某绦蛟O(shè)計語言,面向?qū)ο竺嫦驅(qū)ο?編譯與解釋,用高級語言編寫的程序稱為源程序，計算機不能直接識別和執(zhí)行源程序。在執(zhí)行源程序前需要通過翻譯成機器語言形式的目標程序，這種“翻譯”通常有兩種方式，即編譯方式和解釋方式。,編譯方式是用“編譯程序”將源程序翻譯成與之等價的用機器語言表示的目標程序。 如果編譯過程中發(fā)現(xiàn)程序有錯，計算機系統(tǒng)會給出相應(yīng)的提示，這時必須修改程序并重新編譯，直到程序編譯正確為止。 當程序編譯正確后，將產(chǎn)生一個目標程序。,編譯與解釋,編譯與解釋,解釋方式的翻譯工作由解釋器來完成。 當運行使用解釋語言編寫的程序時，解釋器會讀一條語句，然后對其進行分析，若沒有錯誤，則將該語句翻譯成一條或多條可執(zhí)行的機器語言指令，執(zhí)行完該指令后解釋器再讀入下一條語句并解釋成機器指令；若解釋時發(fā)現(xiàn)錯誤，便會立即停止，報錯并提醒用戶修改程序。如此繼續(xù)，整個過程不產(chǎn)生目標程序。,編譯與解釋,編譯把源程序的執(zhí)行過程分為兩個階段：編譯階段和運行階段，即先把源程序全部翻譯成目標代碼，然后再運行此目標代碼，得到執(zhí)行結(jié)果。解釋卻把兩個階段合并成一個階段，稱為解釋執(zhí)行階段，即按照源程序中語句的動態(tài)順序，直接地逐句進行分析解釋，并立即執(zhí)行，直至源程序結(jié)束。 經(jīng)編譯得到的目標程序，可以脫離編譯程序獨立運行；被解釋的程序卻不能脫離解釋環(huán)境執(zhí)行。,常用程序設(shè)計語言,FORTRAN語言 COBOL 語言 BASIC 語言 PASCAL 語言 C 語 言,C+ 語 言 LISP 語 言 PROLOG語言 JAVA 語言,高級程序設(shè)計語言的特征,高級語言的數(shù)據(jù)類型一般分為基本數(shù)據(jù)類型和構(gòu)造數(shù)據(jù)類型兩大類。 基本數(shù)據(jù)類型：整數(shù)類型、實數(shù)類型、字符類型、邏輯類型、指針類型等。 構(gòu)造數(shù)據(jù)類型：數(shù)組類型、枚舉類型、記錄類型（結(jié)構(gòu)類型）、文件等。,高級程序設(shè)計語言的特征,把表示數(shù)值的名字稱為標識符。 常量：以不變的數(shù)值形式出現(xiàn)的量，僅標識一個固定數(shù)據(jù)值的名字稱為常量標識符。 變量：程序執(zhí)行過程中可能發(fā)生變化的對象用一個名字給以標識，對該名字的處理，可以是對該名字標識的任何一個數(shù)據(jù)值進行處理，該名字稱為變量。例如，計算的數(shù)據(jù)對象和計算結(jié)果對象在程序中可以用變量表示。變量具有作用域，它取決于該變量的實際使用范圍。 標識符的構(gòu)成規(guī)則：第一個字符必須是字母，其他字符可以是字母、數(shù)字或下劃線等。,高級程序設(shè)計語言的特征,程序中對數(shù)據(jù)進行處理是通過運算符實現(xiàn)的。 不同的程序設(shè)計語言提供的運算符種類不同，表示形式也可能不同，通常有如下幾類運算： 算術(shù)運算符：加、減、乘、除、乘方等。 關(guān)系運算符：大于、大于等于、小于、小于等于、相等、不相等。 邏輯運算符：與、或、非等。 字符運算符：連接、比較、取子串等。 賦值運算符 ：,高級程序設(shè)計語言的特征,表達式是程序中進行計算并取值的基本單位，它由常量、變量、函數(shù)調(diào)用和運算符組成。通常表達式由若干個運算符把一些運算對象連接在一起。 例如，已知圓半徑r，求圓面積的C語句如下： 其中，PI*r*r就是一個表達式，r和s都是變量，PI是符號常量。是賦值運算符。,s=PI*r*r;,高級程序設(shè)計語言的特征,語句是程序中具有獨立含義的基本單位，通常分為說明性語句和執(zhí)行性語句。 說明性語句用來說明程序中被處理對象的標識符名及其類型，在某些語言（如C語言）中還用于說明對象的存儲類型，即對象的作用域。 執(zhí)行性語句由程序設(shè)計語言所提供的語句組成，是可以執(zhí)行的。,高級程序設(shè)計語言的特征,高級語言引入過程或函數(shù)的目的是把一個復(fù)雜程序分解為若干個功能單一的子程序(過程或函數(shù))。 當程序中要進行多次重復(fù)計算時，可以把重復(fù)部分定義成一個子程序(過程或函數(shù))，當程序中需要進行該計算時，就調(diào)用該子程序(過程或函數(shù))。,實 例,高級程序設(shè)計語言的特征,有一個任務(wù)要將一個班的學(xué)生成績按平均成績降序輸出。算法描述： 輸入一個班學(xué)生的各門課程成績； 計算每個學(xué)生的平均成績； 將平均成績按降序排列； 輸出排序結(jié)果。,按功能將該任務(wù)分解成4個子任務(wù)，即 輸入子任務(wù)； 計算平均成績子任務(wù)； 降序排序子任務(wù)； 輸出子任務(wù)。,高級程序設(shè)計語言的特征,按功能將該任務(wù)分解成4個子任務(wù)，即 輸入子任務(wù)； 計算平均成績子任務(wù)； 降序排序子任務(wù)； 輸出子任務(wù)。,一個子任務(wù)對應(yīng)一個過程或函數(shù)。按這種方法編寫程序，便于多人合作，降低了程序的復(fù)雜度，程序結(jié)構(gòu)更加清晰。 在高級語言系統(tǒng)的函數(shù)庫中，通常為用戶提供了大量的可直接調(diào)用標準函數(shù)。例如，數(shù)學(xué)函數(shù)，字符串處理函數(shù)，類型轉(zhuǎn)換函數(shù)等。,高級程序設(shè)計語言的特征,對象的作用域是指變量使用的有效范圍，它與定義對象的位置和過程的結(jié)構(gòu)有關(guān)。,高級程序設(shè)計語言的特征,每一種高級語言都提供了各自的輸入/輸出語句或輸入/輸出函數(shù)。通常，輸入/輸出都有兩種方式。 人機交互方式：例如從鍵盤上的輸入，通常是少量的數(shù)據(jù)輸入。 文件方式：當數(shù)據(jù)量較大時，通常將數(shù)據(jù)事先存放到一個數(shù)據(jù)文件中，需要時在程序中打開該數(shù)據(jù)文件，從文件中讀出數(shù)據(jù)。,處理,主要內(nèi)容,程序設(shè)計過程及方法,程序設(shè)計基本過程,問題建模,編譯調(diào)試,設(shè)計,編寫代碼,程序設(shè)計過程及方法,執(zhí)行程序的一般過程,程序設(shè)計過程及方法,程序設(shè)計過程及方法,分類一,程序設(shè)計過程及方法,分類二,原則：在軟件設(shè)計和實現(xiàn)過程中，采用自頂向下、逐步求精、模塊化。 程序設(shè)計模式：“數(shù)據(jù)結(jié)構(gòu)算法” 基本結(jié)構(gòu)：順序、選擇、循環(huán)三種基本控制結(jié)構(gòu)，避免使用GOTO語句。,順序結(jié)構(gòu),選擇結(jié)構(gòu),程序設(shè)計過程及方法,循環(huán)結(jié)構(gòu),程序設(shè)計過程及方法,面向?qū)ο蠓椒ň哂信c人類習(xí)慣的思維方法一致，穩(wěn)定性好，可重用性好，可維護性好，易于開發(fā)大型軟件。 面向?qū)ο蠓椒ê图夹g(shù)將問題分解為對象，以對象為核心。對象是由數(shù)據(jù)和容許的操作組成的封裝體。對象之間通過傳遞消息互相聯(lián)系。 程序設(shè)計模式：“對象消息”,程序設(shè)計過程及方法,對 象（Object）,程序設(shè)計過程及方法,系統(tǒng)中用來描述客觀事物的一個實體，是構(gòu)成系統(tǒng)的一個基本單位，它由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。 例如，一輛汽車是一個對象，它包含了汽車的屬性(如顏色、型號、載重量等)及其操作(如啟動、剎車等)。,類（Class）和 實例（Instance）,程序設(shè)計過程及方法,類是具有相同類型對象的抽象，它描述了屬于該對象類型的所有對象的性質(zhì)，而一個對象則是其對應(yīng)類的一個實例。 人是一個類，而每一個具體的人則是這個類中的一個對象，一個名為李敏的人就是這個類中的一個具體的對象，即實例。,封 裝,封裝是一種信息隱蔽技術(shù)，它使數(shù)據(jù)和加工該數(shù)據(jù)的方法(函數(shù))封裝為一個整體。 封裝的目的在于把對象的設(shè)計者和對象的使用者分開，使用者不必知曉行為實現(xiàn)的細節(jié)，只須用設(shè)計者提供的消息來訪問該對象。,繼 承 性（Inheritance）,程序設(shè)計過程及方法,繼承性是子類自動共享父類之間數(shù)據(jù)和方法的機制,它由類的派生功能體現(xiàn),是一種聯(lián)結(jié)類與類的層次模型。 一個新類可以從現(xiàn)有類中派生，這個過程稱為類繼承。新類繼承了原來類的特性，稱為原來類的派生類(子類)，原來類稱為新類的基類(父類)。 繼承可以使得子類具有父類的各種屬性和方法，而不需要再次編寫相同的代碼。 繼承具有傳遞性，如果類C繼承類B，類B繼承類A，則類C繼承類A。 繼承分為單繼承(一個子類只有一父類)和多重繼承(一個類有多個父類)。,多 態(tài) 性（Polymorphism）,程序設(shè)計過程及方法,多態(tài)性是指對于不同數(shù)據(jù)類型的相似操作使用相同的命名。多態(tài)是指不同事物具有不同表現(xiàn)形式的能力。,消 息（Message）,一個對象向另一個對象發(fā)出的請求被稱為“消息”。當對象接收到發(fā)給它的消息時，就調(diào)用有關(guān)的方法，執(zhí)行相應(yīng)的操作。面向?qū)ο蟪绦蛟O(shè)計技術(shù)中必須提供一種機制允許一個對象與另一個對象的交互，這種機制叫消息傳遞。,主要內(nèi)容,算法基礎(chǔ),算法與數(shù)據(jù)結(jié)構(gòu)是計算機程序的兩大基礎(chǔ)。 數(shù)據(jù)結(jié)構(gòu)是為了研究數(shù)據(jù)運算而存在的，它直接影響計算機進行數(shù)據(jù)處理的效率； 算法是為了實現(xiàn)數(shù)據(jù)運算，算法的好壞也直接影響計算機的效率。,算法+數(shù)據(jù)結(jié)構(gòu)=程序,算法+數(shù)據(jù)結(jié)構(gòu)=程序,算法+數(shù)據(jù)結(jié)構(gòu)=程序,算法+數(shù)據(jù)結(jié)構(gòu)=程序,算法+數(shù)據(jù)結(jié)構(gòu)=程序,算法基礎(chǔ),算法特性,算法基礎(chǔ),算法要求,算法基礎(chǔ),算法基礎(chǔ),自然語言：用人們使用的語言描述算法。,【實例5】求任意三個正整數(shù)a、b、c中的最大者。,用自然語言描述的算法如下： 輸入a，b，c； a和b比較，若ab則max=a，否則max=b； c和max比較，若cmax，則max=c; 輸出max。,算法基礎(chǔ),流程圖：用圖形來表示算法。,算法基礎(chǔ),流程圖：用圖形來表示算法。,【實例5】求任意三個正整 數(shù)a、b、c中的最大者。,算法基礎(chǔ),N-S結(jié)構(gòu)流程圖：去掉了傳統(tǒng)流程圖中帶箭頭的線，全部算法以一個大的矩形框表示，框內(nèi)還可以包含一些從屬于它的小矩形框，適于結(jié)構(gòu)化程序設(shè)計。,算法基礎(chǔ),N-S結(jié)構(gòu)流程圖：,【實例5】求任意三個正整數(shù)a、b、c中的最大者。,算法基礎(chǔ),偽代碼：Pseudo-code又稱PDL語言，是用介于自然語言和計算機語言之間的文字和符號來描述算法。偽代碼不能被計算機所理解，但接近于某種語言編寫的程序，便于轉(zhuǎn)換成編程語言。,read a, b, c if ab a=max else b=max if cmax c=max print max,【實例5】求任意三個正整 數(shù)a、b、c中的最大者。,算法基礎(chǔ),依題目的部分條件確定答案的大致范圍，在此范圍內(nèi)對所有可能的情況逐一驗證，直到全部情況驗證完。 若某個情況經(jīng)驗證符合題目的全部條件，則為本題的一個答案。 若全部情況經(jīng)驗證后都不符合題目的全部條件，則本題無答案。,列舉法,算法基礎(chǔ),【實例6】百錢買百雞。雞翁一，值錢五；雞母一，值錢三； 雞雛三，值錢一。百錢買百雞，問雞翁、雞母、雞雛各幾何？,假設(shè)雞翁、雞母、雞雛分別為a,b,c只，可得如下兩方程： a+b+c=100 (1)（a的取值范圍為020 ，b為033 ） 5a+3b+c/3=100 (2) 列舉法依次對a,b,c取值范圍內(nèi)的各數(shù)一一試探，找出滿足方程(1)和(2)的組合。,列舉法,算法基礎(chǔ),通過列舉少量特殊情況，經(jīng)過分析，歸納出一般的關(guān)系。 它比列舉法更能反映問題的本質(zhì)，并且可以解決列舉量為無限的問題。,歸納法,算法基礎(chǔ),從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。 遞推的過程就是找出舊值和新值之間的關(guān)系，每次都從舊值推出新值，然后用新值代替舊值。,遞推法,【實例7】猴子吃桃問題。,一只猴子第一天摘下若干個桃子，當即吃了一半