算法設(shè)計(jì)與分析第一章算法概述

1、目目 錄錄前言前言第一篇第一篇 引入篇引入篇 第一章第一章 算法概述算法概述 第二章第二章 算法分析基礎(chǔ)算法分析基礎(chǔ)第二篇第二篇 基礎(chǔ)篇基礎(chǔ)篇 第三章第三章 算法基本工具和優(yōu)化技巧算法基本工具和優(yōu)化技巧第三篇第三篇 核心篇核心篇 第四章第四章 基本的算法策略基本的算法策略 第五章第五章 圖的搜索算法圖的搜索算法第四篇第四篇 應(yīng)用篇應(yīng)用篇 第六章第六章 算法設(shè)計(jì)實(shí)踐算法設(shè)計(jì)實(shí)踐引引 入入 篇篇第一章 算法概述 1.1 1.1 用計(jì)算機(jī)求解問(wèn)題用計(jì)算機(jī)求解問(wèn)題 問(wèn)題求解問(wèn)題求解(problem solving)(problem solving)是個(gè)大課題，它涉是個(gè)大課題，它涉及歸約、推斷、決策、規(guī)

2、劃、常識(shí)推理、定理證明及歸約、推斷、決策、規(guī)劃、常識(shí)推理、定理證明和相關(guān)過(guò)程的核心概念和相關(guān)過(guò)程的核心概念 我們學(xué)習(xí)算法設(shè)計(jì)的我們學(xué)習(xí)算法設(shè)計(jì)的重點(diǎn)重點(diǎn)就是把人類找到的求就是把人類找到的求解問(wèn)題的方法、步驟，以過(guò)程化、形式化、機(jī)械化解問(wèn)題的方法、步驟，以過(guò)程化、形式化、機(jī)械化的形式表示出來(lái)，以便讓計(jì)算機(jī)執(zhí)行。（當(dāng)然人工的形式表示出來(lái)，以便讓計(jì)算機(jī)執(zhí)行。（當(dāng)然人工智能軟件系統(tǒng)也離不開(kāi)智能軟件系統(tǒng)也離不開(kāi)“算法設(shè)計(jì)算法設(shè)計(jì)”這個(gè)最基本的這個(gè)最基本的軟件設(shè)計(jì)環(huán)節(jié)。）就把我們軟件設(shè)計(jì)環(huán)節(jié)。）就把我們學(xué)習(xí)的目標(biāo)學(xué)習(xí)的目標(biāo)定為定為“用計(jì)用計(jì)算機(jī)求解問(wèn)題算機(jī)求解問(wèn)題”。1.1.1 1.1.1 用計(jì)算機(jī)求解問(wèn)

3、題的步驟用計(jì)算機(jī)求解問(wèn)題的步驟 現(xiàn)實(shí)中，在解決一個(gè)問(wèn)題時(shí)，根據(jù)不同的經(jīng)驗(yàn)，不同的現(xiàn)實(shí)中，在解決一個(gè)問(wèn)題時(shí)，根據(jù)不同的經(jīng)驗(yàn)，不同的環(huán)境會(huì)采用不同的方法，用計(jì)算機(jī)解決現(xiàn)實(shí)中的問(wèn)題，同樣環(huán)境會(huì)采用不同的方法，用計(jì)算機(jī)解決現(xiàn)實(shí)中的問(wèn)題，同樣也有很多不同的方法，但解決問(wèn)題的基本步驟是相同的。也有很多不同的方法，但解決問(wèn)題的基本步驟是相同的。下面給出用計(jì)算機(jī)求解問(wèn)題的一般步驟。下面給出用計(jì)算機(jī)求解問(wèn)題的一般步驟。1. 1. 問(wèn)題分析問(wèn)題分析 準(zhǔn)確、完整地準(zhǔn)確、完整地理解和描述問(wèn)題理解和描述問(wèn)題是解決問(wèn)題的第一步。是解決問(wèn)題的第一步。要做到這一點(diǎn)，必須注意以下一些問(wèn)題：在未經(jīng)加工的原始要做到這一點(diǎn)，必須注意

4、以下一些問(wèn)題：在未經(jīng)加工的原始表達(dá)中，所用的術(shù)語(yǔ)是否都明白其準(zhǔn)確定義？題目提供了哪表達(dá)中，所用的術(shù)語(yǔ)是否都明白其準(zhǔn)確定義？題目提供了哪些信息？這些信息有什么用？題目要求得到什么結(jié)果？題目些信息？這些信息有什么用？題目要求得到什么結(jié)果？題目中作了哪些假定？是否有潛在的信息？判定求解結(jié)果所需要中作了哪些假定？是否有潛在的信息？判定求解結(jié)果所需要的中間結(jié)果有哪些？等等。針對(duì)每個(gè)具體的問(wèn)題，必須認(rèn)真的中間結(jié)果有哪些？等等。針對(duì)每個(gè)具體的問(wèn)題，必須認(rèn)真審查問(wèn)題描述，理解問(wèn)題的真實(shí)要求。審查問(wèn)題描述，理解問(wèn)題的真實(shí)要求。2 2、數(shù)學(xué)模型建立、數(shù)學(xué)模型建立 用計(jì)算機(jī)解決實(shí)際問(wèn)題必須有合適的數(shù)學(xué)模型，因?yàn)橛糜?jì)

5、算機(jī)解決實(shí)際問(wèn)題必須有合適的數(shù)學(xué)模型，因?yàn)樵诂F(xiàn)實(shí)問(wèn)題面前，計(jì)算機(jī)是無(wú)能為力。在現(xiàn)實(shí)問(wèn)題面前，計(jì)算機(jī)是無(wú)能為力。對(duì)一個(gè)實(shí)際問(wèn)題建立數(shù)學(xué)模型，可以考慮這樣兩個(gè)基對(duì)一個(gè)實(shí)際問(wèn)題建立數(shù)學(xué)模型，可以考慮這樣兩個(gè)基本問(wèn)題：最適合于此問(wèn)題的數(shù)學(xué)模型是什么？是否有已經(jīng)解本問(wèn)題：最適合于此問(wèn)題的數(shù)學(xué)模型是什么？是否有已經(jīng)解決了的類似問(wèn)題可借鑒？決了的類似問(wèn)題可借鑒？ 如果上述第二個(gè)問(wèn)題的答復(fù)是肯定的如果上述第二個(gè)問(wèn)題的答復(fù)是肯定的, ,那么通過(guò)類似的那么通過(guò)類似的問(wèn)題的分析、比較和聯(lián)想，可加速問(wèn)題的解決。問(wèn)題的分析、比較和聯(lián)想，可加速問(wèn)題的解決。 3 3、算法設(shè)計(jì)與選擇、算法設(shè)計(jì)與選擇 算法設(shè)計(jì)是指設(shè)計(jì)求解某一

