第10章 程序設(shè)計基礎(chǔ)

第十章程序設(shè)計基礎(chǔ)《大學計算機》（第三版）高等教育出版社10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.1程序設(shè)計的概念程序：是解題方法和步驟的描述，是供計算機執(zhí)行并能完成特定功能的指令序列。程序的核心：數(shù)據(jù)結(jié)構(gòu)和算法。程序設(shè)計（Programming）：先對問題進行分析并建立數(shù)學模型，然后考慮數(shù)據(jù)的組織方式和算法，并用某一種程序設(shè)計語言編寫程序，最后調(diào)試程序，使之運行后能產(chǎn)生預(yù)期的結(jié)果。10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.1程序設(shè)計的概念程序設(shè)計的基本步驟：

(1)分析問題，確定數(shù)學模型或方法。

(2)設(shè)計算法，畫出流程圖。

(3)選擇編程工具，按算法編寫程序。

(4)調(diào)試程序，分析輸出結(jié)果。10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.2算法計算機解決問題的方法和步驟，就是計算機解題的算法(Algorithm)。

算法舉例：

（1）將兩個變量的值互換。

（2）歐幾里德（Euclid）算法求兩個正整數(shù)m和n的最大公約數(shù)。（3）非數(shù)值計算算法：有9枚銅幣，其中有1枚略輕的是假幣，用一臺沒有砝碼的天平將假幣找出來，應(yīng)怎樣找稱。10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.2.1算法的概念10.2算法(1)有窮性。算法中執(zhí)行的步驟總是有限次數(shù)的，不能無止境地執(zhí)行下去。

(2)確定性。算法中的每一步操作必須具有確切的含義，不能有二義性。

(3)有效性。算法中的每一步操作必須是可執(zhí)行的。

(4)要有數(shù)據(jù)輸入。算法中操作的對象是數(shù)據(jù)，因此應(yīng)提供有關(guān)數(shù)據(jù)。

(5)要有結(jié)果輸出。10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.2.2算法的特性10.2算法1．算法評價標準（1）正確性。

（2）可讀性。

（3）通用性。

（4）高效率。

2.算法效率的度量

（1）時間度量

（2）空間度量10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.2.3算法的評價10.2算法用傳統(tǒng)的流程圖描述算法傳統(tǒng)的流程圖是用一些幾何框圖、流程線和文字說明表示各種類型的操作。一般用矩形框表示進行某種處理，有一個入口，一個出口。用菱形框表示判斷，有一個入口，兩個出口。在框內(nèi)寫上簡明的文字或符號表示具體的操作，用帶箭頭的流向線表示操作的先后順序。

10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.2.4算法的描述10.2算法2.用結(jié)構(gòu)化流程圖描述算法

（1）程序的三種基本結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。

（2）結(jié)構(gòu)化流程圖（N-S圖）10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.2.4算法的描述10.2算法2.用結(jié)構(gòu)化流程圖描述算法

（1）程序的三種基本結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。

（2）結(jié)構(gòu)化流程圖（N-S圖）10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.2.4算法的描述10.2算法3．用偽代碼描述算法計算2+4+…+100并輸出，設(shè)計算法并用VisualBasic偽代碼描述如下：0→sum1→iDoWhilei≤100Ifi/2的余數(shù)為0THENsum+i→sumi+1→iLoopPrintsum10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.2.4算法的描述10.2算法1．迭代算法迭代是一種建立在循環(huán)基礎(chǔ)上的算法。在數(shù)學中，迭代經(jīng)常被用來進行數(shù)值計算，例如求方程的解，不斷用變量原來的值遞推求新的值的過程。討論求若干個數(shù)之和或乘積的問題。

