計算機(jī)導(dǎo)論-問題求解與程序設(shè)計

程序設(shè)計程序設(shè)計在計算機(jī)系統(tǒng)的位置問題求解與程序設(shè)計本章討論的主要問題是：

1.什么是程序？什么是程序設(shè)計？什么是程序設(shè)計語言？

2.程序是怎么設(shè)計出來的？程序設(shè)計的關(guān)鍵是什么？

3.計算機(jī)運行程序的過程就是對數(shù)據(jù)的加工處理過程，如何將數(shù)據(jù)存儲到計算機(jī)的內(nèi)存中？如何描述問題的處理方法和具體步驟才能讓計算機(jī)“看懂”呢？

4.為了方便編寫程序，現(xiàn)代程序設(shè)計普遍采用高級程序設(shè)計語言，高級語言程序如何轉(zhuǎn)換為等價的機(jī)器指令？情景問題——七橋問題

【問題】17世紀(jì)的東普魯士有一座哥尼斯堡城（現(xiàn)在叫加里寧格勒，在波羅的海南岸），城中有一座島，普雷格爾河的兩條支流環(huán)繞其旁，并將整個城市分成北區(qū)、東區(qū)、南區(qū)和島區(qū)4個區(qū)域，全城共有七座橋?qū)?個城區(qū)連接起來，于是，產(chǎn)生了一個有趣的問題：一個人是否能在一次步行中穿越全部的七座橋后回到起點，且每座橋只經(jīng)過一次。情景問題——七橋問題

東區(qū)北區(qū)島區(qū)南區(qū)CADB

抽象【想法——抽象模型】可以用A、B、C、D表示4個城區(qū)，用7條線表示7座橋，將七橋問題抽象為一個圖模型。情景問題——七橋問題

【想法——基本思路】是否存在歐拉回路的判定規(guī)則是：（1）如果通奇數(shù)橋的地方多于兩個，則不存在歐拉回路；（2）如果只有兩個地方通奇數(shù)橋，可以從這兩個地方之一出發(fā)，找到歐拉回路；（3）如果沒有一個地方通奇數(shù)橋，則無論從哪里出發(fā)，都能找到歐拉回路。由上述判定規(guī)則得到求解七橋問題的基本思路：依次計算圖中與每個節(jié)點相關(guān)聯(lián)的邊的個數(shù)（稱為節(jié)點的度），根據(jù)度為奇數(shù)的節(jié)點個數(shù)判定是否存在歐拉回路。情景問題——七橋問題

【數(shù)據(jù)表示——數(shù)據(jù)結(jié)構(gòu)】設(shè)鄰接矩陣arc[n][n]存儲圖?！緮?shù)據(jù)處理——算法】算法用偽代碼描述如下：1.通奇數(shù)橋的頂點個數(shù)count初始化為0；

2.下標(biāo)i從0~n–1重復(fù)執(zhí)行下述操作：

2.1計算矩陣arc[n][n]第i行元素之和degree;2.2如果degree為奇數(shù)，則count++;3.如果count等于0或2，則存在歐拉回路；否則不存在歐拉回路；偽代碼0122101121002100ABCDABCD情景問題——七橋問題

【程序?qū)崿F(xiàn)】以下是用C語言編寫的程序：intEulerCircuit(intmat[10][10],intn)//函數(shù)定義，二維數(shù)組作為形參