6、特定類型問(wèn)題的一系列步算法設(shè)計(jì)是指設(shè)計(jì)求解某一特定類型問(wèn)題的一系列步驟，并且這些步驟是可以通過(guò)計(jì)算機(jī)的基本操作來(lái)實(shí)現(xiàn)的。驟，并且這些步驟是可以通過(guò)計(jì)算機(jī)的基本操作來(lái)實(shí)現(xiàn)的。算法設(shè)計(jì)要同時(shí)結(jié)合數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)，簡(jiǎn)單說(shuō)數(shù)據(jù)結(jié)算法設(shè)計(jì)要同時(shí)結(jié)合數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)，簡(jiǎn)單說(shuō)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)就是選取存儲(chǔ)方式。算法的設(shè)計(jì)與模型的選擇更是構(gòu)的設(shè)計(jì)就是選取存儲(chǔ)方式。算法的設(shè)計(jì)與模型的選擇更是密切相關(guān)的，但同一模型仍然可以有不同的算法，而且它們密切相關(guān)的，但同一模型仍然可以有不同的算法，而且它們的有效性可能有相當(dāng)大的差距。的有效性可能有相當(dāng)大的差距。*在這些步驟中，算法設(shè)計(jì)是解決問(wèn)題的核心。在這些步驟中，算法設(shè)計(jì)是解決問(wèn)

7、題的核心。 4 4、算法分析、算法分析 算法分析的目的，首先為了對(duì)算法的某些特定輸入，算法分析的目的，首先為了對(duì)算法的某些特定輸入，估算該算法所需的內(nèi)存空間和運(yùn)行時(shí)間；其次是為了建立衡估算該算法所需的內(nèi)存空間和運(yùn)行時(shí)間；其次是為了建立衡量算法優(yōu)劣的標(biāo)準(zhǔn)，用以比較同一類問(wèn)題的不同算法。通常量算法優(yōu)劣的標(biāo)準(zhǔn)，用以比較同一類問(wèn)題的不同算法。通常將時(shí)間和空間的增長(zhǎng)率作為衡量的標(biāo)準(zhǔn)。另參見(jiàn)將時(shí)間和空間的增長(zhǎng)率作為衡量的標(biāo)準(zhǔn)。另參見(jiàn)1 11 14 4算算法及其設(shè)計(jì)的評(píng)價(jià)法及其設(shè)計(jì)的評(píng)價(jià)5 5、算法表示、算法表示 對(duì)于復(fù)雜的問(wèn)題，確定算法后可以通過(guò)圖形準(zhǔn)確表示對(duì)于復(fù)雜的問(wèn)題，確定算法后可以通過(guò)圖形準(zhǔn)確表示算

8、法。算法的表示方式很多如：算法流程圖、盒圖、算法。算法的表示方式很多如：算法流程圖、盒圖、PADPAD圖圖和偽碼（類似于程序設(shè)計(jì)語(yǔ)言）等。和偽碼（類似于程序設(shè)計(jì)語(yǔ)言）等。 6 6、算法實(shí)現(xiàn)、算法實(shí)現(xiàn) 根據(jù)選用的程序設(shè)計(jì)語(yǔ)言，要解決下列一些問(wèn)題：有根據(jù)選用的程序設(shè)計(jì)語(yǔ)言，要解決下列一些問(wèn)題：有哪些變量，它們是什么類型？需要多少數(shù)組，規(guī)模有多大？哪些變量，它們是什么類型？需要多少數(shù)組，規(guī)模有多大？用什么結(jié)構(gòu)來(lái)組織數(shù)據(jù)？需要哪些子算法？等等。用什么結(jié)構(gòu)來(lái)組織數(shù)據(jù)？需要哪些子算法？等等。 算法的實(shí)現(xiàn)方式，對(duì)運(yùn)算速度和所需內(nèi)存容量都有很大算法的實(shí)現(xiàn)方式，對(duì)運(yùn)算速度和所需內(nèi)存容量都有很大影響。影響。7 7

9、、程序測(cè)試、程序測(cè)試 算法測(cè)試的實(shí)質(zhì)是對(duì)算法應(yīng)完成任務(wù)的實(shí)驗(yàn)證實(shí)，同算法測(cè)試的實(shí)質(zhì)是對(duì)算法應(yīng)完成任務(wù)的實(shí)驗(yàn)證實(shí)，同時(shí)確定算法的使用范圍。測(cè)試方法一般有兩種：白盒測(cè)試對(duì)時(shí)確定算法的使用范圍。測(cè)試方法一般有兩種：白盒測(cè)試對(duì)算法的各個(gè)分支進(jìn)行測(cè)試；黑盒測(cè)試檢驗(yàn)對(duì)給定的輸入是否算法的各個(gè)分支進(jìn)行測(cè)試；黑盒測(cè)試檢驗(yàn)對(duì)給定的輸入是否有指定輸出。有指定輸出。 如何選擇算法測(cè)試中的輸入，還沒(méi)有一般答案。通常采如何選擇算法測(cè)試中的輸入，還沒(méi)有一般答案。通常采用的方法是，對(duì)輸入數(shù)據(jù)做有代表性的采樣，使之對(duì)被測(cè)試用的方法是，對(duì)輸入數(shù)據(jù)做有代表性的采樣，使之對(duì)被測(cè)試算法的各個(gè)語(yǔ)句、分支和路徑盡可能都被檢查到。對(duì)輸入集

10、算法的各個(gè)語(yǔ)句、分支和路徑盡可能都被檢查到。對(duì)輸入集中的邊界點(diǎn)也要進(jìn)行測(cè)試。經(jīng)測(cè)試驗(yàn)證是否正確的算法，在中的邊界點(diǎn)也要進(jìn)行測(cè)試。經(jīng)測(cè)試驗(yàn)證是否正確的算法，在較大程度上是可以相信它的正確性。較大程度上是可以相信它的正確性。、結(jié)果整理文檔編制、結(jié)果整理文檔編制編制文檔的目的是讓人了解你編寫(xiě)的算法。首先要把編制文檔的目的是讓人了解你編寫(xiě)的算法。首先要把代碼編寫(xiě)清楚。代碼本身就是文檔。同時(shí)還要采用注釋的方代碼編寫(xiě)清楚。代碼本身就是文檔。同時(shí)還要采用注釋的方式，另外還包括算法的流程圖，自頂向下各研制階段的有關(guān)式，另外還包括算法的流程圖，自頂向下各研制階段的有關(guān)記錄，算法的正確性證明（或論述），算法測(cè)試結(jié)

11、果，對(duì)輸記錄，算法的正確性證明（或論述），算法測(cè)試結(jié)果，對(duì)輸入入/ /輸出的要求及格式的詳細(xì)描述等。輸出的要求及格式的詳細(xì)描述等。1.1.2 1.1.2 算法及其要素和特性算法及其要素和特性、算法的定義、算法的定義算法是指在解決問(wèn)題時(shí)，按照某種機(jī)械步驟一定可以算法是指在解決問(wèn)題時(shí)，按照某種機(jī)械步驟一定可以得到問(wèn)題結(jié)果的處理過(guò)程。當(dāng)面臨某個(gè)問(wèn)題時(shí)，需要找到用得到問(wèn)題結(jié)果的處理過(guò)程。當(dāng)面臨某個(gè)問(wèn)題時(shí)，需要找到用計(jì)算機(jī)解決這個(gè)問(wèn)題的方法和步驟，計(jì)算機(jī)解決這個(gè)問(wèn)題的方法和步驟，算法就是對(duì)解決這個(gè)問(wèn)算法就是對(duì)解決這個(gè)問(wèn)題的方法和步驟的描述題的方法和步驟的描述,是指令的有限序列是指令的有限序列。 機(jī)械步驟