10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.2.5算法示例10.2算法2．窮舉算法窮舉法也叫枚舉法，它的基本思路是對眾多可能解，按某種順序進行逐一枚舉和檢驗，并從中找出那些符合要求的可能解，作為問題的解。窮舉的計算量是相當大的，但對于計算機來說，做起來很容易。窮舉算法是一種重要的算法設(shè)計策略，可以說是計算機解題的一大特點。求方程x+2y+5z=100的整數(shù)解。10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.2.5算法示例10.2算法3．排序算法

所謂排序，就是將一組數(shù)據(jù)元素按照某個關(guān)鍵字遞增或遞減的次序排列起來。

（1）選擇排序(SelectionSort)

選擇排序法的實現(xiàn)過程是：首先找出表中關(guān)鍵字最小的元素，將其與第一個元素進行交換，然后，再在其余元素中找出關(guān)鍵字最小的元素，將其與第二個元素進行交換。依次類推，直到將表中所有關(guān)鍵字按由小到大的順序排列好為止。10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.2.5算法示例10.2算法（2）冒泡排序(BubbleSort)冒泡法排序法是每趟將相鄰的兩個數(shù)兩兩進行比較，若滿足升序次序，則進行下一次比較，若不滿足升序次序，則交換這兩個數(shù)，直到最后?？偟谋容^次數(shù)為n-1次，此時最后的元素為最大數(shù)，此為一趟排序。接著進行第二趟排序，方法同前，只是這次最后一個元素不再參與比較，比較次數(shù)為n-2次，依次類推。10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.2.5算法示例10.2算法4．查找算法查找是根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素，若表中存在這樣的數(shù)據(jù)元素，稱此查找是成功的。若表中不存在關(guān)鍵字等于給定值的數(shù)據(jù)元素，稱此查找是不成功的。

（1）順序查找

順序查找是最常用的查找方法，其查找過程為：從第一個元素起，逐個將給定值與數(shù)據(jù)元素的關(guān)鍵字進行比較，若某個元素的關(guān)鍵字與給定值相等，則認為查找是成功的，否則，查找失敗。10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.2.5算法示例10.2算法（2）折半查找作為折半查找的表必須是順序存儲的有序表，即表采用順序結(jié)構(gòu)存儲，表中的元素按關(guān)鍵字值遞增（或遞減）排列。

假設(shè)表中的關(guān)鍵字值遞增排列，則折半查找的實現(xiàn)方法是：首先取整個有序表的中間元素Am的關(guān)鍵字同給定值x比較，若相等，則查找成功；否則，若Am的關(guān)鍵字小于x，則說明待查元素只可能落在表的后半部分中，接著只要在表的后半部分子表中查找即可；若Am的關(guān)鍵字大于x，則說明待查元素只可能落在表的前半部分中，接著只要在表的前半部分子表中查找即可。這樣，經(jīng)過一次關(guān)鍵字的比較，就縮小一半的查找空間，重復(fù)進行下去，直到找到關(guān)鍵字為x的元素，或者表中沒有待查元素（此時查找區(qū)間為空）為止。10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.2.5算法示例10.3程序設(shè)計語言10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.3.1程序設(shè)計語言的分類機器語言匯編語言高級語言面向過程面向?qū)ο?0.3程序設(shè)計語言10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.3.1程序設(shè)計語言的分類1．機器語言（Machinelanguage）

機器語言：機器指令的總稱。

特點：繁瑣冗長、不直觀、容易出錯、程序不通用。

2．匯編語言（Assemblylanguage）

用助記符表示的機器指令。

特點：直觀性增強了，但與機器指令一一對應(yīng)。

3．高級語言（Highlevellanguage）

高級語言：接近自然語言和數(shù)學表達式的一種語言。

特點：直觀、通用性，便于推廣交流。

兩種執(zhí)行方式：編譯方式和解釋方式。10.3程序設(shè)計語言10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.3.1程序設(shè)計語言的分類高級語言程序的編譯執(zhí)行過程：編譯程序工作過程:10.3程序設(shè)計語言10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.3.2高級語言的基本特征1．數(shù)據(jù)類型