{inti,j,count=0,degree;//count累計通奇數(shù)橋的節(jié)點個數(shù)

for(i=0;i<n;i++)//依次累加每一行的元素

{degree=0;//degree存儲通過節(jié)點i的橋數(shù)，初始化為0for(j=0;j<n;j++)//依次處理每一列的元素

{degree=degree+mat[i][j];//將通過節(jié)點i的橋數(shù)求和

}if(degree%2!=0)//橋數(shù)為奇數(shù)

count++;}returncount;//結(jié)束函數(shù)，并將count返回到調(diào)用處問題算法程序想法抽象模型基本思路數(shù)據(jù)表示數(shù)據(jù)處理程序語言設(shè)計方法編程環(huán)境人（設(shè)計方案）計算機(jī)(執(zhí)行方案)問題求解與程序設(shè)計——程序設(shè)計程序設(shè)計的一般過程為問題建立模型，抽象化、模型化將算法轉(zhuǎn)換程序，掌握程序語言、熟悉編程環(huán)境，設(shè)計解決方案，需要數(shù)據(jù)結(jié)構(gòu)和算法的知識。問題算法程序想法問題求解與程序設(shè)計——程序設(shè)計程序設(shè)計的一般過程理解程序問題求解與程序設(shè)計——程序設(shè)計

計算機(jī)是一個大容量、高速運轉(zhuǎn)、但是沒有思維的機(jī)器。計算機(jī)只認(rèn)識0和1，聽不懂人說的話——計算機(jī)如何接收人的指令？有問題需要解決的人可以解決問題的計算機(jī)Hello理解程序如何實現(xiàn)人和計算機(jī)的交流？問題求解與程序設(shè)計——程序設(shè)計

計算機(jī)是一個大容量、高速運轉(zhuǎn)、但是沒有思維的機(jī)器。計算機(jī)輸出了0和1的編碼，可是人看不懂——如何解釋計算機(jī)的運算結(jié)果？有問題需要解決的人可以解決問題的計算機(jī)0101000110……理解程序問題求解與程序設(shè)計——程序設(shè)計有問題需要解決的人可以解決問題的計算機(jī)程序是跨越這條鴻溝的橋梁，人要和計算機(jī)有效地交流，必須通過程序。程序

程序：是能夠?qū)崿F(xiàn)特定功能的一組指令序列的集合，是描述對某一問題的解決步驟。其中，指令可以是機(jī)器指令、匯編語言的語句，也可以是高級語言的語句，甚至還可以是用自然語言描述的指令。用高級語言編寫的程序稱為源程序；用機(jī)器語言（或匯編語言）編寫的程序稱為目標(biāo)程序；由二進(jìn)制代碼表示的程序稱為機(jī)器代碼。程序設(shè)計：是給出解決特定問題的程序的過程，是軟件構(gòu)造活動中的重要組成部分，程序設(shè)計往往以某種程序設(shè)計語言為工具，給出這種語言下的程序。專業(yè)的程序設(shè)計人員常被稱為程序員。問題求解與程序設(shè)計——程序設(shè)計程序設(shè)計的關(guān)鍵問題求解與程序設(shè)計——程序設(shè)計

程序設(shè)計的關(guān)鍵是數(shù)據(jù)表示和數(shù)據(jù)處理。

數(shù)據(jù)表示完成的任務(wù)是從問題抽象出數(shù)據(jù)模型，并將該模型從機(jī)外表示轉(zhuǎn)換為機(jī)內(nèi)表示；

數(shù)據(jù)處理完成的任務(wù)是對問題的求解方法進(jìn)行抽象描述，即設(shè)計算法，再將算法的指令轉(zhuǎn)換為某種程序設(shè)計語言對應(yīng)的語句，轉(zhuǎn)換所依據(jù)的規(guī)則就是某種程序設(shè)計語言的語法。程序設(shè)計的關(guān)鍵問題求解與程序設(shè)計——程序設(shè)計

計算機(jī)能夠求解的問題一般可以分為數(shù)值問題和非數(shù)值問題，數(shù)值問題抽象出的數(shù)據(jù)模型通常是數(shù)學(xué)方程，非數(shù)值問題抽象出的數(shù)據(jù)模型通常是線性表、樹、圖等數(shù)據(jù)結(jié)構(gòu)。

存儲程序意味著需要將抽象出的數(shù)據(jù)模型從機(jī)外表示轉(zhuǎn)換為機(jī)內(nèi)表示，也就是將數(shù)據(jù)模型存儲到計算機(jī)的內(nèi)存中，典型方法就是用程序設(shè)計語言描述數(shù)據(jù)模型。

程序設(shè)計的關(guān)鍵問題求解與程序設(shè)計——程序設(shè)計

問題的解決方案最終需要借助程序設(shè)計語言來表示，也就是將算法轉(zhuǎn)換為程序，只有在計算機(jī)上能夠運行良好的程序才能為人們解決特定的實際問題。數(shù)據(jù)處理的核心是算法設(shè)計，一般來說，對不同求解方法的抽象描述產(chǎn)生了相應(yīng)的不同算法，不同的算法將設(shè)計出不同的程序。