12、是指，算法中有待執(zhí)行的運(yùn)算和操機(jī)械步驟是指，算法中有待執(zhí)行的運(yùn)算和操作，必須是相當(dāng)基本的。換言之，它們都是能夠作，必須是相當(dāng)基本的。換言之，它們都是能夠精確地運(yùn)行的算法，執(zhí)行者甚至不需要掌握算法精確地運(yùn)行的算法，執(zhí)行者甚至不需要掌握算法的含義，即可根據(jù)該算法的每一步驟要求，進(jìn)行的含義，即可根據(jù)該算法的每一步驟要求，進(jìn)行操作并最終得出正確的結(jié)果。操作并最終得出正確的結(jié)果。2 2算法的要素算法的要素 算法由算法由操作、控制結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)操作、控制結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)三要素組三要素組成。成。 1 1）操作）操作 算術(shù)運(yùn)算：加、減、乘、除算術(shù)運(yùn)算：加、減、乘、除 關(guān)系比較：大于、小于、等于、不等于關(guān)系比較：

13、大于、小于、等于、不等于 邏輯運(yùn)算：與、或、非邏輯運(yùn)算：與、或、非 數(shù)據(jù)傳送：輸入、輸出數(shù)據(jù)傳送：輸入、輸出, , 賦值賦值2 2）控制結(jié)構(gòu)）控制結(jié)構(gòu) 各操作之間的執(zhí)行次序。各操作之間的執(zhí)行次序。 順序結(jié)構(gòu)：各操作依次執(zhí)行順序結(jié)構(gòu)：各操作依次執(zhí)行 選擇結(jié)構(gòu)：由條件是否成立來(lái)選擇選擇結(jié)構(gòu)：由條件是否成立來(lái)選擇 執(zhí)行執(zhí)行 循環(huán)結(jié)構(gòu)：有些操作要重復(fù)執(zhí)行，直到功循環(huán)結(jié)構(gòu)：有些操作要重復(fù)執(zhí)行，直到功能滿足某個(gè)條件時(shí)結(jié)束。又稱重復(fù)或迭代結(jié)構(gòu)。能滿足某個(gè)條件時(shí)結(jié)束。又稱重復(fù)或迭代結(jié)構(gòu)。注意：注意： 模塊間的調(diào)用也是一種控制結(jié)構(gòu)，特別模塊間的調(diào)用也是一種控制結(jié)構(gòu)，特別 地模地模塊自身的直接或間接調(diào)用塊自身的直

14、接或間接調(diào)用遞歸結(jié)構(gòu)，是一種功能遞歸結(jié)構(gòu)，是一種功能很強(qiáng)的控制結(jié)構(gòu)。很強(qiáng)的控制結(jié)構(gòu)。3 3）數(shù)據(jù)結(jié)構(gòu)）數(shù)據(jù)結(jié)構(gòu) 算法操作的對(duì)象是數(shù)據(jù)，數(shù)據(jù)間的邏輯關(guān)算法操作的對(duì)象是數(shù)據(jù)，數(shù)據(jù)間的邏輯關(guān)系、數(shù)據(jù)的存儲(chǔ)方式及處理方式就是數(shù)據(jù)的數(shù)據(jù)系、數(shù)據(jù)的存儲(chǔ)方式及處理方式就是數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。它與算法設(shè)計(jì)是緊密相關(guān)的。結(jié)構(gòu)。它與算法設(shè)計(jì)是緊密相關(guān)的。注意：注意： 算法是把人類找到的求解問(wèn)題的方法，算法是把人類找到的求解問(wèn)題的方法，用以上要素過(guò)程化、形式化、機(jī)械化地表示出來(lái)。用以上要素過(guò)程化、形式化、機(jī)械化地表示出來(lái)。在算法的表示中要滿足以下的性質(zhì)：在算法的表示中要滿足以下的性質(zhì)：目的性目的性 算法有明確的目的，能

15、完成賦予它的功能算法有明確的目的，能完成賦予它的功能分步性分步性 算法為完成其復(fù)雜的功能，由一系列計(jì)算機(jī)可執(zhí)算法為完成其復(fù)雜的功能，由一系列計(jì)算機(jī)可執(zhí) 行的步驟組成行的步驟組成有序性有序性 算法的步驟是有序的，不可隨意改變算法步驟的算法的步驟是有序的，不可隨意改變算法步驟的 執(zhí)行順序執(zhí)行順序有限性有限性 算法是有限的指令序列，所包含步驟也是有限的算法是有限的指令序列，所包含步驟也是有限的 操作性操作性 算法是有限的指令序列，算法所包含的步驟是有算法是有限的指令序列，算法所包含的步驟是有 限的限的 3. 3. 算法的基本性質(zhì)算法的基本性質(zhì)4. 4. 算法的地位算法的地位 算法是計(jì)算機(jī)學(xué)科中最具有

16、方法論性質(zhì)的核算法是計(jì)算機(jī)學(xué)科中最具有方法論性質(zhì)的核心概念，也被譽(yù)為計(jì)算機(jī)學(xué)科的靈魂。心概念，也被譽(yù)為計(jì)算機(jī)學(xué)科的靈魂。5. 5. 算法的基本特征算法的基本特征有窮性有窮性 一個(gè)算法在執(zhí)行有窮步之后必須結(jié)束。也就是說(shuō)一一個(gè)算法在執(zhí)行有窮步之后必須結(jié)束。也就是說(shuō)一個(gè)算法它所包含的計(jì)算步驟是有限的而且每個(gè)步驟都能個(gè)算法它所包含的計(jì)算步驟是有限的而且每個(gè)步驟都能在有限時(shí)間內(nèi)完成。在有限時(shí)間內(nèi)完成。確定性確定性 對(duì)于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確對(duì)于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行

17、。并且在任何條件下，算法都只有一條執(zhí)行路如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑。徑?？尚行钥尚行?算法中描述的操作都可以通過(guò)已經(jīng)實(shí)現(xiàn)的算法中描述的操作都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)?；静僮鬟\(yùn)算有限次實(shí)現(xiàn)。算法有零個(gè)或多個(gè)的輸入算法有零個(gè)或多個(gè)的輸入 有些輸入量需要在算法執(zhí)行過(guò)程中輸入，有些輸入量需要在算法執(zhí)行過(guò)程中輸入，而有的算法表面上可以沒(méi)有輸入，實(shí)際上已被嵌而有的算法表面上可以沒(méi)有輸入，實(shí)際上已被嵌入算法之中。入算法之中。算法有一個(gè)或多個(gè)的輸出算法有一個(gè)或多個(gè)的輸出 它是一組與輸入有確定關(guān)系的量值，是算它是一組與輸入有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果