各種高級語言都提供了豐富的數(shù)據(jù)類型，這些數(shù)據(jù)類型可以分為兩大類：簡單類型和構(gòu)造類型。其中簡單類型一般有整型、實型、字符型、邏輯型、指針類型等，構(gòu)造類型有數(shù)組類型、集合類型、記錄類型、文件類型等。10.3程序設(shè)計語言10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.3.2高級語言的基本特征2．運算與表達式

（1）常量

（2）變量

（3）表達式

3．語句

（1）賦值語句

（2）輸入輸出語句

（3）程序的控制結(jié)構(gòu)語句

4．子程序、函數(shù)與過程

10.3程序設(shè)計語言10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.3.3常用高級語言1.傳統(tǒng)高級語言

（1）FORTRAN語言：FORTRAN66、FORTRAN77、FORTRAN90。

（2）BASIC語言：BASIC、VisualBasic、VisualBasic.NET。

（3）PASCAL語言

（4）C語言：C、C++、C＃。

（5）COBOL語言10.3程序設(shè)計語言10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.3.3常用高級語言2．網(wǎng)絡(luò)編程語言

（1）Java語言

（2）腳本語言（ScriptingLanguage）：JavaScript、VBScript、Perl、PHP。

3．科學計算語言：MATLAB10.3程序設(shè)計語言10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.3.3常用高級語言2．網(wǎng)絡(luò)編程語言

（1）Java語言

（2）腳本語言（ScriptingLanguage）：JavaScript、VBScript、Perl、PHP。

3．科學計算語言：MATLAB討論：如何學習一種高級語言？如何選擇高級語言？10.4程序設(shè)計方法10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.4.1結(jié)構(gòu)化程序設(shè)計結(jié)構(gòu)化程序設(shè)計采用自頂向下、逐步求精和模塊化的分析方法，從而有效地將一個較復(fù)雜的程序系統(tǒng)設(shè)計任務(wù)分解成許多易于控制和處理的子程序，便于開發(fā)和維護。10.4程序設(shè)計方法10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.4.2面向?qū)ο蟪绦蛟O(shè)計(Object-OrientedProgramming,OOP)傳統(tǒng)的程序設(shè)計是基于求解過程來組織程序流程。在這類程序中，數(shù)據(jù)和施加于數(shù)據(jù)的操作是獨立設(shè)計的，以對數(shù)據(jù)進行操作的過程作為程序的主體。面向?qū)ο蟪绦蛟O(shè)計則以對象作為程序的主體。對象是數(shù)據(jù)和操作的“封裝體”，封裝在對象內(nèi)的程序通過“消息”來驅(qū)動運行。在圖形用戶界面上，消息可通過鍵盤或鼠標的某種操作來傳遞。10.4程序設(shè)計方法10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.4.2面向?qū)ο蟪绦蛟O(shè)計(Object-OrientedProgramming,OOP)（1）對象(Object)對象是指現(xiàn)實世界中具體存在的實體。每一個對象都有自己的屬性（包括自己特有的屬性和同類對象的共同屬性）。屬性反映對象自身狀態(tài)變化，表現(xiàn)為當前的屬性值。

方法是用來描述對象動態(tài)特征的一個操作序列。

（2)類(Class)類是具有相同屬性和方法的一組對象的集合，它為屬于該類的全部對象提供了統(tǒng)一的抽象描述。10.4程序設(shè)計方法10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法OPP與OOP比較10.4程序設(shè)計方法10.1程序設(shè)計的概念10.2算法10.3程序設(shè)計語

言10.4程序設(shè)計方

法10.4.3可視化程序設(shè)計讓程序設(shè)計人員利用語言工具本身所提供的各種控件，像搭積木式地構(gòu)造應(yīng)用程序的各種界面，使得整個界面設(shè)計是在“所見即所得”的可視化狀態(tài)下完成。相對于編寫代碼方式的程序設(shè)計而言的，可視化程序設(shè)計具有直觀形象、方便高效等優(yōu)點。10.