問題求解與程序設(shè)計——數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)：所有能輸入到計算機(jī)中并能被計算機(jī)程序識別和處理的符號集合。包括數(shù)值、字符、圖形、圖像、聲音等。

數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計算機(jī)程序中通常作為一個整體進(jìn)行考慮和處理。

數(shù)據(jù)結(jié)構(gòu)：相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合，通常，數(shù)據(jù)元素之間具有以下三種基本關(guān)系：（1）一對一的線性關(guān)系：線性結(jié)構(gòu)；（2）一對多的層次關(guān)系：樹結(jié)構(gòu)；（3）多對多的任意關(guān)系：圖結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)的基本概念問題求解與程序設(shè)計——數(shù)據(jù)結(jié)構(gòu)例6.1為學(xué)籍管理問題抽象數(shù)據(jù)模型。數(shù)據(jù)結(jié)構(gòu)的基本概念問題求解與程序設(shè)計——數(shù)據(jù)結(jié)構(gòu)例6.2為人機(jī)對弈問題抽象數(shù)據(jù)模型。數(shù)據(jù)結(jié)構(gòu)的基本概念問題求解與程序設(shè)計——數(shù)據(jù)結(jié)構(gòu)例6.3為七巧板涂色問題抽象數(shù)據(jù)模型。數(shù)據(jù)結(jié)構(gòu)的基本概念

為現(xiàn)實世界的問題建立數(shù)據(jù)模型后，還要將該模型存儲在計算機(jī)的內(nèi)存中，即將數(shù)據(jù)從機(jī)外表示轉(zhuǎn)換為機(jī)內(nèi)表示。通常有兩種存儲表示方法：順序存儲和鏈接存儲。

順序存儲的基本思想是：用一組連續(xù)的存儲單元依次存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系由元素的存儲位置來表示；

鏈接存儲的基本思想是：用一組任意的存儲單元存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系用指針來表示。問題求解與程序設(shè)計——數(shù)據(jù)結(jié)構(gòu)存儲結(jié)構(gòu)問題求解與程序設(shè)計——數(shù)據(jù)結(jié)構(gòu)存儲結(jié)構(gòu)問題求解與程序設(shè)計——數(shù)據(jù)結(jié)構(gòu)存儲結(jié)構(gòu)ABCDEFGHIJ算法的定義問題求解與程序設(shè)計——算法

算法（Algorithm）:對特定問題求解步驟的一種描述，是指令的有限序列。

算法的五大特性：⑴

輸入：一個算法有零個或多個輸入。⑵輸出：一個算法有一個或多個輸出。⑶有窮性：一個算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成。⑷確定性：算法中的每一條指令必須有確切的含義，對于相同的輸入只能得到相同的輸出。⑸可行性：算法描述的操作可以通過已經(jīng)實現(xiàn)的基本操作執(zhí)行有限次來實現(xiàn)。算法的定義問題求解與程序設(shè)計——算法

算法（Algorithm）:對特定問題求解步驟的一種描述，是指令的有限序列。操作步驟（有窮性、確定性、可行性）

1.………2.………3.………輸入輸入描述算法問題求解與程序設(shè)計——算法

算法的設(shè)計者在構(gòu)思和設(shè)計了一個算法之后，必須清楚準(zhǔn)確地將所設(shè)計的求解步驟記錄下來，即描述算法。通常用偽代碼來描述算法。

偽代碼是介于自然語言和程序設(shè)計語言之間的方法，保留了程序設(shè)計語言嚴(yán)謹(jǐn)?shù)慕Y(jié)構(gòu)、語句的形式和控制成分，忽略了繁瑣的變量說明，在抽象地描述算法時一些處理和條件允許使用自然語言來表達(dá)。至于算法中自然語言的成份有多少，取決于算法的抽象級別。由于偽代碼書寫方便、格式緊湊、容易理解和修改，因此被稱為算法語言。描述算法問題求解與程序設(shè)計——算法例6.4設(shè)計算法，在含有n個元素的集合中查找最大值元素。解：設(shè)最大值為max，可以假定第1個元素為最大值元素，依次將第2、3、……、n個元素與max比較，max中保存的始終是每次比較后的最大值元素，算法用偽代碼描述如下：step1:max