18、。法進(jìn)行信息加工后得到的結(jié)果。1.1.3 1.1.3 算法設(shè)計(jì)及基本方法算法設(shè)計(jì)及基本方法1. 1. 算法設(shè)計(jì)的概念算法設(shè)計(jì)的概念 算法設(shè)計(jì)算法設(shè)計(jì)作為用計(jì)算機(jī)解決問(wèn)題的一個(gè)步驟作為用計(jì)算機(jī)解決問(wèn)題的一個(gè)步驟, ,其任務(wù)是對(duì)各類具體問(wèn)題設(shè)計(jì)良好的算法其任務(wù)是對(duì)各類具體問(wèn)題設(shè)計(jì)良好的算法; ;作為作為一門(mén)課程，是研究設(shè)計(jì)算法的規(guī)律和方法。一門(mén)課程，是研究設(shè)計(jì)算法的規(guī)律和方法。2 2算法設(shè)計(jì)應(yīng)注意的問(wèn)題算法設(shè)計(jì)應(yīng)注意的問(wèn)題 1 1）正確性（）正確性（CorrectnessCorrectness） 一切合法的輸入數(shù)據(jù)都能得出滿足要求的結(jié)一切合法的輸入數(shù)據(jù)都能得出滿足要求的結(jié)果；典型、苛刻的幾組輸入數(shù)

19、據(jù)也能夠得出滿足果；典型、苛刻的幾組輸入數(shù)據(jù)也能夠得出滿足要求的結(jié)果。要求的結(jié)果。 2 2）可讀性）可讀性(Readability)(Readability) 算法應(yīng)該易于人的理解；晦澀難讀的算法易算法應(yīng)該易于人的理解；晦澀難讀的算法易于隱藏較多錯(cuò)誤而難以調(diào)試。于隱藏較多錯(cuò)誤而難以調(diào)試。 3 3）健壯性（）健壯性（RubustnessRubustness） 算法的異常情況。處理出錯(cuò)的方法是返回一算法的異常情況。處理出錯(cuò)的方法是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。層次上進(jìn)行處理。 4 4）高效率與低存儲(chǔ)量需求）高效率與低存儲(chǔ)量

20、需求 效率指的是算法執(zhí)行時(shí)間；存儲(chǔ)量指的是算效率指的是算法執(zhí)行時(shí)間；存儲(chǔ)量指的是算法執(zhí)行過(guò)程中所需的最大存儲(chǔ)空間。法執(zhí)行過(guò)程中所需的最大存儲(chǔ)空間。3算法設(shè)計(jì)的基本方法算法設(shè)計(jì)的基本方法 1 1）結(jié)構(gòu)化方法）結(jié)構(gòu)化方法“自頂向下自頂向下, , 逐步求精逐步求精” 結(jié)構(gòu)化方法總的指導(dǎo)思想是自頂向下、逐步求精。它的基本結(jié)構(gòu)化方法總的指導(dǎo)思想是自頂向下、逐步求精。它的基本原則是功能的分解與模塊化原則是功能的分解與模塊化 所謂所謂“自頂向下自頂向下” 是將現(xiàn)實(shí)世界的問(wèn)題經(jīng)抽象轉(zhuǎn)化為邏輯是將現(xiàn)實(shí)世界的問(wèn)題經(jīng)抽象轉(zhuǎn)化為邏輯空間或求解空間的問(wèn)題。是將復(fù)雜且大的問(wèn)題劃分為較小問(wèn)題，空間或求解空間的問(wèn)題。是將復(fù)雜

21、且大的問(wèn)題劃分為較小問(wèn)題，找出問(wèn)題的關(guān)鍵和重點(diǎn)，然后抽象、概括地描述問(wèn)題。找出問(wèn)題的關(guān)鍵和重點(diǎn)，然后抽象、概括地描述問(wèn)題。 所謂所謂“逐步求精逐步求精” 是將復(fù)雜問(wèn)題經(jīng)抽象化處理變?yōu)橄鄬?duì)比是將復(fù)雜問(wèn)題經(jīng)抽象化處理變?yōu)橄鄬?duì)比較簡(jiǎn)單的問(wèn)題。經(jīng)若干步精化處理，最后細(xì)化到用較簡(jiǎn)單的問(wèn)題。經(jīng)若干步精化處理，最后細(xì)化到用“三種基本結(jié)三種基本結(jié)構(gòu)構(gòu)”及基本操作去描述算法。及基本操作去描述算法。結(jié)構(gòu)算法設(shè)計(jì)技術(shù)的優(yōu)越性結(jié)構(gòu)算法設(shè)計(jì)技術(shù)的優(yōu)越性: : 符合人類解決復(fù)雜問(wèn)題的普遍規(guī)律符合人類解決復(fù)雜問(wèn)題的普遍規(guī)律 。 用先全局后局部、先整體后細(xì)節(jié)、先用先全局后局部、先整體后細(xì)節(jié)、先 抽象后具體的逐步求精過(guò)程開(kāi)發(fā)出

22、的抽象后具體的逐步求精過(guò)程開(kāi)發(fā)出的 算法有清晰的層次結(jié)構(gòu)算法有清晰的層次結(jié)構(gòu) 。2) 2) 面向?qū)ο蠓椒嫦驅(qū)ο蠓椒?對(duì)象對(duì)象= =數(shù)據(jù)數(shù)據(jù)+ +對(duì)數(shù)據(jù)操作的代碼實(shí)體對(duì)數(shù)據(jù)操作的代碼實(shí)體 面向?qū)ο笏惴ㄔO(shè)計(jì)方法的過(guò)程包括以下步驟：面向?qū)ο笏惴ㄔO(shè)計(jì)方法的過(guò)程包括以下步驟： 在給定的抽象層次上識(shí)別類和對(duì)象在給定的抽象層次上識(shí)別類和對(duì)象 識(shí)別這些對(duì)象和類的語(yǔ)義識(shí)別這些對(duì)象和類的語(yǔ)義 識(shí)別類和對(duì)象之間的關(guān)系識(shí)別類和對(duì)象之間的關(guān)系 實(shí)現(xiàn)類和對(duì)象實(shí)現(xiàn)類和對(duì)象面向?qū)ο蠓椒ǖ奶卣髦饕嫦驅(qū)ο蠓椒ǖ奶卣髦饕? : 抽象化抽象化 將各種獨(dú)立的操作分解成為可以用命將各種獨(dú)立的操作分解成為可以用命名區(qū)分的單元。

23、名區(qū)分的單元。 封裝性封裝性 不同的操作具有不同的作用范圍。不同的操作具有不同的作用范圍。 多態(tài)性多態(tài)性 對(duì)于不同數(shù)據(jù)類型的相似操作使用相同對(duì)于不同數(shù)據(jù)類型的相似操作使用相同的名。的名。 繼承性繼承性 類可以被繼承。類可以被繼承。 重用重用是面向?qū)ο蟮囊粋€(gè)重要優(yōu)點(diǎn)。最大特點(diǎn)是是面向?qū)ο蟮囊粋€(gè)重要優(yōu)點(diǎn)。最大特點(diǎn)是能夠大幅度的提高軟件項(xiàng)目的成功率，減少日能夠大幅度的提高軟件項(xiàng)目的成功率，減少日后的維護(hù)費(fèi)用，提高軟件的可移植性和可靠性。后的維護(hù)費(fèi)用，提高軟件的可移植性和可靠性。3 3）本書(shū)采用的設(shè)計(jì)方法）本書(shū)采用的設(shè)計(jì)方法結(jié)構(gòu)化設(shè)計(jì)方法結(jié)構(gòu)化設(shè)計(jì)方法 （1 1）自頂向下）自頂向下從抽象到具體從抽象到

