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

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

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

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

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

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

【問題】17世紀的東普魯士有一座哥尼斯堡城（現(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è)計方案）計算機(執(zhí)行方案)問題求解與程序設(shè)計——程序設(shè)計程序設(shè)計的一般過程為問題建立模型，抽象化、模型化將算法轉(zhuǎn)換程序，掌握程序語言、熟悉編程環(huán)境，設(shè)計解決方案，需要數(shù)據(jù)結(jié)構(gòu)和算法的知識。問題算法程序想法問題求解與程序設(shè)計——程序設(shè)計程序設(shè)計的一般過程理解程序問題求解與程序設(shè)計——程序設(shè)計

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

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

程序：是能夠?qū)崿F(xiàn)特定功能的一組指令序列的集合，是描述對某一問題的解決步驟。其中，指令可以是機器指令、匯編語言的語句，也可以是高級語言的語句，甚至還可以是用自然語言描述的指令。用高級語言編寫的程序稱為源程序；用機器語言（或匯編語言）編寫的程序稱為目標(biāo)程序；由二進制代碼表示的程序稱為機器代碼。程序設(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ù)模型，并將該模型從機外表示轉(zhuǎn)換為機內(nèi)表示；

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

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

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

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

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

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

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

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

數(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為人機對弈問題抽象數(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ù)模型后，還要將該模型存儲在計算機的內(nèi)存中，即將數(shù)據(jù)從機外表示轉(zhuǎn)換為機內(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è)計了一個算法之后，必須清楚準確地將所設(shè)計的求解步驟記錄下來，即描述算法。通常用偽代碼來描述算法。

偽代碼是介于自然語言和程序設(shè)計語言之間的方法，保留了程序設(shè)計語言嚴謹?shù)慕Y(jié)構(gòu)、語句的形式和控制成分，忽略了繁瑣的變量說明，在抽象地描述算法時一些處理和條件允許使用自然語言來表達。至于算法中自然語言的成份有多少，取決于算法的抽象級別。由于偽代碼書寫方便、格式緊湊、容易理解和修改，因此被稱為算法語言。描述算法問題求解與程序設(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;算法分析：對算法所需要的計算機資源進行估算。時間復(fù)雜度（TimeComplexity）空間復(fù)雜度（SpaceComplexity）撇開與計算機軟硬件有關(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句對算法運行時間的貢獻最大，是算法中最重要的操作。分析算法的時間復(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ā)展是一個不斷演化的過程，其根本的推動力是對抽象機制的更高的要求，以及對程序設(shè)計思想的更好的支持。

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

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

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

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

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

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

結(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ā)展是一個不斷演化的過程，其根本的推動力是對抽象機制的更高的要求，以及對程序設(shè)計思想的更好的支持。

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

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

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

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

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

程序設(shè)計語言的基本要素問題求解與程序設(shè)計——程序語言自然語言與程序設(shè)計語言的類比：文章由段落、句子、單詞和字母組成，類似地，程序設(shè)計語言的一個程序由模塊、語句、單詞和基本字符組成。文章——程序段落——模塊句子——語句單詞——單詞字母——基本字符基本符號單詞語句函數(shù)程序詞法規(guī)則語法規(guī)則功能邏輯有機組合程序設(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è)計語言的最終目的都是控制計算機按照人們的意愿去工作。共同的目的使各種各樣的程序設(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è)計語言進行程序開發(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è)計——翻譯程序

利用高級語言編寫的程序不能直接在計算機上執(zhí)行，因為計算機只能執(zhí)行二進制的機器指令，所以，必須將高級語言編寫的程序（稱為源程序）轉(zhuǎn)換為在邏輯上等價的機器指令（稱為目標(biāo)程序），實現(xiàn)這種轉(zhuǎn)換的程序稱為翻譯程序。不同的程序設(shè)計語言需要有不同的翻譯程序。同一種程序設(shè)計語言在不同類型的計算機上也需要配置不同的翻譯程序。翻譯程序的工作方式問題求解與程序設(shè)計——翻譯程序同一種程序設(shè)計語言在不同類型的計算機上也需要配置不同的翻譯程序。翻譯程序的工作方式問題求解與程序設(shè)計——翻譯程序解釋方式一般是翻譯一句執(zhí)行一句，在翻譯過程中，并不把源程序翻譯成一個完整的目標(biāo)程序，而是按照源程序中語句的順序逐條語句翻譯成機器可執(zhí)行的指令并立即予以執(zhí)行。由于解釋方式不產(chǎn)生目標(biāo)代碼，所以，源程序的執(zhí)行不能脫離其解釋環(huán)境，并且每次運行都需要重新解釋。BASIC語言和JAVA語言都具有逐條解釋執(zhí)行程序的功能。翻譯程序的工作方式問題求解與程序設(shè)計——翻譯程序編譯方式是一個整體理解和翻譯的過程，先由編譯程序把源程序翻譯成目標(biāo)程序，然后再由計算機執(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ù)是對源程序進行掃描和分解，按照詞法規(guī)則識別出一個個的單詞，如關(guān)鍵字、標(biāo)識符、運算符等，并將單詞轉(zhuǎn)化為某種機內(nèi)表示。

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