第1個元素；

step2:初始化被比較元素的序號i2；

step3:當(dāng)i小于等于n時重復(fù)執(zhí)行下述操作：

step3.1:如果第i個元素大于max，則max

第i個元素；

step3.2:ii+1；step4:輸出max；偽代碼描述算法問題求解與程序設(shè)計——算法例6.5設(shè)計算法，實現(xiàn)歐幾里德算法。解：設(shè)兩個自然數(shù)是m和n并滿足m≥n，歐幾里德算法的基本思想是將m和n輾轉(zhuǎn)相除直到余數(shù)為0。例如，m=35，n=25，m除以n的余數(shù)用r表示，計算過程如下：當(dāng)余數(shù)r為0時，被除數(shù)n就是m和n的最大公約數(shù)。描述算法問題求解與程序設(shè)計——算法例6.5設(shè)計算法，實現(xiàn)歐幾里德算法。偽代碼step1:r

mmodn;

step2:循環(huán)直到r等于0step2.1:m

n;step2.2:n

r;step2.3:r

mmodn;

step3:輸出n;算法分析：對算法所需要的計算機(jī)資源進(jìn)行估算。時間復(fù)雜度（TimeComplexity）空間復(fù)雜度（SpaceComplexity）撇開與計算機(jī)軟硬件有關(guān)的因素，影響算法時間代價的最主要因素是問題規(guī)模。問題規(guī)模：輸入量的多少，一般來說，它可以從問題描述中得到。例如，找出100以內(nèi)的所有素數(shù)，問題規(guī)模是100。一個顯而易見的事實是：幾乎所有的算法，對于規(guī)模更大的輸入需要運行更長的時間。例如，找出10000以內(nèi)的所有素數(shù)比找出100以內(nèi)的所有素數(shù)需要更多的時間。所以運行算法所需要的時間T是問題規(guī)模n的函數(shù)，記作T(n)。算法分析問題求解與程序設(shè)計——算法為了客觀地反映一個算法的執(zhí)行時間，可以用算法中基本語句的執(zhí)行次數(shù)來度量算法的工作量?；菊Z句：執(zhí)行次數(shù)與整個算法的執(zhí)行次數(shù)成正比的操作指令?；菊Z句對算法運行時間的貢獻(xiàn)最大，是算法中最重要的操作。分析算法的時間復(fù)雜度的基本方法是：找出所有語句中執(zhí)行次數(shù)最多的那條語句作為基本語句，計算基本語句的執(zhí)行次數(shù)，取其數(shù)量級放入大Ｏ中即可。這種衡量效率的方法得出的不是時間量，而是一種增長趨勢的度量。算法分析問題求解與程序設(shè)計——算法算法分析問題求解與程序設(shè)計——算法例6.6分析下列算法的時間復(fù)雜度。解：基本語句是step3.1的比較語句，即第i個元素是否大于max，該語句需要重復(fù)執(zhí)行n–1次，因此，算法的時間復(fù)雜度是O(n)。step1:max

第1個元素；

step2:初始化被比較元素的序號i2；

step3:當(dāng)i小于等于n時重復(fù)執(zhí)行下述操作：

step3.1:如果第i個元素大于max，則max

第i個元素；

step3.2:ii+1；step4:輸出max；偽代碼程序設(shè)計語言的發(fā)展問題求解與程序設(shè)計——程序語言程序設(shè)計語言的發(fā)展是一個不斷演化的過程，其根本的推動力是對抽象機(jī)制的更高的要求，以及對程序設(shè)計思想的更好的支持。

第一代程序設(shè)計語言（1GL）——機(jī)器語言

如果不小心弄錯了一個二進(jìn)制位，該如何找出來？程序設(shè)計語言的發(fā)展問題求解與程序設(shè)計——程序語言程序設(shè)計語言的發(fā)展是一個不斷演化的過程，其根本的推動力是對抽象機(jī)制的更高的要求，以及對程序設(shè)計思想的更好的支持。