24、具體 把一個(gè)較大的算法劃分為若干子模塊把一個(gè)較大的算法劃分為若干子模塊 每一個(gè)模塊可繼續(xù)劃分為更小的子模塊每一個(gè)模塊可繼續(xù)劃分為更小的子模塊 直到用三種控制結(jié)構(gòu)和具體操作表示算直到用三種控制結(jié)構(gòu)和具體操作表示算 法法注：注：運(yùn)用這種編程方法，考慮問(wèn)題必須先進(jìn)行運(yùn)用這種編程方法，考慮問(wèn)題必須先進(jìn)行整體分析。整體分析。（2 2）模塊劃分的基本要求）模塊劃分的基本要求 模塊的功能盡可能地單一化、明確化模塊的功能盡可能地單一化、明確化 模塊間的聯(lián)系及相互影響盡可能地小模塊間的聯(lián)系及相互影響盡可能地小 模塊的規(guī)模應(yīng)當(dāng)足夠小，以便于調(diào)試模塊的規(guī)模應(yīng)當(dāng)足夠小，以便于調(diào)試 原則是簡(jiǎn)單性、獨(dú)立性和完整性原則是簡(jiǎn)

25、單性、獨(dú)立性和完整性。（3）模塊間的接口問(wèn)題）模塊間的接口問(wèn)題 傳遞方式一般有以下幾種：傳遞方式一般有以下幾種： 按名共享：全局變量按名共享：全局變量 子模塊返回調(diào)用模塊信息：子模塊名子模塊返回調(diào)用模塊信息：子模塊名 調(diào)用模塊傳遞給子模塊信息：值參數(shù)傳遞調(diào)用模塊傳遞給子模塊信息：值參數(shù)傳遞 調(diào)用模塊與子模塊互相傳遞信息：變量參數(shù)傳遞調(diào)用模塊與子模塊互相傳遞信息：變量參數(shù)傳遞(C(C語(yǔ)言沒(méi)有此種傳遞方語(yǔ)言沒(méi)有此種傳遞方,Pascal,Pascal、C+C+語(yǔ)言提供此類參數(shù)語(yǔ)言提供此類參數(shù)) ) 按地址共享變量：地址參數(shù)傳遞（參數(shù)為指針變量按地址共享變量：地址參數(shù)傳遞（參數(shù)為指針變量名、數(shù)組名，變

26、量地址）名、數(shù)組名，變量地址）（4 4）算法細(xì)節(jié)設(shè)計(jì)的基本方法算法細(xì)節(jié)設(shè)計(jì)的基本方法從具體到抽象從具體到抽象 設(shè)計(jì)算法設(shè)計(jì)算法“如何做如何做”的細(xì)節(jié)是比較容易出錯(cuò)的，如：循環(huán)的細(xì)節(jié)是比較容易出錯(cuò)的，如：循環(huán)變量的初始值或終值，數(shù)組的下標(biāo)與循環(huán)變量間的關(guān)系等算法變量的初始值或終值，數(shù)組的下標(biāo)與循環(huán)變量間的關(guān)系等算法細(xì)節(jié)的確定。最基本的方法是通過(guò)細(xì)節(jié)的確定。最基本的方法是通過(guò)“枚舉枚舉”一些真實(shí)數(shù)據(jù)，從一些真實(shí)數(shù)據(jù)，從具體的實(shí)例中，抽象具體的實(shí)例中，抽象“歸納歸納”出算法的這些細(xì)節(jié)。出算法的這些細(xì)節(jié)。 （5 5）算法的正確性）算法的正確性 算法的正確性算法的正確性不容易證明。即使可以證明，不容易證

27、明。即使可以證明，所涉及的數(shù)學(xué)理論和推導(dǎo)證明過(guò)程也很復(fù)雜。所涉及的數(shù)學(xué)理論和推導(dǎo)證明過(guò)程也很復(fù)雜。 設(shè)計(jì)算法時(shí)力爭(zhēng)嚴(yán)謹(jǐn)、考慮周全，可能的情設(shè)計(jì)算法時(shí)力爭(zhēng)嚴(yán)謹(jǐn)、考慮周全，可能的情況下，分析論證算法設(shè)計(jì)的合理性，況下，分析論證算法設(shè)計(jì)的合理性，最后在算法最后在算法實(shí)現(xiàn)后，靠大量的測(cè)試，以保證算法的正確性。實(shí)現(xiàn)后，靠大量的測(cè)試，以保證算法的正確性。1.1.4 1.1.4 從算法到實(shí)現(xiàn)從算法到實(shí)現(xiàn) 從算法到實(shí)現(xiàn)應(yīng)注意的問(wèn)題有：從算法到實(shí)現(xiàn)應(yīng)注意的問(wèn)題有： 1. 1. 數(shù)據(jù)類型的選擇數(shù)據(jù)類型的選擇 類型的選擇主要取決于你解決問(wèn)題中數(shù)據(jù)的類型的選擇主要取決于你解決問(wèn)題中數(shù)據(jù)的實(shí)際情況。實(shí)際情況。 這部分知

28、識(shí)不屬于本書(shū)的必要內(nèi)容。在此進(jìn)行簡(jiǎn)這部分知識(shí)不屬于本書(shū)的必要內(nèi)容。在此進(jìn)行簡(jiǎn)述是為了讓讀者在學(xué)習(xí)算法設(shè)計(jì)過(guò)程中上機(jī)實(shí)驗(yàn)時(shí)，述是為了讓讀者在學(xué)習(xí)算法設(shè)計(jì)過(guò)程中上機(jī)實(shí)驗(yàn)時(shí)，不要走太多彎路。不要走太多彎路。 2 2 計(jì)算過(guò)程的差異計(jì)算過(guò)程的差異 運(yùn)算符號(hào)的差異運(yùn)算符號(hào)的差異 運(yùn)算符優(yōu)先級(jí)的差異運(yùn)算符優(yōu)先級(jí)的差異 標(biāo)識(shí)符命名方式的差異標(biāo)識(shí)符命名方式的差異 循環(huán)方式的差異循環(huán)方式的差異 3. 3. 結(jié)果的輸出格式結(jié)果的輸出格式 如：如：矩陣輸出時(shí)上、下行的數(shù)據(jù)應(yīng)該對(duì)齊。矩陣輸出時(shí)上、下行的數(shù)據(jù)應(yīng)該對(duì)齊。 4. 4. 算法實(shí)現(xiàn)后的測(cè)試、調(diào)試算法實(shí)現(xiàn)后的測(cè)試、調(diào)試 測(cè)試就是要發(fā)現(xiàn)算法是否存在問(wèn)題。測(cè)試就測(cè)試

