大學(xué)計(jì)算機(jī)基礎(chǔ)-計(jì)算思維視角 課件 ch06計(jì)算平臺(tái)一一算法與程序設(shè)計(jì)

算法與程序設(shè)計(jì)新工科建設(shè)之路·計(jì)算機(jī)類專業(yè)精品教材計(jì)算平臺(tái)第六章算法的概念0101算法的概念1.什么是算法算法(Algorithm)一詞源于算術(shù)(Algorism)，即算術(shù)方法，是指一種由已知推求未知的運(yùn)算過程。后來，人們把進(jìn)行某一工作的方法和步驟稱為算法。隨著計(jì)算機(jī)的出現(xiàn)，算法被廣泛地應(yīng)用于計(jì)算機(jī)的問題求解中，被認(rèn)為是程序設(shè)計(jì)的精髓。在計(jì)算機(jī)科學(xué)中，算法是指問題求解的方法及求解過程的描述，是一個(gè)經(jīng)過精心設(shè)計(jì)，用以解決一類特定問題的計(jì)算序列。01算法的概念2.算法的特性確定性算法中每一個(gè)步驟都必須是確切定義的，不能產(chǎn)生二義性，對于相同的輸入必須得出相同的執(zhí)行結(jié)果。01可行性算法必須是由一系列具體步驟組成的，并且每一步都能被計(jì)算機(jī)理解和執(zhí)行。02有窮性一個(gè)算法應(yīng)包含有限個(gè)操作步驟。在執(zhí)行有限個(gè)操作步驟之后，算法能正常結(jié)束，而且每一步都能在合理的時(shí)間范圍內(nèi)完成。0301算法的概念2.算法的特性有零個(gè)或多個(gè)輸入一個(gè)算法可以有零個(gè)或多個(gè)輸入，這取決于算法要實(shí)現(xiàn)的功能。這里的輸入可能是鍵盤輸入，也可能是從文件中讀取的輸入。04有一個(gè)或多個(gè)輸出算法的執(zhí)行結(jié)果必須以某種形式反饋給用戶，沒有輸出的算法毫無意義。這里的輸出可以是屏幕輸出或打印，也可以是將結(jié)果保存到文件或數(shù)據(jù)庫中。0501算法的概念3.算法的分類算法的種類很多，分類標(biāo)準(zhǔn)也很多。根據(jù)處理的數(shù)據(jù)是數(shù)值數(shù)據(jù)還是非數(shù)值數(shù)據(jù)，算法可以分為數(shù)值計(jì)算方法和非數(shù)值計(jì)算方法。數(shù)值計(jì)算是指以獲得數(shù)值結(jié)果為目標(biāo)的計(jì)算，主要用于科學(xué)計(jì)算，其特點(diǎn)是少量的輸輸出和復(fù)雜的運(yùn)算，如解線性方程組的直接法、解線性方程組的迭代法等算法。入非數(shù)值計(jì)算的計(jì)算對象是信息，包含文字、圖形、記錄等，目的是對數(shù)據(jù)進(jìn)行管理，其特點(diǎn)是大量的輸入、輸出和大量的邏輯運(yùn)算，如對數(shù)據(jù)的排序、查找等算法。在解決非數(shù)值計(jì)算問題時(shí)，可以借鑒一些基礎(chǔ)的思維方式，如分治、遞歸等。02算法的表示1.算法的自然語言描述自然語言就是人們?nèi)粘Ｊ褂玫恼Z言，可以使用漢語、英語或其他語言等。用自然語言表示算法通俗易懂，但文字冗長，表示的含義往往不太嚴(yán)格，要根據(jù)上下文才能判斷其正確含義，容易出現(xiàn)歧義性。此外，用自然語言來描述包含分支和循環(huán)的算法很不方便，因此除那些簡單的問題外，一般不用自然語言描述算法。02算法的表示2.算法的流程圖描述流程圖(FlowChart)描述是指使用一些幾何圖形、線條和文字來表示各種操作和處理步驟。用流程圖來描述問題的解題步驟，可使算法十分明確，具體直觀，易于理解。美國國家標(biāo)準(zhǔn)化協(xié)會(huì)(AmericanNationalStandardInstitute，ANSI)規(guī)定了一些常用的流程圖符號(hào)。02算法的表示3.算法的偽代碼描述由于算法的設(shè)計(jì)需要反復(fù)修改，每次修改均需要重新繪制流程圖，而繪圖過程較費(fèi)時(shí),因而為了方便設(shè)計(jì)算法，常采用偽代碼表示。偽代碼產(chǎn)生于20世紀(jì)70年代，用介于自然語言與計(jì)算機(jī)語言之間的文字和符號(hào)來描述算法。偽代碼不使用圖形，格式緊湊，易于理解。02算法的表示4.算法的計(jì)算機(jī)語言描述不管是流程圖還是偽代碼，最后要讓計(jì)算機(jī)識(shí)別并能自動(dòng)執(zhí)行，都需要轉(zhuǎn)換成計(jì)算機(jī)語言編寫的程序。用計(jì)算機(jī)語言描述算法必須嚴(yán)格遵循所選擇的編程語言的語法規(guī)則。[例6.1]假設(shè)期末總評成績的計(jì)算方法平時(shí)成績x0.2+考試成績X0.8現(xiàn)已知某學(xué)生某門課程的平時(shí)成績和考試成績，計(jì)算出該生的總評成績，并給出該課程是否通過(大于或等于60分為通過)。算法的流程圖、偽代碼和C語言3種描述方法。03常用的基本算法1.枚舉法枚舉法也稱窮舉法、列舉法、試湊法、蠻力法等。枚舉法的求解思路很簡單，就是對所有可能的解逐一嘗試，從而找出問題的真正解。枚舉法的基本思想是首先依據(jù)題目的部分條件確定答案的大致范圍，然后在此范圍內(nèi)對所有可能情況逐一驗(yàn)證，直到全部情況驗(yàn)證完。若某個(gè)情況經(jīng)過驗(yàn)證符合題目的全部條件，則為本題的一個(gè)答案;若全部情況經(jīng)過驗(yàn)證后都不符合題目的條件，則本題無解。枚舉法是一種比較耗時(shí)的算法。由于計(jì)算機(jī)的運(yùn)算速度快，擅長重復(fù)操作，因此很容易用計(jì)算機(jī)完成大量的枚舉。03常用的基本算法1.枚舉法[例6.2]百錢買百雞問題的枚舉法求解過程。03常用的基本算法2.迭代法選代法也稱遞推法、輾轉(zhuǎn)法等，它是利用問題本身所具有的某種遞推關(guān)系求解問題的一種方法。迭代法的基本思想是從初值出發(fā)，歸納出新值與舊值間存在的關(guān)系，這個(gè)關(guān)系就是迭代遞推公式，利用此公式不斷地用舊的變量值遞推計(jì)算新的變量值，從而把一個(gè)復(fù)雜的計(jì)算過程轉(zhuǎn)化為簡單過程的多次重復(fù)。03常用的基本算法2.迭代法[例6.3]用歐幾里得算法求兩個(gè)任意整數(shù)的最大公約數(shù)。03常用的基本算法2.迭代法[例6.4]計(jì)算任意一個(gè)整數(shù)的相反數(shù)，如整數(shù)1389，其相反數(shù)是9831。對于任意整數(shù)，因不知確定的位數(shù)，所以求其相反數(shù)的算法可以用如下所示的迭代過程。03常用的基本算法3.遞歸法若一個(gè)算法直接地或間接地調(diào)用自己本身，則稱這個(gè)算法是遞歸算法。遞歸法的基本思想是把一個(gè)大型復(fù)雜的問題層層轉(zhuǎn)化為一個(gè)與原問題相似的規(guī)模較小的問題來進(jìn)行求解。因?yàn)閱栴}規(guī)模變小，所以遞歸策略可以簡單描述，且易于理解;解題過程需要多次重復(fù)計(jì)算，因此遞歸本質(zhì)上是一種循環(huán)的算法結(jié)構(gòu)。03常用的基本算法3.遞歸法[例6.5]計(jì)算n的階乘(n!)。03常用的基本算法4.最值算法所謂最值，就是指最大值和最小值。當(dāng)求最值時(shí)，需要有一個(gè)變量來記錄最大或最小這個(gè)變量稱為最值變量。求最值的基本思想是首先給最值變量一個(gè)初值，然后每個(gè)元素依次和最值變量比較遇到比最值變量更大(或更小)的元素時(shí)就用其值更新最值變量的值。最值變量的初值可以用元素集合中的第一個(gè)數(shù)，也可以用一個(gè)元素取值范圍中的最小數(shù)(求最大值時(shí))或最大數(shù)(求最小值時(shí))，總之，當(dāng)求最大值時(shí)，最值變量的初值數(shù)據(jù)一定要保證比所用元素集合中的最小值還要小;當(dāng)求最小值時(shí)，最值變量的初值數(shù)據(jù)一定要保證比所用元素集合中的最大值還要大。03常用的基本算法4.最值算法[例6.6]找出10個(gè)整數(shù)中的最大數(shù)使用元素集合中的第一個(gè)數(shù)作為最值變量的初值，描述算法的程序流程圖如圖6-5所示。設(shè)有符號(hào)整數(shù)占內(nèi)存空間2個(gè)字節(jié)，其所表示的數(shù)值大小為-32768~32767，當(dāng)求最大數(shù)時(shí)，最值變量的初值可用-32768表示，描述算法的程序流程圖如圖6-6所示。03常用的基本算法5.排序算法所謂排序，就是按某種特定的順序排列數(shù)據(jù)，把無序的數(shù)據(jù)序列調(diào)整為有序的數(shù)據(jù)序列。排序在數(shù)據(jù)處理領(lǐng)域中應(yīng)用十分廣泛，排序也是計(jì)算機(jī)程序中經(jīng)常要用到的基本算法排序的方法有很多，每種排序方法都有其各自的特點(diǎn)和適用場景，本書僅介紹選擇排序和冒泡排序。03常用的基本算法5.排序算法選擇排序選擇排序是一種簡單直觀的排序算法。它的基本方法是每次先從待排序的無序數(shù)中找出最小(或最大)的一個(gè)元素，存儲(chǔ)在無序數(shù)的第一個(gè)位置;再從剩余的待排序的無序數(shù)中繼續(xù)找出最小(或最大)的一個(gè)元素，存儲(chǔ)在無序數(shù)的第一個(gè)位置或者說是已排序數(shù)的末尾位置。以此類推，直到待排序的數(shù)據(jù)元素的個(gè)數(shù)為零。0103常用的基本算法5.排序算法[例6.7]用選擇排序方法對n個(gè)給定的整數(shù)降序排序設(shè)有49、38、65、76、13、27這6個(gè)數(shù)存儲(chǔ)在數(shù)組a中，選擇排序過程如圖6-7所其中，已有序的數(shù)據(jù)用一對中括號(hào)括起來。降序排序是每次在待排序的數(shù)據(jù)中找最大數(shù)。03常用的基本算法5.排序算法每一輪排序過程相應(yīng)的偽代碼如下，在每一輪排序算法中，不同的部分用粗體進(jìn)行了區(qū)分。03常用的基本算法5.排序算法[例6.8]用冒泡排序方法對n個(gè)給定的整數(shù)升序排序。設(shè)有49、38、657627、13這6個(gè)數(shù)存儲(chǔ)在數(shù)組a中冒泡排序過程如圖6-8所示其中，每經(jīng)過一輪比較后，在待排數(shù)據(jù)中都會(huì)有一個(gè)大數(shù)沉到它的最終位置處，曲線下方的數(shù)據(jù)是每一輪結(jié)束后已經(jīng)排好序的部分。例如，第1輪，最大數(shù)76底，小數(shù)13上升一個(gè)位置;第2輪，次大數(shù)65底，小數(shù)13繼續(xù)上升一個(gè)位置，如此循環(huán)往復(fù)。03常用的基本算法5.排序算法前兩輪排序過程相應(yīng)的偽代碼如下，在每一輪排序算法中，不同的部分用粗體進(jìn)行了區(qū)分。當(dāng)有n個(gè)數(shù)據(jù)時(shí)，排序過程最多需要經(jīng)歷n-1輪。用循環(huán)控制排序的輪數(shù)，最終完整的偽代碼如下。03常用的基本算法6.查找算法查找也稱檢索，是指在大量的數(shù)據(jù)中尋找某個(gè)特定的數(shù)據(jù)元素。查找算法是常用的基本運(yùn)算，利用計(jì)算機(jī)快速運(yùn)算的特點(diǎn)，可以方便地實(shí)現(xiàn)查找。查找的方法很多，對于不同的數(shù)據(jù)結(jié)構(gòu)，對應(yīng)有不同的查找策略。本書僅介紹順序查找和二分法查找。03常用的基本算法6.查找算法順序查找。順序查找又稱線性查找，它的基本方法是在待查找的數(shù)據(jù)元素中從一端開始按順序逐一比較，如果找到與給定值key相同的元素，則查找成功，如果所有元素均比較結(jié)束仍沒有找到與給定值key相同的元素，則查找失敗。順序查找對數(shù)據(jù)沒有特殊要求，可用于有序列表，也可用于無序列表;可用于線性結(jié)構(gòu)存儲(chǔ)的數(shù)據(jù)，也可用于鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)的數(shù)據(jù)。最好的情況是比較第1個(gè)數(shù)時(shí)即找到，最壞的情況是比較到第n個(gè)數(shù)(最后一個(gè)數(shù))時(shí)才知道結(jié)果，因此順序查找的平均查找次數(shù)是(n+1)/2，當(dāng)n值比較大時(shí)，查找效率較低。0103常用的基本算法6.查找算法[例6.9]用順序查找方法在n個(gè)元素中查找值為key的元素。順序查找過程如圖6-9所示。03常用的基本算法6.查找算法二分法查找二分法查找又稱折半查找，是在數(shù)據(jù)量較大時(shí)采用的一種高效查找法。當(dāng)采用二分法查找時(shí)，要求數(shù)據(jù)結(jié)構(gòu)必須是線性存儲(chǔ)結(jié)構(gòu)，且數(shù)據(jù)事先必須有序。猜數(shù)游戲使用的就是二分法查找，如果已知猜數(shù)范圍是1~100的整數(shù)，人們一般都會(huì)先猜50，若猜大了，下次就會(huì)在1~50之間猜25，以此類推，每次猜完后就可以過濾掉一半數(shù)據(jù)，使得下次要猜的數(shù)據(jù)量大大減少。二分法查找的基本思想是將待查找數(shù)據(jù)的中間元素與給定值key相比較，若相等，則查找成功;若不等，則依據(jù)數(shù)據(jù)的排序情況，或者取中間值左邊部分，或者取中間值右邊部分，作為下一次查找的待查找數(shù)據(jù)。重復(fù)此過程，直到查找成功，或者直到待查找數(shù)據(jù)不再存在，此時(shí)查找不成功。0203常用的基本算法6.查找算法[例6.10]用二分法查找在n個(gè)元素中查找值為key的元素。04算法的復(fù)雜性分析算法的復(fù)雜性分析(AlgorithmComplexityAnalysis)主要針對運(yùn)行該算法所需要的計(jì)算機(jī)資源的多少，需要的時(shí)間資源的量稱為時(shí)間復(fù)雜性，需要的空間資源的量稱為空間復(fù)雜性。算法所需要的資源越多，該算法的復(fù)雜性越高;反之，算法所需要的資源越少，該算法的復(fù)雜性越低。一個(gè)特定問題的算法在大部分情況下都不是唯一的，也就是說，同一個(gè)問題可以有多種解決問題的算法。算法沒有對錯(cuò)之分，但有優(yōu)劣之分。就好像我們做事情，常常會(huì)思考怎樣才能高效地解決問題。對于特定的問題、特定的約束條件，設(shè)計(jì)出復(fù)雜性最低的算法是設(shè)計(jì)算法時(shí)追求的重要目標(biāo)之一，而在存在的多種算法中選取其中復(fù)雜性最低的算法也是選用算法遵循的重要標(biāo)準(zhǔn)。用計(jì)算機(jī)求解問題的難易程度又稱為計(jì)算復(fù)雜性，其實(shí)就是度量它的時(shí)間復(fù)雜性和空間復(fù)雜性。04算法的復(fù)雜性分析1.時(shí)間復(fù)雜性時(shí)間復(fù)雜性(時(shí)間復(fù)雜度)是指算法實(shí)現(xiàn)過程所消耗的時(shí)間。假設(shè)每條語句執(zhí)行一次所需要的時(shí)間為單位時(shí)間，那么一個(gè)算法的執(zhí)行時(shí)間就和算法中需要執(zhí)行語句的次數(shù)成正比，就是所有語句的執(zhí)行次數(shù)之和，用O(m))表示。其中O表示代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長的變化趨勢，也稱漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。04算法的復(fù)雜性分析1.時(shí)間復(fù)雜性[例6.11]有如下C語言程序。其中，第3、4、5行各執(zhí)行一次，第6、8行分別執(zhí)行n次，第9、11行分別執(zhí)行n2次，所以可以得出時(shí)間復(fù)雜度為0(2n2+2n+3)，當(dāng)n的值非常大時(shí)，公式中的低階常數(shù)和系數(shù)三部分并不左右增長趨勢，因此可以忽略不計(jì)，上述算法的時(shí)間復(fù)雜度即O(n2)。04算法的復(fù)雜性分析2.空間復(fù)雜性在一般情況下，一個(gè)算法所占用的存儲(chǔ)空間包括算法自身、算法的輸入、算法的輸出及實(shí)現(xiàn)算法的程序在運(yùn)行時(shí)所占用空間的總和。由于算法的輸入和輸出所占用的空間基本上是一個(gè)確定的值，它們不會(huì)隨著算法的不同而不同，而算法自身所占用的空間與實(shí)現(xiàn)算法的語言和使用的語句密切相關(guān)，因此一個(gè)算法的空間復(fù)雜性(空間復(fù)雜度)的度量主要考慮的是算法在運(yùn)行過程中所需要的存儲(chǔ)空間的大小。實(shí)際上，時(shí)間、空間是一對矛盾體，有的時(shí)候不得不為了節(jié)省時(shí)間而消耗空間，有的時(shí)候又不得不為了節(jié)省空間而消耗時(shí)間。04算法的復(fù)雜性分析2.空間復(fù)雜性[例6.12]交換兩個(gè)整數(shù)，可以有如下兩種算法。其中算法1比算法2的空間復(fù)雜度大，但是算法1的通用性強(qiáng)，適合于各種類型的數(shù)據(jù)交換，而算法2只適合于整型數(shù)據(jù)。04算法的復(fù)雜性分析3.設(shè)計(jì)算法時(shí)應(yīng)考慮的原則正確性算法的正確性是指算法至少應(yīng)該能正確反映問題的需求，能夠得到問的正確答案。01可讀性設(shè)計(jì)算法的目的，一方面是讓計(jì)算機(jī)執(zhí)行，另一方面是便于自己和他人閱讀，讓人理解和交流?？勺x性是評判算法好壞很重要的標(biāo)志。0204算法的復(fù)雜性分析3.設(shè)計(jì)算法時(shí)應(yīng)考慮的原則健壯性當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法應(yīng)當(dāng)能恰當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名其妙的輸出結(jié)果。并且算法處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。03高效率與低存儲(chǔ)量算法的效率指的是算法的執(zhí)行時(shí)間，算法的存儲(chǔ)量指的是算法執(zhí)行過程中所需的最大存儲(chǔ)空間。在算法正確、易讀、健壯的情況下，還需要利用數(shù)學(xué)工具，討論其時(shí)間復(fù)雜度和空間復(fù)雜度，探討具體算法對問題的適應(yīng)性。04算法中的數(shù)據(jù)結(jié)構(gòu)02算法中的數(shù)據(jù)結(jié)構(gòu)著名的計(jì)算機(jī)科學(xué)家NiklausWirth曾提出:

程序=算法+數(shù)據(jù)結(jié)構(gòu)這個(gè)公式說明，程序是由算法和數(shù)據(jù)結(jié)構(gòu)兩大要素構(gòu)成的。其中，數(shù)據(jù)結(jié)構(gòu)是指欲處理的數(shù)據(jù)類型和數(shù)據(jù)的組織形式。例如，學(xué)號(hào)、姓名、出生日期等數(shù)據(jù)都具有相應(yīng)的數(shù)據(jù)類型，大量數(shù)據(jù)在計(jì)算機(jī)中存儲(chǔ)時(shí)采用何種組織形式可以帶來更高的運(yùn)行效率或存儲(chǔ)效率，是數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容。算法中的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)為算法服務(wù)算法要作用在特定的數(shù)據(jù)結(jié)構(gòu)之上。例如，常用的二分法查找需要用數(shù)組這種線性存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)數(shù)據(jù)，而鏈表這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是無法使用二分法查找的；在大量的有序數(shù)據(jù)中插入一個(gè)新數(shù)據(jù)后，若欲使數(shù)據(jù)依然保持有序狀態(tài)，那么采用數(shù)組這種線性存儲(chǔ)結(jié)構(gòu)就需要涉及數(shù)據(jù)的后移，之后才能插入新數(shù)據(jù)，而采用鏈表這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)則無須移動(dòng)數(shù)據(jù)，直接插入即可。程序設(shè)計(jì)步驟0301程序/02程序設(shè)計(jì)01程序人們事先編制的一組指令的有序集合。計(jì)算機(jī)系統(tǒng)能完成各種工作的核心就是程序。02程序設(shè)計(jì)程序設(shè)計(jì)是指從人們分析實(shí)際問題開始到計(jì)算機(jī)給出正確結(jié)果的完整過程。03程序設(shè)計(jì)方法程序設(shè)計(jì)方法在很大程度上會(huì)影響程序設(shè)計(jì)的成敗及程序的質(zhì)量。目前，常用的是結(jié)構(gòu)化程序設(shè)計(jì)和面向?qū)ο蟪绦蛟O(shè)計(jì)。無論哪種程序設(shè)計(jì)方法，程序的可靠性、易讀性、高效性、可維護(hù)性等都是衡量程序質(zhì)量的重要標(biāo)準(zhǔn)。03程序設(shè)計(jì)方法1.結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)(StructuredProgramming，SP)思想最早由荷蘭科學(xué)家EWDijikstra在1965年提出，是計(jì)算機(jī)軟件發(fā)展的一個(gè)重要里程碑。自頂向下、逐步求精在進(jìn)行程序設(shè)計(jì)時(shí)，先考慮整體，后考慮細(xì)節(jié);先考慮全局目標(biāo)，后考慮局部目標(biāo):先從最上層總目標(biāo)開始設(shè)計(jì)，逐步使問題具體化，逐步細(xì)化。01模塊化把要解決的總目標(biāo)分解為若干個(gè)子目標(biāo)，進(jìn)一步分解為具體的小目標(biāo),把每一個(gè)小目標(biāo)稱為一個(gè)模塊(函數(shù)):各個(gè)模塊都基于順序、選擇、循環(huán)3種基本控制結(jié)構(gòu)，且具有單入口和單出口;限制使用goto語句在程序中任意跳轉(zhuǎn)。0203程序設(shè)計(jì)方法1.結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序的結(jié)構(gòu)簡單清晰，可讀性好，模塊化強(qiáng)，程序執(zhí)行效率高。但存在如下一些問題。程序的重用性差重用性是指同一事物不經(jīng)修改或稍加修改就可多次重復(fù)使用的性質(zhì)。01程序難以適應(yīng)大型軟件的設(shè)計(jì)在結(jié)構(gòu)化程序設(shè)計(jì)中，算法是一個(gè)獨(dú)立的整體，數(shù)據(jù)結(jié)構(gòu)也是一個(gè)獨(dú)立的整體，二者分開設(shè)計(jì)，以算法為主，即數(shù)據(jù)和處理數(shù)據(jù)分離。因此在大型軟件系統(tǒng)開發(fā)中，程序容易出錯(cuò)，難以維護(hù)。0203程序設(shè)計(jì)方法2.面向?qū)ο蟪绦蛟O(shè)計(jì)面向?qū)ο蟪绦蛟O(shè)計(jì)(ObjectOrientedProgramming，00P)是20世紀(jì)80年代初提出的一種計(jì)算機(jī)編程架構(gòu)，它汲取了結(jié)構(gòu)化程序設(shè)計(jì)中好的思想，并引入了新的概念，盡可能模擬人類的思維方式，采用對象、類、方法、實(shí)例等相關(guān)概念進(jìn)行程序設(shè)計(jì)。面向?qū)ο蟪绦蛟O(shè)計(jì)認(rèn)為現(xiàn)實(shí)世界是由一個(gè)個(gè)對象組成的，構(gòu)成客觀事物的基本單元是對象。當(dāng)解決某個(gè)問題時(shí)，先要確定這個(gè)問題由哪些對象組成。例如，一個(gè)學(xué)校是一個(gè)對象，一個(gè)班級是一個(gè)對象，一個(gè)學(xué)生是一個(gè)對象，而一個(gè)班級又是由若干個(gè)學(xué)生對象組成的，一個(gè)學(xué)校又是由若干個(gè)班級對象和若干個(gè)其他對象組成的。作為對象，一般應(yīng)具備兩個(gè)因素:一個(gè)是從事活動(dòng)的主體，如班級中的若干個(gè)學(xué)生;另一個(gè)是活動(dòng)的內(nèi)容，如上課、開會(huì)等。從計(jì)算機(jī)的角度看，一個(gè)對象一般包括兩個(gè)因素:一個(gè)是數(shù)據(jù)，相當(dāng)于班級中的學(xué)生屬性;另一個(gè)是需要進(jìn)行的操作(函數(shù))，相當(dāng)于班級中學(xué)生進(jìn)行的各種活動(dòng)。對象就是一個(gè)包含數(shù)據(jù)及與這些數(shù)據(jù)有關(guān)的操作集合。03程序設(shè)計(jì)方法2.面向?qū)ο蟪绦蛟O(shè)計(jì)抽象抽象是指對具體問題進(jìn)行概括，提取出一類對象的公共性質(zhì)并加以描述的過程。抽象的過程是對問題進(jìn)行分析和認(rèn)知的過程，這是人類認(rèn)識(shí)世界的基本手段之-抽象的作用是表示同一類事物的本質(zhì)，如不同品牌的電視、不同形狀的桌子等，它們分別屬于同一類事物，所以可以對它們進(jìn)行歸納，找出共同的屬性和行為。01例如，對人類進(jìn)行抽象。通過對人類進(jìn)行歸納、抽象，抽取其中的共性，可得如下結(jié)論。人類的共同屬性:姓名、性別、年齡、身高、體重等。人類的共同行為:吃飯、走路、睡覺等生物性行為:工作、學(xué)習(xí)等社會(huì)性行為。屬性可用變量來表達(dá)。行為可用函數(shù)來表達(dá)。03程序設(shè)計(jì)方法2.面向?qū)ο蟪绦蛟O(shè)計(jì)封裝將抽象得到的數(shù)據(jù)和行為相結(jié)合，形成一個(gè)有機(jī)的整體，即將數(shù)據(jù)和操作數(shù)據(jù)的函數(shù)進(jìn)行有機(jī)的結(jié)合，形成“類”。封裝是面向?qū)ο蟪绦蛟O(shè)計(jì)的一個(gè)重要特點(diǎn)。封裝包含兩個(gè)含義:一是將有關(guān)的數(shù)據(jù)和函數(shù)封裝在一個(gè)對象中，形成一個(gè)基本單位，各個(gè)對象之間相互獨(dú)立，互不干擾:二是將對象中某些部分對外隱蔽，即隱蔽其內(nèi)部細(xì)節(jié)，只留下少量接口，以便與外界聯(lián)系，接收外界的消息。這種對外界隱蔽的做法稱為信息隱蔽。信息隱蔽有利于數(shù)據(jù)安全，防止無關(guān)的人了解和修改數(shù)據(jù)。02封裝改變了傳統(tǒng)方法中數(shù)據(jù)和處理數(shù)據(jù)分離的缺陷。03程序設(shè)計(jì)方法2.面向?qū)ο蟪绦蛟O(shè)計(jì)繼承繼承是面向?qū)ο蟪绦蛟O(shè)計(jì)的又一個(gè)重要特點(diǎn)。只有繼承，才可以在別人認(rèn)識(shí)的基礎(chǔ)之上有所發(fā)現(xiàn)，有所突破，擺脫重復(fù)分析、重復(fù)開發(fā)的困境。例如，如果某汽車制造廠想生產(chǎn)一款新型汽車，一般不會(huì)全部從頭開始設(shè)計(jì)，而是選擇已有的某一型號(hào)汽車為基礎(chǔ)，增加新的功能后形成一款新的汽車，從而提高生產(chǎn)效率，降低成本。這種新產(chǎn)品的研制方式稱為繼承。0303程序設(shè)計(jì)方法2.面向?qū)ο蟪绦蛟O(shè)計(jì)多態(tài)廣義地說，多態(tài)是指一種行為表現(xiàn)出了多種形態(tài)。例如，你“吃飯”，我也“吃飯”，但吃的東西不一樣，所以吃飯的動(dòng)作不同。所謂多態(tài)性，是指由繼承而產(chǎn)生的不同的派生類，其對象對同一消息會(huì)做出不同的響應(yīng)。多態(tài)性也是面向?qū)ο蟪绦蛟O(shè)計(jì)的一個(gè)重要特點(diǎn)，能增加程序的靈活性。04①整個(gè)軟件由各種各樣的對象構(gòu)成。③根據(jù)對象的屬性和運(yùn)動(dòng)規(guī)律的相似性可以將對象分類。②每個(gè)對象都有各自的內(nèi)部狀態(tài)和運(yùn)動(dòng)規(guī)律。④復(fù)雜對象由相對簡單的對象構(gòu)成。03程序設(shè)計(jì)方法2.面向?qū)ο蟪绦蛟O(shè)計(jì)多態(tài)04⑤不同對象的組合及其間的相瓦作用和聯(lián)系構(gòu)成系統(tǒng)。⑥對象間的相互作用通過消息傳遞，對象根據(jù)所接收到的消息做出自身的響應(yīng)。由此可以看出，面向?qū)ο蟪绦蛟O(shè)計(jì)將問題抽象成許多類，將數(shù)據(jù)與對數(shù)據(jù)的操作封裝在一起，各個(gè)類之間可能存在著繼承關(guān)系，對象是類的實(shí)例，程序由對象組成，程序可以被描述為:程序=對象+對象+···+對象，對象=數(shù)據(jù)結(jié)構(gòu)+算法。面向?qū)ο蟪绦蛟O(shè)計(jì)可以較好地克服面向過程程序設(shè)計(jì)存在的問題，使用得好，可以開發(fā)出健壯的、易于擴(kuò)展和維護(hù)的應(yīng)用程序。基于計(jì)算機(jī)的問題求解0401基于計(jì)算機(jī)軟件的問題求解方法在實(shí)際工作中，當(dāng)我們遇到問題時(shí)，首先會(huì)怎么做呢?大多數(shù)人的做法一般都是有意或無意地尋找一些現(xiàn)成的工具。一些計(jì)算機(jī)的通用軟件就是我們的工具。例如，當(dāng)我們需要利用計(jì)算機(jī)處理圖像時(shí)，可以使用圖像處理軟件Photoshop;當(dāng)我們需要處理文檔時(shí)，可以使用字處理軟件Word;當(dāng)我們需要求解擬合問題、等高線、權(quán)限等諸多數(shù)學(xué)問題時(shí)，可以使用商業(yè)數(shù)學(xué)軟件MATLAB:當(dāng)我們發(fā)現(xiàn)計(jì)算機(jī)可能感染病毒時(shí)，可以使用對應(yīng)的殺毒軟件，等等。通用問題與求解問題的相應(yīng)軟件如表6-1所示。02基于計(jì)算機(jī)程序的問題求解方法軟件這么強(qiáng)大，那么所有計(jì)算機(jī)可解的問題都有可用的軟件嗎?顯然不是。無論計(jì)算機(jī)軟件多么