第二代程序設(shè)計語言（2GL）——匯編語言

例如，ADD表示機(jī)器指令00000100。相對于機(jī)器語言，匯編語言簡化了程序編寫，而且不容易出錯程序設(shè)計語言的發(fā)展問題求解與程序設(shè)計——程序語言程序設(shè)計語言的發(fā)展是一個不斷演化的過程，其根本的推動力是對抽象機(jī)制的更高的要求，以及對程序設(shè)計思想的更好的支持。

第三代程序設(shè)計語言（3GL）——高級語言

高級語言：高級程序設(shè)計語言，相應(yīng)地，機(jī)器語言和匯編語言稱為低級語言，低級意味著要求程序員從機(jī)器的層次上考慮問題。

結(jié)構(gòu)化程序設(shè)計語言：BASIC、PASCAL、C等。

面向?qū)ο蟪绦蛟O(shè)計語言：Java、C++、C#等。

可視化程序設(shè)計語言：VB、Delphi、VisualC++等。

網(wǎng)絡(luò)程序設(shè)計語言：ASP、PHP和JSP等。程序設(shè)計語言的發(fā)展問題求解與程序設(shè)計——程序語言程序設(shè)計語言的發(fā)展是一個不斷演化的過程，其根本的推動力是對抽象機(jī)制的更高的要求，以及對程序設(shè)計思想的更好的支持。

第四代程序設(shè)計語言（4GL）——非過程式語言

利用4GL開發(fā)軟件只需要考慮“做什么”而不必考慮“如何做”，不涉及太多的算法細(xì)節(jié)，從而大大提高軟件生產(chǎn)率。到目前為止，使用最廣泛的4GL是數(shù)據(jù)庫查詢語言，許多大型數(shù)據(jù)庫語言如Oracle、Sybase、Informix等都包含有4GL成分。

程序設(shè)計語言的發(fā)展問題求解與程序設(shè)計——程序語言程序設(shè)計語言的發(fā)展是一個不斷演化的過程，其根本的推動力是對抽象機(jī)制的更高的要求，以及對程序設(shè)計思想的更好的支持。

第五代程序設(shè)計語言（5GL）——知識型語言

5GL主要應(yīng)用在人工智能研究上，典型代表是LISP語言和PROLOG語言。目前，4GL和5GL的發(fā)展都不是很成熟，在效率、應(yīng)用等方面都存在諸多問題，常用的程序設(shè)計語言仍然是3GL。

程序設(shè)計語言的基本要素問題求解與程序設(shè)計——程序語言自然語言與程序設(shè)計語言的類比：文章由段落、句子、單詞和字母組成，類似地，程序設(shè)計語言的一個程序由模塊、語句、單詞和基本字符組成。文章——程序段落——模塊句子——語句單詞——單詞字母——基本字符基本符號單詞語句函數(shù)程序詞法規(guī)則語法規(guī)則功能邏輯有機(jī)組合程序設(shè)計語言的基本要素問題求解與程序設(shè)計——程序語言程序設(shè)計語言由語法和語義兩方面定義的。語法包括詞法規(guī)則和語法規(guī)則，詞法規(guī)則規(guī)定了如何從語言的基本符號構(gòu)成詞法單位（也稱單詞），語法規(guī)則規(guī)定了如何由單詞構(gòu)成語法單位（例如語句），這些規(guī)則是判斷一個字符串是否構(gòu)成一個形式上正確的程序的依據(jù)；語義規(guī)則規(guī)定了各語法單位的具體含義，程序設(shè)計語言的語義具有上下文無關(guān)性，程序文本所表示的語義是單一的、確定的。從某種角度說，學(xué)習(xí)程序設(shè)計語言主要就是學(xué)習(xí)這些規(guī)則。程序設(shè)計語言的基本要素問題求解與程序設(shè)計——程序語言學(xué)習(xí)程序設(shè)計語言的最終目的是能夠表示問題的解決方案。實際上，所有程序設(shè)計語言的最終目的都是控制計算機(jī)按照人們的意愿去工作。共同的目的使各種各樣的程序設(shè)計語言具有共同的基本內(nèi)容，無論哪一種程序設(shè)計語言，都是以數(shù)據(jù)的表示（常量、變量、數(shù)據(jù)類型等）、數(shù)據(jù)的組織（數(shù)組、結(jié)構(gòu)體、類等）、數(shù)據(jù)處理（賦值運算、算術(shù)運算、邏輯運算等）、程序的流程控制（順序、分支、循環(huán)等）、數(shù)據(jù)傳遞（全局變量、函數(shù)調(diào)用、消息傳遞等）為基本內(nèi)容，只是不同的語言采用不同的方法實現(xiàn)上述基本內(nèi)容，體現(xiàn)為不同的程序設(shè)計語言具有不同的表述格式（即語法規(guī)則）。程序設(shè)計的環(huán)境問題求解與程序設(shè)計——程序語言程序設(shè)計的環(huán)境是指利用程序設(shè)計語言進(jìn)行程序開發(fā)的編程環(huán)境。目前的編程環(huán)境大都是交互式集成開發(fā)環(huán)境（IntegratedDesignEnvironment，IDE），包括程序編輯、程序編譯、運行調(diào)試等功能。此外，還包括許多編程的實用程序。熟練使用編程工具和環(huán)境，也是提高編程效率的因素之一，初學(xué)者應(yīng)該盡快熟悉編程環(huán)境。