29、就是要發(fā)現(xiàn)算法是否存在問(wèn)題。測(cè)試就是要找到出現(xiàn)問(wèn)題的原因并改正它。然后還需要是要找到出現(xiàn)問(wèn)題的原因并改正它。然后還需要進(jìn)行回歸測(cè)試，以確保算法的正確性。進(jìn)行回歸測(cè)試，以確保算法的正確性。1.2 1.2 算法描述算法描述1.2.1 1.2.1 算法描述簡(jiǎn)介算法描述簡(jiǎn)介算法是對(duì)解題過(guò)程的精確描述。算法是對(duì)解題過(guò)程的精確描述。 算法算法 = = 控制結(jié)構(gòu)控制結(jié)構(gòu) + + 原操作原操作 表示算法的語(yǔ)言主要有：自然語(yǔ)言、流程圖、表示算法的語(yǔ)言主要有：自然語(yǔ)言、流程圖、盒圖、盒圖、PADPAD圖、偽代碼和計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言等。圖、偽代碼和計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言等。1 1自然語(yǔ)言自然語(yǔ)言 自然語(yǔ)言是人們?nèi)粘Ｋ?/p>

30、的語(yǔ)言。其缺點(diǎn)是：自然語(yǔ)言是人們?nèi)粘Ｋ玫恼Z(yǔ)言。其缺點(diǎn)是： 由于自然語(yǔ)言的歧義性容易導(dǎo)致算法執(zhí)行的不確定性。由于自然語(yǔ)言的歧義性容易導(dǎo)致算法執(zhí)行的不確定性。 自然語(yǔ)言的語(yǔ)句一般太長(zhǎng)從而導(dǎo)致了用自然語(yǔ)言描述自然語(yǔ)言的語(yǔ)句一般太長(zhǎng)從而導(dǎo)致了用自然語(yǔ)言描述的算法太長(zhǎng)。的算法太長(zhǎng)。 當(dāng)一個(gè)算法中循環(huán)和分支較多時(shí)就很難清晰地表示出當(dāng)一個(gè)算法中循環(huán)和分支較多時(shí)就很難清晰地表示出來(lái)。來(lái)。 自然語(yǔ)言表示的算法不便翻譯成計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言自然語(yǔ)言表示的算法不便翻譯成計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言理解的語(yǔ)言。理解的語(yǔ)言。2 2流程圖流程圖 流程圖可以表示任何算法的邏輯結(jié)構(gòu)。流程圖可以表示任何算法的邏輯結(jié)構(gòu)。 1) 1) 基本

31、組件基本組件 算法的算法的 加工、處理加工、處理 條件條件 控制流控制流 連接點(diǎn)連接點(diǎn) 入口和出口入口和出口2 2）三種基本控制結(jié)構(gòu)）三種基本控制結(jié)構(gòu) 順序結(jié)構(gòu)：順序結(jié)構(gòu)： 選擇結(jié)構(gòu)IF THEN ELSE型分支 DOCASE型多分支 循環(huán)結(jié)構(gòu) DOWHILE型循環(huán) DOUNTIL循環(huán)結(jié)構(gòu)3) 3) 算法流程圖的主要缺點(diǎn)算法流程圖的主要缺點(diǎn) 不是逐步求精的好工具，它誘使算法員過(guò)不是逐步求精的好工具，它誘使算法員過(guò)早地考慮算法的控制流程，而不去考慮算法的全早地考慮算法的控制流程，而不去考慮算法的全局結(jié)構(gòu)。局結(jié)構(gòu)。 隨意性太強(qiáng)，結(jié)構(gòu)化不明顯。隨意性太強(qiáng)，結(jié)構(gòu)化不明顯。 不易表示數(shù)據(jù)結(jié)構(gòu)。不易表示數(shù)

32、據(jù)結(jié)構(gòu)。 流程圖的層次感不明顯流程圖的層次感不明顯, ,并且當(dāng)問(wèn)題復(fù)雜并且當(dāng)問(wèn)題復(fù)雜程序大時(shí)，優(yōu)勢(shì)基本沒(méi)有。程序大時(shí)，優(yōu)勢(shì)基本沒(méi)有。3 3盒圖（盒圖（NSNS流程圖）流程圖） （1 1）盒圖具有以下優(yōu)點(diǎn)：）盒圖具有以下優(yōu)點(diǎn)： 層次感強(qiáng)、嵌套明確層次感強(qiáng)、嵌套明確 支持自頂向下、逐步求精。支持自頂向下、逐步求精。 容易轉(zhuǎn)換成高級(jí)語(yǔ)言源算法容易轉(zhuǎn)換成高級(jí)語(yǔ)言源算法（2 2）三種基本控制結(jié)）三種基本控制結(jié)構(gòu)構(gòu) 順序結(jié)構(gòu)順序結(jié)構(gòu)A AB B 選擇結(jié)構(gòu)選擇結(jié)構(gòu) P PP1P1P2P2P2P2PnPnA1A1A2A2A3A3AnAn 當(dāng)條件當(dāng)條件P P為真執(zhí)行語(yǔ)句體為真執(zhí)行語(yǔ)句體A A 當(dāng)條件當(dāng)條件P P

33、的值為的值為P1P1時(shí)執(zhí)行語(yǔ)句體時(shí)執(zhí)行語(yǔ)句體 否則執(zhí)行語(yǔ)句體否則執(zhí)行語(yǔ)句體B A1B A1，為，為P2P2時(shí)執(zhí)行語(yǔ)句體時(shí)執(zhí)行語(yǔ)句體 A2A2， n 循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu) 如果條件如果條件P P成立，成立， 如果條件如果條件P P不成立，不成立， 重復(fù)執(zhí)行重復(fù)執(zhí)行S S 重復(fù)執(zhí)行重復(fù)執(zhí)行S S （3）主要缺點(diǎn)：）主要缺點(diǎn)： 不易擴(kuò)充和修改，不易描述大型復(fù)雜算法。不易擴(kuò)充和修改，不易描述大型復(fù)雜算法。4 4 PADPAD圖圖 問(wèn)題分析圖問(wèn)題分析圖(Problem Analysis Diagram, (Problem Analysis Diagram, 簡(jiǎn)稱簡(jiǎn)稱PAD)PAD)表示的算法是一個(gè)二維樹(shù)形結(jié)

34、構(gòu)圖，層表示的算法是一個(gè)二維樹(shù)形結(jié)構(gòu)圖，層次感強(qiáng)、嵌套明確且有明確的控制流程。次感強(qiáng)、嵌套明確且有明確的控制流程。三種基本控制結(jié)構(gòu) 順序結(jié)構(gòu) 選擇結(jié)構(gòu) 如果條件P成立，執(zhí)行S1 當(dāng)條件P的值為P1,執(zhí)行語(yǔ)句體S1 條件不成立，執(zhí)行S2 為P2時(shí)執(zhí)行語(yǔ)句體A2， 循環(huán)結(jié)構(gòu)如果條件P成立，重復(fù)執(zhí)行S 如果條件P不成立，重復(fù)執(zhí)行S PAD PAD圖的主要優(yōu)點(diǎn)：圖的主要優(yōu)點(diǎn)： 設(shè)計(jì)出來(lái)的算法必是結(jié)構(gòu)化的。設(shè)計(jì)出來(lái)的算法必是結(jié)構(gòu)化的。 PADPAD圖描繪的算法結(jié)構(gòu)清晰。圖描繪的算法結(jié)構(gòu)清晰。 用用PADPAD圖表現(xiàn)的算法邏輯，易讀、易懂、記。圖表現(xiàn)的算法邏輯，易讀、易懂、記。 容易用軟件工具自動(dòng)將容易用