程序設(shè)計的環(huán)境問題求解與程序設(shè)計——程序語言編輯窗口執(zhí)行按鈕編譯按鈕信息窗口翻譯程序的工作方式問題求解與程序設(shè)計——翻譯程序

利用高級語言編寫的程序不能直接在計算機(jī)上執(zhí)行，因為計算機(jī)只能執(zhí)行二進(jìn)制的機(jī)器指令，所以，必須將高級語言編寫的程序（稱為源程序）轉(zhuǎn)換為在邏輯上等價的機(jī)器指令（稱為目標(biāo)程序），實現(xiàn)這種轉(zhuǎn)換的程序稱為翻譯程序。不同的程序設(shè)計語言需要有不同的翻譯程序。同一種程序設(shè)計語言在不同類型的計算機(jī)上也需要配置不同的翻譯程序。翻譯程序的工作方式問題求解與程序設(shè)計——翻譯程序同一種程序設(shè)計語言在不同類型的計算機(jī)上也需要配置不同的翻譯程序。翻譯程序的工作方式問題求解與程序設(shè)計——翻譯程序解釋方式一般是翻譯一句執(zhí)行一句，在翻譯過程中，并不把源程序翻譯成一個完整的目標(biāo)程序，而是按照源程序中語句的順序逐條語句翻譯成機(jī)器可執(zhí)行的指令并立即予以執(zhí)行。由于解釋方式不產(chǎn)生目標(biāo)代碼，所以，源程序的執(zhí)行不能脫離其解釋環(huán)境，并且每次運行都需要重新解釋。BASIC語言和JAVA語言都具有逐條解釋執(zhí)行程序的功能。翻譯程序的工作方式問題求解與程序設(shè)計——翻譯程序編譯方式是一個整體理解和翻譯的過程，先由編譯程序把源程序翻譯成目標(biāo)程序，然后再由計算機(jī)執(zhí)行目標(biāo)程序。由于編譯后形成了可執(zhí)行的目標(biāo)代碼，所以，目標(biāo)程序可以脫離其語言環(huán)境獨立執(zhí)行。C、C++語言都是編譯型語言。編譯程序的基本過程問題求解與程序設(shè)計——翻譯程序編譯程序是把源程序翻譯成目標(biāo)程序，因此，編譯程序需要根據(jù)源語言的具體特點和對目標(biāo)程序的具體要求來設(shè)計。如同自然語言的翻譯，編譯程序的翻譯規(guī)則是源語言的語法規(guī)則和語義規(guī)則。

編譯程序的基本過程問題求解與程序設(shè)計——翻譯程序詞法分析的任務(wù)是對源程序進(jìn)行掃描和分解，按照詞法規(guī)則識別出一個個的單詞，如關(guān)鍵字、標(biāo)識符、運算符等，并將單詞轉(zhuǎn)化為某種機(jī)內(nèi)表示。

其中，單詞①是關(guān)鍵字，單詞②是