35、軟件工具自動(dòng)將PADPAD圖轉(zhuǎn)換成高級(jí)語(yǔ)言圖轉(zhuǎn)換成高級(jí)語(yǔ)言 源算法。源算法。 既可用于表示算法邏輯，也可用于描繪數(shù)據(jù)結(jié)構(gòu)。既可用于表示算法邏輯，也可用于描繪數(shù)據(jù)結(jié)構(gòu)。 支持自頂向下、逐步求精。支持自頂向下、逐步求精。缺點(diǎn)：由于是圖形符號(hào)書(shū)寫(xiě)、錄入不方便。缺點(diǎn)：由于是圖形符號(hào)書(shū)寫(xiě)、錄入不方便。例：例：圖圖3.6 3.6 問(wèn)題分析圖實(shí)例問(wèn)題分析圖實(shí)例5 5偽代碼偽代碼 偽代碼是用介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之偽代碼是用介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)來(lái)描述算法的工具。它不用圖形間的文字和符號(hào)來(lái)描述算法的工具。它不用圖形符號(hào)，因此符號(hào)，因此書(shū)寫(xiě)方便格式緊湊，易于理解，便于書(shū)寫(xiě)方便格式緊湊，易于理

36、解，便于用計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)。用計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)。6程序設(shè)計(jì)語(yǔ)言的缺點(diǎn)程序設(shè)計(jì)語(yǔ)言的缺點(diǎn) 算法的基本邏輯流程難于遵循算法的基本邏輯流程難于遵循，與自然語(yǔ)言一樣，與自然語(yǔ)言一樣，程序設(shè)計(jì)語(yǔ)言也是基于串行的，當(dāng)算法的邏輯流程較為復(fù)雜程序設(shè)計(jì)語(yǔ)言也是基于串行的，當(dāng)算法的邏輯流程較為復(fù)雜時(shí)這個(gè)問(wèn)題就變得更加嚴(yán)重時(shí)這個(gè)問(wèn)題就變得更加嚴(yán)重 特定程序設(shè)計(jì)語(yǔ)言編寫(xiě)的算法限制了與他人的交流，特定程序設(shè)計(jì)語(yǔ)言編寫(xiě)的算法限制了與他人的交流，不利于問(wèn)題的解決不利于問(wèn)題的解決 要花費(fèi)大量的時(shí)間去熟悉和掌握某種特定的程序設(shè)計(jì)要花費(fèi)大量的時(shí)間去熟悉和掌握某種特定的程序設(shè)計(jì)語(yǔ)言語(yǔ)言 要求描述計(jì)算步驟的細(xì)節(jié)而忽視算法

37、的本質(zhì)要求描述計(jì)算步驟的細(xì)節(jié)而忽視算法的本質(zhì) 需要考慮語(yǔ)法細(xì)節(jié)，而擾亂算法設(shè)計(jì)的思路需要考慮語(yǔ)法細(xì)節(jié)，而擾亂算法設(shè)計(jì)的思路 考慮到程序設(shè)計(jì)語(yǔ)言的不斷更新，不適于描述算法?？紤]到程序設(shè)計(jì)語(yǔ)言的不斷更新，不適于描述算法。 算法設(shè)計(jì)都不用程序設(shè)計(jì)語(yǔ)言直接描述。算法設(shè)計(jì)都不用程序設(shè)計(jì)語(yǔ)言直接描述。1.2.2 1.2.2 算法描述約定算法描述約定 本書(shū)采用類本書(shū)采用類C語(yǔ)言的偽代碼描述，具體細(xì)節(jié)語(yǔ)言的偽代碼描述，具體細(xì)節(jié)約定如下：約定如下： 1、三種基本控制結(jié)構(gòu)的描述、三種基本控制結(jié)構(gòu)的描述 1）順序結(jié)構(gòu)）順序結(jié)構(gòu) 一個(gè)操作以分號(hào)一個(gè)操作以分號(hào)“；”結(jié)束，每行一般只寫(xiě)結(jié)束，每行一般只寫(xiě)一條操作。一條操作

38、。2）選擇結(jié)構(gòu)）選擇結(jié)構(gòu) 單條件控制單條件控制 if 條件條件 語(yǔ)句體語(yǔ)句體1 else 語(yǔ)句體語(yǔ)句體2 多條件控制多條件控制switch(表達(dá)式表達(dá)式0) case常量表達(dá)式常量表達(dá)式1: 語(yǔ)語(yǔ)句組句組1; case常量表達(dá)式常量表達(dá)式n: 語(yǔ)語(yǔ)句組句組n; default : 語(yǔ)句組語(yǔ)句組n+1; 3 3）循環(huán)結(jié)構(gòu)）循環(huán)結(jié)構(gòu) 計(jì)數(shù)循環(huán)：計(jì)數(shù)循環(huán)： for(for(表達(dá)式表達(dá)式1 1；表達(dá)式；表達(dá)式2 2；表達(dá)式；表達(dá)式3) 3) 循環(huán)體循環(huán)體 當(dāng)型循環(huán)：當(dāng)型循環(huán)： while (while (循環(huán)條件循環(huán)條件) ) 循環(huán)體循環(huán)體 直到型循環(huán)：直到型循環(huán)： dodo 循環(huán)體循環(huán)體 while

39、(while(循環(huán)條件循環(huán)條件) )；說(shuō)明：說(shuō)明：在這三種循環(huán)體中，均可有在這三種循環(huán)體中，均可有continue語(yǔ)句和語(yǔ)句和 break語(yǔ)句。語(yǔ)句。2 2、數(shù)據(jù)結(jié)構(gòu)說(shuō)明、數(shù)據(jù)結(jié)構(gòu)說(shuō)明 算法中的標(biāo)識(shí)符由字母數(shù)字構(gòu)成，以字母開(kāi)頭。算法中的標(biāo)識(shí)符由字母數(shù)字構(gòu)成，以字母開(kāi)頭。 1 1）一般類型說(shuō)明方式：類型名）一般類型說(shuō)明方式：類型名 變量表；變量表； 類型名有：整型類型名有：整型int int 、實(shí)型、實(shí)型floatfloat、雙精度型、雙精度型 double double 字符型字符型 char char 2 2）指針類型說(shuō)明方式：類型名）指針類型說(shuō)明方式：類型名 * *指針變量名表；指針變量名

40、表；3 3）構(gòu)造類型：）構(gòu)造類型：數(shù)組說(shuō)明：類型名數(shù)組說(shuō)明：類型名 一維數(shù)組名一維數(shù)組名n(n(開(kāi)辟開(kāi)辟n n個(gè)空間，個(gè)空間， 下標(biāo)下標(biāo)0n-1)0n-1)； 類型名類型名 二維數(shù)組名二維數(shù)組名m,n(m,n(開(kāi)辟開(kāi)辟m m* *n n個(gè)空個(gè)空 間，下標(biāo)間，下標(biāo)0,0m-1,n-1)0,0m-1,n-1)；結(jié)構(gòu)類型結(jié)構(gòu)類型: struct : struct 結(jié)構(gòu)體類型名結(jié)構(gòu)體類型名 類型類型 成員名成員名; ; 類型類型 成員名成員名; ; . . ; ; 4 4）動(dòng)態(tài)空間申請(qǐng)函數(shù)）動(dòng)態(tài)空間申請(qǐng)函數(shù) malloc(size) malloc(size) 功能：申請(qǐng)功能：申請(qǐng)sizesize個(gè)字節(jié)

41、的一個(gè)空間；返個(gè)字節(jié)的一個(gè)空間；返回所申請(qǐng)空間的首地址?；厮暾?qǐng)空間的首地址。 calloc(num,size ) calloc(num,size ) 功能：申請(qǐng)功能：申請(qǐng)numnum個(gè)個(gè)sizesize個(gè)字節(jié)的空個(gè)字節(jié)的空間；返回所申請(qǐng)空間的首地址。間；返回所申請(qǐng)空間的首地址。 free( free( * *p ) p ) 功能：釋放功能：釋放p p指向的動(dòng)態(tài)空間。指向的動(dòng)態(tài)空間。3 3模塊及模塊間的接口方式的描述模塊及模塊間的接口方式的描述 算法或算法中模塊結(jié)構(gòu)為：算法或算法中模塊結(jié)構(gòu)為： 模塊（算法）名（參數(shù)）模塊（算法）名（參數(shù)） 模塊體模塊體 模塊間的接口方式的描述如下：模塊間的接口

42、方式的描述如下： 全局變量：定義模塊外的變量。全局變量：定義模塊外的變量。 子模塊返回調(diào)用模塊信息：子模塊返回調(diào)用模塊信息： 調(diào)用函數(shù)：子模塊名調(diào)用函數(shù)：子模塊名 被調(diào)用函數(shù)：被調(diào)用函數(shù)：return(return(返回信息返回信息) ) 調(diào)用模塊傳遞給子模塊信息：值參數(shù)傳遞調(diào)用模塊傳遞給子模塊信息：值參數(shù)傳遞 實(shí)際參數(shù)為：表達(dá)式、普通變量名、常量或數(shù)組元素實(shí)際參數(shù)為：表達(dá)式、普通變量名、常量或數(shù)組元素 形式參數(shù)為：普通變量名形式參數(shù)為：普通變量名 調(diào)用模塊與子模塊互相傳遞信息：變量參數(shù)傳遞調(diào)用模塊與子模塊互相傳遞信息：變量參數(shù)傳遞 實(shí)際參數(shù)為：普通變量名實(shí)際參數(shù)為：普通變量名 形式參數(shù)為：形

43、式參數(shù)為：& &變量名變量名 按地址共享變量：地址參數(shù)傳遞按地址共享變量：地址參數(shù)傳遞 實(shí)際參數(shù)為：指針變量名實(shí)際參數(shù)為：指針變量名( (不帶不帶* *) )、數(shù)組名，變量地址（、數(shù)組名，變量地址（& &變量名）變量名） 形式參數(shù)為：指針變量名形式參數(shù)為：指針變量名( (* *變量名變量名) )4 4其它細(xì)節(jié)說(shuō)明：其它細(xì)節(jié)說(shuō)明： 1 1）無(wú)歧義的情況下一般不做存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)類型說(shuō)明。）無(wú)歧義的情況下一般不做存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)類型說(shuō)明。 2 2）運(yùn)算符號(hào)采用較通用的表示形式，如求余不用）運(yùn)算符號(hào)采用較通用的表示形式，如求余不用“%”%”而用而用“mod”mod”表示、

44、邏輯表示、邏輯“與與”不用不用“&”&”而用而用“and”and”表示表示等等。等等。 3 3）用）用 表示整除，用表示整除，用 / / 表示帶小數(shù)除法。表示帶小數(shù)除法。 4 4）無(wú)歧義時(shí)允許連續(xù)賦值，如）無(wú)歧義時(shí)允許連續(xù)賦值，如a=b=1a=b=1。 5 5）條件語(yǔ)句中判斷相等，用符號(hào)）條件語(yǔ)句中判斷相等，用符號(hào)“=”=”，判斷不相等，判斷不相等，用符號(hào)用符號(hào)“”。 6 6）算法中的注釋用）算法中的注釋用“/ /* * * */”/”與操作分隔。與操作分隔。 7 7）為講解說(shuō)明方便，）為講解說(shuō)明方便，有的有的算法對(duì)指令進(jìn)行編號(hào)。算法對(duì)指令進(jìn)行編號(hào)。 8 8）輸入用輸入用inp

45、utinput( (變量表變量表) )表示，表示，輸出用輸出用printprint( (輸出項(xiàng)輸出項(xiàng)) )表示，一般不說(shuō)明輸入、輸出格式。表示，一般不說(shuō)明輸入、輸出格式。 9 9）算法中會(huì)使用庫(kù)函數(shù)，一般在算法中注釋其功能。）算法中會(huì)使用庫(kù)函數(shù)，一般在算法中注釋其功能。如如ABSABS（）取絕對(duì)值，（）取絕對(duì)值，INTINT（）取整函數(shù)（舍去小數(shù)部分）。（）取整函數(shù)（舍去小數(shù)部分）。 1.2.3 1.2.3 一個(gè)簡(jiǎn)單問(wèn)題的求解過(guò)程一個(gè)簡(jiǎn)單問(wèn)題的求解過(guò)程問(wèn)題求解的步驟可以簡(jiǎn)化為三步：?jiǎn)栴}求解的步驟可以簡(jiǎn)化為三步：具體（問(wèn)題的現(xiàn)實(shí)領(lǐng)域）具體（問(wèn)題的現(xiàn)實(shí)領(lǐng)域） 1 1問(wèn)題分析建立模型問(wèn)題分析建立模型抽象（邏輯結(jié)構(gòu)、模型建立、功能確認(rèn)）抽象（邏輯結(jié)構(gòu)、模型建立、功能確認(rèn)）2 2算法設(shè)計(jì)算法設(shè)計(jì)具體（計(jì)算機(jī)世界）具體（計(jì)算機(jī)世界）3 3算法分析算法分析抽象（性能及算法文檔）。抽象（性能及算法文檔）。【例例】求二個(gè)正整數(shù)的最大公約數(shù)。求二個(gè)正整數(shù)的最大公約數(shù)。問(wèn)題分析：此題只需有小學(xué)知識(shí)，就可有以下建立以下問(wèn)題分析：此題只需有小學(xué)知識(shí)，就可有以下建立以下的數(shù)學(xué)模型。的數(shù)學(xué)模型。數(shù)學(xué)模型：數(shù)學(xué)模型：a，b0 的整數(shù)，求的整數(shù)，求c，c能整除能整除a，b，且，且a/c與與b/c互質(zhì)?；ベ|(zhì)。算法設(shè)計(jì)：這個(gè)方法首先基于人能算法設(shè)計(jì)：這個(gè)方法首先基于人能“宏觀宏觀