第5章算法與數(shù)據(jù)結(jié)構(gòu)

1、我們畢業(yè)啦其實(shí)是答辯的標(biāo)題地方Taiyuan University of Technology大學(xué)計(jì)算機(jī)基礎(chǔ)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 計(jì)算機(jī)基礎(chǔ)教學(xué)部2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部數(shù)學(xué)思維強(qiáng)調(diào)數(shù)與形的邏輯關(guān)系、演算推理能力和嚴(yán)謹(jǐn)態(tài)度，計(jì)算思維強(qiáng)調(diào)問題求解的操作過程和機(jī)器實(shí)現(xiàn)。問題求解的思路和方法，即為算法。而在確定問題求解的算法之前應(yīng)先分析問題，從中抽象提取操作對象，并找到這些操作對象之間蘊(yùn)含的關(guān)系，即數(shù)據(jù)結(jié)構(gòu)。 計(jì)算機(jī)算法與數(shù)據(jù)結(jié)構(gòu)都是問題求解過程中兩個(gè)要素，且二者密切相關(guān)，算法無不依附于具體的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)直接關(guān)系到算法的選擇和效率?？梢哉f一個(gè)好的算法

2、和數(shù)據(jù)結(jié)構(gòu)可能使某個(gè)原來需要用成年累月才能完成的問題在分秒之中得到解決。在某些特殊的領(lǐng)域，例如圖形學(xué)、數(shù)據(jù)庫、語法分析、數(shù)值分析和模擬等，解決問題的能力幾乎完全依賴于最新的算法和數(shù)據(jù)結(jié)構(gòu)。 算法設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)是相互依存相互影響的。 數(shù)據(jù)結(jié)構(gòu)十算法= 程序，可見兩者間在計(jì)算機(jī)科學(xué)界與計(jì)算機(jī)應(yīng)用界的地位。22022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部35.1 算法基礎(chǔ)5.2 數(shù)據(jù)結(jié)構(gòu)5.3 算法設(shè)計(jì)本章小結(jié)第五章 算法與數(shù)據(jù)結(jié)構(gòu)2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部45.1 算法基礎(chǔ)算法（算法（Algorithm）是計(jì)算機(jī)學(xué)科中最具有方法論性質(zhì)

3、的核）是計(jì)算機(jī)學(xué)科中最具有方法論性質(zhì)的核心概念，被譽(yù)為計(jì)算機(jī)學(xué)科的靈魂。心概念，被譽(yù)為計(jì)算機(jī)學(xué)科的靈魂。廣義地說，算法就是為解決某一問題采用的方法和步驟，廣義地說，算法就是為解決某一問題采用的方法和步驟，即算法要解決的問題就是即算法要解決的問題就是“做什么做什么”和和“怎么做怎么做”。2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部本節(jié)內(nèi)容55.1.1算法的起源算法的起源5.1.2 算法的定義和特性算法的定義和特性5.1.3 算法的表述算法的表述5.1.4 算法的基本結(jié)構(gòu)算法的基本結(jié)構(gòu)5.1.5 算法的評價(jià)算法的評價(jià)周髀算經(jīng)九章算術(shù)最早四則運(yùn)算、最大公約數(shù)、最小公倍數(shù)、開平

4、方根、開立方根、求素?cái)?shù)、線性方程組求解第一個(gè)算法歐幾里得算法（輾轉(zhuǎn)相除法）：求兩個(gè)正整數(shù)m和n的最大公約數(shù)：第一步: 比較兩個(gè)數(shù)大小，將m設(shè)置為較大的數(shù)，n為較小的數(shù)；第二步: m除以n，得到余數(shù)r；第三步: 如果r等于0，則最大公約數(shù)就是n，否則將n賦值給m，r賦值給n，重復(fù) 第二 、第三步。5.1.15.1.1算法的起源算法的起源5.1.2 5.1.2 算法的定義和特性算法的定義和特性2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部廣義：為解決問題采用的方法和步驟。計(jì)算機(jī)算法就是研究適合計(jì)算機(jī)實(shí)現(xiàn)的求解問題的方法和步計(jì)算機(jī)算法就是研究適合計(jì)算機(jī)實(shí)現(xiàn)的求解問題的方法和步驟

5、。計(jì)算機(jī)按照算法設(shè)計(jì)的順序來執(zhí)行這些命令，以達(dá)到解決某驟。計(jì)算機(jī)按照算法設(shè)計(jì)的順序來執(zhí)行這些命令，以達(dá)到解決某個(gè)問題的目的。亦即算法代表著用系統(tǒng)的方法描述解決問題的策個(gè)問題的目的。亦即算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制。略機(jī)制。算法的基本特征：2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部（1）有窮性：）有窮性：有窮有窮步驟、步驟、有窮時(shí)間。有窮時(shí)間。（2）確定性：）確定性：算法中每一條指令必須有確切的含義，不存在二義算法中每一條指令必須有確切的含義，不存在二義性，確保對于同一個(gè)算法，相同的輸入必然得出相同的執(zhí)行結(jié)果性，確保對于同一個(gè)算法，相同的輸入必然得出相同

6、的執(zhí)行結(jié)果。且算法只有一個(gè)入口和一個(gè)出口。且算法只有一個(gè)入口和一個(gè)出口。（3）可行性：）可行性：可以執(zhí)行的，并得到確定的結(jié)果。即算法中不應(yīng)該可以執(zhí)行的，并得到確定的結(jié)果。即算法中不應(yīng)該有永遠(yuǎn)都執(zhí)行不到的有永遠(yuǎn)都執(zhí)行不到的“死語句死語句”和不可操作的和不可操作的“虛語句虛語句”。（4）輸入：）輸入：有零個(gè)或多個(gè)輸入（即可以沒有輸入有零個(gè)或多個(gè)輸入（即可以沒有輸入）。）。（5）輸出：）輸出：一個(gè)算法至少有一個(gè)或多個(gè)輸出（即必須有輸出），一個(gè)算法至少有一個(gè)或多個(gè)輸出（即必須有輸出），5.1.3 5.1.3 算法的表述算法的表述2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部算法的

7、表述就是用文字或圖形把算法表示出來，便于人們閱讀和算法的表述就是用文字或圖形把算法表示出來，便于人們閱讀和理解。好的表述可使程序員清楚地了解其中的邏輯關(guān)系，發(fā)現(xiàn)和理解。好的表述可使程序員清楚地了解其中的邏輯關(guān)系，發(fā)現(xiàn)和改正錯(cuò)誤，進(jìn)而提高程序設(shè)計(jì)的效率。改正錯(cuò)誤，進(jìn)而提高程序設(shè)計(jì)的效率。一個(gè)算法的表述可用多種描述工具，經(jīng)常使用的有一個(gè)算法的表述可用多種描述工具，經(jīng)常使用的有自然語言、流自然語言、流程圖、程圖、N-S圖、圖、PAD圖、圖、偽代碼、偽代碼、程序設(shè)計(jì)語言等方法。程序設(shè)計(jì)語言等方法。1. 自然語言2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部自然語言（自然語言（Na

8、tural Language）即人們?nèi)粘Ｉ钪惺褂玫恼Z言。可以是漢語、即人們?nèi)粘Ｉ钪惺褂玫恼Z言。可以是漢語、英語、數(shù)學(xué)關(guān)系式等。使用自然語言描述算法，通俗易懂，初學(xué)者容易掌握。英語、數(shù)學(xué)關(guān)系式等。使用自然語言描述算法，通俗易懂，初學(xué)者容易掌握。缺點(diǎn)缺點(diǎn)：（1）描述文字顯得冗長。（）描述文字顯得冗長。（2）容易產(chǎn)生歧義性。（）容易產(chǎn)生歧義性。（3）不易直接轉(zhuǎn)化為程序。）不易直接轉(zhuǎn)化為程序?！纠纠?-1】 用計(jì)算機(jī)實(shí)現(xiàn)：比較兩個(gè)數(shù)用計(jì)算機(jī)實(shí)現(xiàn)：比較兩個(gè)數(shù)a、b的值，請按從大到小的順序輸出。用的值，請按從大到小的順序輸出。用自然語言描述的算法如下：自然語言描述的算法如下：S1：輸入：輸入a和和b

9、的值；的值；S2：比較：比較a，b的大小，如果的大小，如果a=b，則先打印，則先打印a，再打印，再打印b；否則，先打印；否則，先打印b，再，再打印打印a；S3：算法結(jié)束。：算法結(jié)束。 2. 2. 流程圖流程圖2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部流程圖（流程圖（Flow Chart）也稱為程序框圖，是用各種幾何圖形、流也稱為程序框圖，是用各種幾何圖形、流程線及文字說明來表示各種類型的操作框圖。美國國家標(biāo)準(zhǔn)化協(xié)程線及文字說明來表示各種類型的操作框圖。美國國家標(biāo)準(zhǔn)化協(xié)會會ANSI規(guī)定了一些常用的流程圖符號規(guī)定了一些常用的流程圖符號：2022-3-7太原理工大學(xué).計(jì)算機(jī)

10、科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部優(yōu)點(diǎn)：優(yōu)點(diǎn)：流程圖方法形象直觀，易于理解，流程圖方法形象直觀，易于理解，并可直觀地將算法轉(zhuǎn)化為程序。并可直觀地將算法轉(zhuǎn)化為程序。缺點(diǎn)：缺點(diǎn)：流程圖占用篇幅較多，尤其是當(dāng)算流程圖占用篇幅較多，尤其是當(dāng)算法比較復(fù)雜時(shí)，制作流程圖既費(fèi)時(shí)又不方法比較復(fù)雜時(shí)，制作流程圖既費(fèi)時(shí)又不方便。此外，由于流程線沒有約束，可以任便。此外，由于流程線沒有約束，可以任意轉(zhuǎn)向，從而造成算法閱讀和修改上的困意轉(zhuǎn)向，從而造成算法閱讀和修改上的困難，不利于結(jié)構(gòu)化程序的設(shè)計(jì)。難，不利于結(jié)構(gòu)化程序的設(shè)計(jì)。如例如例5-1用流程圖來描述的算法如用流程圖來描述的算法如下：下：2022-3-7太原理工大學(xué).

11、計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部用流程圖描述算法時(shí)，一般要注意一下幾點(diǎn)。用流程圖描述算法時(shí)，一般要注意一下幾點(diǎn)。（1）根據(jù)解決問題的步驟從上至下順序地畫流程線，各圖框）根據(jù)解決問題的步驟從上至下順序地畫流程線，各圖框中的文字要盡量簡潔。中的文字要盡量簡潔。（2）為避免流程圖的圖形顯得過長，圖中的流程線要盡量短）為避免流程圖的圖形顯得過長，圖中的流程線要盡量短。（3）用流程圖描述算法的原則是：根據(jù)實(shí)際問題的復(fù)雜性，）用流程圖描述算法的原則是：根據(jù)實(shí)際問題的復(fù)雜性，流程圖達(dá)到的最終效果應(yīng)該是：依據(jù)此圖就能用某種程序設(shè)流程圖達(dá)到的最終效果應(yīng)該是：依據(jù)此圖就能用某種程序設(shè)計(jì)語言實(shí)現(xiàn)相應(yīng)的算法（即

12、完成編程）。計(jì)語言實(shí)現(xiàn)相應(yīng)的算法（即完成編程）。3. N-S3. N-S圖圖2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部N-S圖圖指將指將流程圖中流程線去掉，在框內(nèi)將算法的每一步都用一個(gè)矩流程圖中流程線去掉，在框內(nèi)將算法的每一步都用一個(gè)矩形框來描述，把一個(gè)個(gè)矩形框按執(zhí)行的次序連接起來組成一個(gè)大矩形形框來描述，把一個(gè)個(gè)矩形框按執(zhí)行的次序連接起來組成一個(gè)大矩形框，就是一個(gè)完整的算法描述。這種流程圖就稱為框，就是一個(gè)完整的算法描述。這種流程圖就稱為N-S結(jié)構(gòu)流程圖（結(jié)構(gòu)流程圖（簡稱簡稱N-S圖）或盒圖。圖）或盒圖。特點(diǎn)：特點(diǎn)：N-S圖描述的算法在執(zhí)行時(shí)只能從上圖描述的算法在執(zhí)

13、行時(shí)只能從上到下順序執(zhí)行，從而避免了算法流程的任意到下順序執(zhí)行，從而避免了算法流程的任意轉(zhuǎn)向，保證了程序的質(zhì)量。轉(zhuǎn)向，保證了程序的質(zhì)量。N-S圖的另一個(gè)圖的另一個(gè)優(yōu)點(diǎn)是形象直觀，畫圖節(jié)省篇幅，尤其適合優(yōu)點(diǎn)是形象直觀，畫圖節(jié)省篇幅，尤其適合結(jié)構(gòu)化程序的設(shè)計(jì)。結(jié)構(gòu)化程序的設(shè)計(jì)。如如：用用N-S圖來描述例圖來描述例5-1的算法如圖所示。的算法如圖所示。4. 4. 偽代碼偽代碼2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部偽代碼（偽代碼（Pseudocode）又稱程序設(shè)計(jì)語言又稱程序設(shè)計(jì)語言PDL，是一種近似高級，是一種近似高級語言但又不受語法約束的一種語言描述方式，它用一種介于

14、自然語語言但又不受語法約束的一種語言描述方式，它用一種介于自然語言和程序設(shè)計(jì)語言之間的文字和符號來描述算法。相比程序語言（言和程序設(shè)計(jì)語言之間的文字和符號來描述算法。相比程序語言（例如例如Java、C+、C、VB 等等）它更類似自然語言，是計(jì)算機(jī)代等等）它更類似自然語言，是計(jì)算機(jī)代碼的簡略形式。碼的簡略形式。特點(diǎn)：特點(diǎn)：偽代碼可以用英文、漢字、數(shù)學(xué)表達(dá)式等混合表示算法，且偽代碼可以用英文、漢字、數(shù)學(xué)表達(dá)式等混合表示算法，且無固定的、嚴(yán)格的語法規(guī)則，以便于書寫和閱讀為原則，故其能更無固定的、嚴(yán)格的語法規(guī)則，以便于書寫和閱讀為原則，故其能更好的轉(zhuǎn)換為高級語言程序。好的轉(zhuǎn)換為高級語言程序。2022-

15、3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部如例如例5-1用偽代碼描述其算法如下。用偽代碼描述其算法如下。 int a,b /*定義兩個(gè)整型變量a，b*/scanf a、b; /*鍵盤輸入a，b的值*/ if( a=b) /*如果ab */ printf a,b; /*輸出a的值*/ else printf b,a; /*否則輸出b的值*/#include main() int a,b; scanf(%d,%d,&a,&b); if(ab) printf(%d,%d,a,b); else printf(%d,%d,b,a);將算法轉(zhuǎn)化為將算法轉(zhuǎn)化為C語言程序語言程序：5.1.4

16、5.1.4 算法的基本結(jié)構(gòu)算法的基本結(jié)構(gòu)2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部一個(gè)算法具有兩個(gè)要素：操作和控制結(jié)構(gòu)。一個(gè)算法具有兩個(gè)要素：操作和控制結(jié)構(gòu)。（1）操作：指計(jì)算機(jī)最基本的功能操作，包括算術(shù)運(yùn)算）操作：指計(jì)算機(jī)最基本的功能操作，包括算術(shù)運(yùn)算、關(guān)系運(yùn)算、邏輯運(yùn)算和數(shù)據(jù)傳送等。、關(guān)系運(yùn)算、邏輯運(yùn)算和數(shù)據(jù)傳送等。（2）控制結(jié)構(gòu)：指各操作之間的執(zhí)行順序。算法中的每）控制結(jié)構(gòu)：指各操作之間的執(zhí)行順序。算法中的每個(gè)步驟必須是定義完好的、執(zhí)行流暢的結(jié)構(gòu)。個(gè)步驟必須是定義完好的、執(zhí)行流暢的結(jié)構(gòu)。計(jì)算機(jī)科學(xué)家為結(jié)構(gòu)化程序設(shè)計(jì)或算法定義了三種控制結(jié)計(jì)算機(jī)科學(xué)家為結(jié)構(gòu)化程序設(shè)

17、計(jì)或算法定義了三種控制結(jié)構(gòu)：構(gòu)：順序結(jié)構(gòu)順序結(jié)構(gòu)、分支結(jié)構(gòu)分支結(jié)構(gòu)和和循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)。1. 順序結(jié)構(gòu)2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部（a）流程圖（b）N-S圖 順序結(jié)構(gòu)示例流程圖順序結(jié)構(gòu)順序結(jié)構(gòu)是最簡單、最基本的控制結(jié)構(gòu)，其操作步驟是按照設(shè)置的先后順序，是最簡單、最基本的控制結(jié)構(gòu)，其操作步驟是按照設(shè)置的先后順序，一步一步地執(zhí)行。一步一步地執(zhí)行。設(shè)設(shè)A、B代表算法的兩個(gè)不同的步驟，順序結(jié)構(gòu)的基本形式為代表算法的兩個(gè)不同的步驟，順序結(jié)構(gòu)的基本形式為“執(zhí)行執(zhí)行A，然后執(zhí)，然后執(zhí)行行B”，即按照從上到下依次執(zhí)行，即按照從上到下依次執(zhí)行A步驟和步驟和B步驟，執(zhí)行流程

18、如圖所示。步驟，執(zhí)行流程如圖所示。 【例例5-2】表述用計(jì)算表述用計(jì)算機(jī)實(shí)現(xiàn)求任意兩數(shù)之和機(jī)實(shí)現(xiàn)求任意兩數(shù)之和的算法。的算法。2. 分支結(jié)構(gòu)2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部分支結(jié)構(gòu)也叫選擇結(jié)構(gòu)，它首先需要判斷給定條件的真假，然后選擇執(zhí)行方分支結(jié)構(gòu)也叫選擇結(jié)構(gòu)，它首先需要判斷給定條件的真假，然后選擇執(zhí)行方向。如圖向。如圖下所示，其基本形式為下所示，其基本形式為“如果如果P成立，則執(zhí)行成立，則執(zhí)行A，否則（即條件，否則（即條件P不成不成了）執(zhí)行了）執(zhí)行B”。應(yīng)當(dāng)注意，無論條件是否成立，只能執(zhí)行。應(yīng)當(dāng)注意，無論條件是否成立，只能執(zhí)行A或或B之一，不能既執(zhí)行之一，不

19、能既執(zhí)行A又執(zhí)行又執(zhí)行B。（a）流程圖）流程圖（b）N-S圖圖 2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部【例【例5-3】求任意求任意3個(gè)正整數(shù)個(gè)正整數(shù)a、b、c中的最大者。中的最大者。用自然語言描述其算法如下：用自然語言描述其算法如下：S1：輸入：輸入3個(gè)正整數(shù)個(gè)正整數(shù) a，b，c；S2：若：若a大于大于b，則將，則將a放到放到max中，否則將中，否則將b放到放到max中；中；S3：若：若c大于大于max，則將，則將c放到放到max中；中；S4：輸出：輸出max即為三個(gè)數(shù)中最大的一個(gè)。即為三個(gè)數(shù)中最大的一個(gè)。用流程圖描述算法如圖所示。用流程圖描述算法如圖所示。分支結(jié)

20、構(gòu)示例流程圖分支結(jié)構(gòu)示例流程圖3. 3.循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部循環(huán)結(jié)構(gòu)也叫重復(fù)結(jié)構(gòu)，它在給定條件成立時(shí)，需要反復(fù)執(zhí)行同一操作。循環(huán)結(jié)構(gòu)也叫重復(fù)結(jié)構(gòu)，它在給定條件成立時(shí)，需要反復(fù)執(zhí)行同一操作。循環(huán)結(jié)構(gòu)有三個(gè)要素：循環(huán)結(jié)構(gòu)有三個(gè)要素：循環(huán)變量循環(huán)變量、循環(huán)體循環(huán)體和和循環(huán)終止條件循環(huán)終止條件。即從某處開始，按照一定條件需要反復(fù)執(zhí)行的某些步驟，就是循環(huán)體。循環(huán)結(jié)即從某處開始，按照一定條件需要反復(fù)執(zhí)行的某些步驟，就是循環(huán)體。循環(huán)結(jié)構(gòu)中通常都有一個(gè)起循環(huán)計(jì)數(shù)作用的變量，這個(gè)變量的取值一般都包含在執(zhí)行構(gòu)中通常都有一個(gè)起循環(huán)計(jì)數(shù)作用的變量，這個(gè)變

21、量的取值一般都包含在執(zhí)行或終止循環(huán)的條件中，即為循環(huán)變量。循環(huán)結(jié)構(gòu)不能無限制的進(jìn)行下去，否則或終止循環(huán)的條件中，即為循環(huán)變量。循環(huán)結(jié)構(gòu)不能無限制的進(jìn)行下去，否則就成了死循環(huán)，所以一定要在某個(gè)條件下終止循環(huán)，這個(gè)可以用來判定是否繼就成了死循環(huán)，所以一定要在某個(gè)條件下終止循環(huán)，這個(gè)可以用來判定是否繼續(xù)執(zhí)行循環(huán)體的條件就稱為循環(huán)終止條件。續(xù)執(zhí)行循環(huán)體的條件就稱為循環(huán)終止條件。從循環(huán)的形成與控制不同來劃分，循環(huán)結(jié)構(gòu)可分為當(dāng)型循環(huán)結(jié)構(gòu)和直到型循環(huán)從循環(huán)的形成與控制不同來劃分，循環(huán)結(jié)構(gòu)可分為當(dāng)型循環(huán)結(jié)構(gòu)和直到型循環(huán)結(jié)構(gòu)。結(jié)構(gòu)。2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部當(dāng)型循環(huán)結(jié)構(gòu)

22、當(dāng)型循環(huán)結(jié)構(gòu)：是先判斷條件是先判斷條件P，若，若P成立，執(zhí)行循環(huán)體成立，執(zhí)行循環(huán)體A，如此反復(fù)，如此反復(fù)，當(dāng)當(dāng)P不成立時(shí)，退出循環(huán)結(jié)構(gòu)，如圖（不成立時(shí)，退出循環(huán)結(jié)構(gòu)，如圖（a）所示。）所示。直到型循環(huán)結(jié)構(gòu)直到型循環(huán)結(jié)構(gòu)：是先執(zhí)行一次循環(huán)體是先執(zhí)行一次循環(huán)體A后，再對條件后，再對條件P進(jìn)行判斷，若進(jìn)行判斷，若P不成立，執(zhí)行循環(huán)體不成立，執(zhí)行循環(huán)體A，如此反復(fù)，直到條件，如此反復(fù)，直到條件P成立，退出循環(huán)結(jié)構(gòu)，如成立，退出循環(huán)結(jié)構(gòu)，如圖（圖（b）所示。）所示。（a）當(dāng)型循環(huán)結(jié)構(gòu)流程圖和）當(dāng)型循環(huán)結(jié)構(gòu)流程圖和N-S圖圖（b）直到型循環(huán)結(jié)構(gòu)流程圖和）直到型循環(huán)結(jié)構(gòu)流程圖和N-S圖圖5.1.5 算法的評

23、價(jià)2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部同一個(gè)問題可以用許多不同的算法解決，而不同的算法可能耗用系統(tǒng)不同同一個(gè)問題可以用許多不同的算法解決，而不同的算法可能耗用系統(tǒng)不同的時(shí)間、空間或效率。對算法優(yōu)劣的評定稱為的時(shí)間、空間或效率。對算法優(yōu)劣的評定稱為“算法評價(jià)算法評價(jià)”。算法評價(jià)的目的，在于從解決同一問題的不同算法中選擇出較為合適的一算法評價(jià)的目的，在于從解決同一問題的不同算法中選擇出較為合適的一種算法，或者是對原有的算法進(jìn)行改造、加工，使其更優(yōu)、更好。種算法，或者是對原有的算法進(jìn)行改造、加工，使其更優(yōu)、更好。算法評價(jià)的標(biāo)準(zhǔn)算法評價(jià)的標(biāo)準(zhǔn)：（1）算法的正確性（2）算

24、法的可讀性（3）算法的健壯性（4）算法的時(shí)間復(fù)雜度 （5）算法的空間復(fù)雜度2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部5.2 算法設(shè)計(jì)5.2.1 計(jì)算機(jī)基本算法計(jì)算機(jī)基本算法利用計(jì)算機(jī)解題的過程實(shí)際上是實(shí)施某種算法的過程，在這個(gè)過程利用計(jì)算機(jī)解題的過程實(shí)際上是實(shí)施某種算法的過程，在這個(gè)過程中，將具體問題抽象出其數(shù)學(xué)模型固然重要，但也要充分考慮計(jì)算機(jī)強(qiáng)中，將具體問題抽象出其數(shù)學(xué)模型固然重要，但也要充分考慮計(jì)算機(jī)強(qiáng)大的數(shù)據(jù)處理能力和其硬件設(shè)備的限制問題，在此基礎(chǔ)上發(fā)現(xiàn)和構(gòu)造的大的數(shù)據(jù)處理能力和其硬件設(shè)備的限制問題，在此基礎(chǔ)上發(fā)現(xiàn)和構(gòu)造的一些常見問題的處理算法一些常見問題的處

25、理算法，已不同于傳統(tǒng)的數(shù)學(xué)思維處理方法。如：兩，已不同于傳統(tǒng)的數(shù)學(xué)思維處理方法。如：兩個(gè)變量值的交換、累加和累乘問題基本求解算法等。個(gè)變量值的交換、累加和累乘問題基本求解算法等。1. 交換變量的值2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部交換變量的值：需引入一個(gè)中間變量交換變量的值：需引入一個(gè)中間變量t，t=a,a=b,b=tabt1232022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部用自然語言描述其算法如下：用自然語言描述其算法如下：S1：輸入：輸入a，b的值；的值；S2：判斷：判斷ab是否成立，若成立，則依此執(zhí)行是否成立，若成立，則依此執(zhí)行S3

26、、S4、S5、S6；若不成立則執(zhí)行；若不成立則執(zhí)行S7；S3：將：將a的值存放到變量的值存放到變量t的存儲單元中，即的存儲單元中，即t=a； S4：將：將b的值存放到變量的值存放到變量a的存儲單元中，即的存儲單元中，即a=b；S5：將：將t的值（即原來變量的值（即原來變量a的值）存放到變量的值）存放到變量b的的存儲單元中，即存儲單元中，即b=t。S6：輸出：輸出a，b的值；的值；S7：輸出：輸出ab，則交換二者的值。，則交換二者的值。用流程圖表示的算法用流程圖表示的算法:2.累加2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部累加就是對若干個(gè)數(shù)求和。例如累加就是對若干個(gè)數(shù)求

27、和。例如1100的整數(shù)求和，的整數(shù)求和，mn之間的奇數(shù)或偶數(shù)之間的奇數(shù)或偶數(shù)求和等等。求和等等。計(jì)算機(jī)由于硬件所限，每次只能處理兩個(gè)數(shù)的相加運(yùn)算，所以多個(gè)數(shù)相加必計(jì)算機(jī)由于硬件所限，每次只能處理兩個(gè)數(shù)的相加運(yùn)算，所以多個(gè)數(shù)相加必須通過多次的兩兩相加來實(shí)現(xiàn)。而簡單的重復(fù)執(zhí)行某一操作正是計(jì)算機(jī)的強(qiáng)項(xiàng)。須通過多次的兩兩相加來實(shí)現(xiàn)。而簡單的重復(fù)執(zhí)行某一操作正是計(jì)算機(jī)的強(qiáng)項(xiàng)。因此計(jì)算機(jī)實(shí)現(xiàn)累加求和最基本的思想就是因此計(jì)算機(jī)實(shí)現(xiàn)累加求和最基本的思想就是“反復(fù)的做加法反復(fù)的做加法”。存儲累加結(jié)果的變量一般情況下應(yīng)該賦初值為存儲累加結(jié)果的變量一般情況下應(yīng)該賦初值為0?！纠?-5】 計(jì)算1+2+3+n 的值。自

28、然語言算法描述如下：自然語言算法描述如下：S1S1：變量賦初值：變量賦初值：i=1i=1，sum=0sum=0；S2S2：輸入：輸入n n的值；的值；S3S3：判斷：判斷i=ni=n是否成立，若成立則執(zhí)行是否成立，若成立則執(zhí)行S4S4，否則就執(zhí)行，否則就執(zhí)行S5S5；S4S4：執(zhí)行：執(zhí)行sum=sum+i(sum=sum+i(實(shí)現(xiàn)累加實(shí)現(xiàn)累加) )，i=i+1(i=i+1(實(shí)現(xiàn)計(jì)數(shù)實(shí)現(xiàn)計(jì)數(shù)) )，并返回第三步繼續(xù)執(zhí)行，并返回第三步繼續(xù)執(zhí)行；S5S5：輸出：輸出sumsum的值。的值。 【例【例5-55-5】 計(jì)算計(jì)算1+2+3+1+2+3+ +n n 的值。的值。用流程圖描述其算法如圖用流程圖

29、描述其算法如圖5.105.10所示。所示。2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部開 始i= 1 ,su m = 0輸 入 n 的 值i = nsu m = su m + 1i= i+ 1輸 出 su m 的 值結(jié) 束NY3.累乘2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部累乘就是在一個(gè)變量的基礎(chǔ)上重復(fù)乘上一個(gè)數(shù)。其基本思想和累加相同，最累乘就是在一個(gè)變量的基礎(chǔ)上重復(fù)乘上一個(gè)數(shù)。其基本思想和累加相同，最典型的應(yīng)用為階乘問題。存儲累乘結(jié)果的變量的初值應(yīng)置為典型的應(yīng)用為階乘問題。存儲累乘結(jié)果的變量的初值應(yīng)置為1，不能為，不能為0。【例【例5-6】

30、計(jì)算】計(jì)算10！分析：分析：10!=12310，和例，和例5-5不不同的是在循環(huán)中運(yùn)算的是乘法，每一次得同的是在循環(huán)中運(yùn)算的是乘法，每一次得到的是累乘的積，記錄累乘的積的變量初到的是累乘的積，記錄累乘的積的變量初值應(yīng)為值應(yīng)為1。其算法流程圖如圖所示。其算法流程圖如圖所示。開 始p = 1i= 1i = 1 0p = p * ii= i+ 1輸 出 p 的 值結(jié) 束NY5.2.2 經(jīng)典算法策略2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部算法作為一門古老的學(xué)科，隨著歷史的發(fā)展，積累了很多經(jīng)典算法策算法作為一門古老的學(xué)科，隨著歷史的發(fā)展，積累了很多經(jīng)典算法策略。算法策略和算法

31、是有區(qū)別的，他們是算法設(shè)計(jì)中的兩個(gè)方面。算法策略。算法策略和算法是有區(qū)別的，他們是算法設(shè)計(jì)中的兩個(gè)方面。算法策略是面向問題的，算法是面向?qū)崿F(xiàn)的，但是二者又是不可分的，只有通過略是面向問題的，算法是面向?qū)崿F(xiàn)的，但是二者又是不可分的，只有通過一定的算法策略才能找出解決問題的具體算法?；镜乃惴ú呗灾饕懈F一定的算法策略才能找出解決問題的具體算法?；镜乃惴ú呗灾饕懈F舉策略、遞推策略、遞歸策略、分治策略、貪婪策略、回溯策略、和動(dòng)態(tài)舉策略、遞推策略、遞歸策略、分治策略、貪婪策略、回溯策略、和動(dòng)態(tài)規(guī)劃策略等。規(guī)劃策略等。1.枚舉策略2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部枚

32、舉既是一個(gè)策略，也是一個(gè)算法，還是一種分析問題的手段，所以，枚舉既是一個(gè)策略，也是一個(gè)算法，還是一種分析問題的手段，所以，也稱為枚舉法、窮舉法或試湊法。這種算法策略充分利用計(jì)算機(jī)高速運(yùn)算的也稱為枚舉法、窮舉法或試湊法。這種算法策略充分利用計(jì)算機(jī)高速運(yùn)算的特點(diǎn)，將可能出現(xiàn)的、有窮的情況一一列舉出來，用題目給定的檢驗(yàn)條件來特點(diǎn)，將可能出現(xiàn)的、有窮的情況一一列舉出來，用題目給定的檢驗(yàn)條件來判斷其是否符合條件，枚舉完所有對象，問題最終得以解決。枚舉法常用于判斷其是否符合條件，枚舉完所有對象，問題最終得以解決。枚舉法常用于解決解決“是否存在是否存在”或或“有多少種可能有多少種可能”等類型的問題。等類型的

33、問題。枚舉法在具體的程序?qū)崿F(xiàn)過程中，可以通過循環(huán)結(jié)構(gòu)和分支結(jié)構(gòu)來完成枚舉法在具體的程序?qū)崿F(xiàn)過程中，可以通過循環(huán)結(jié)構(gòu)和分支結(jié)構(gòu)來完成?！纠?-7】我國古代數(shù)學(xué)家張丘建在張丘建算經(jīng)一書中提出了“百錢買百雞問題”：雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一。百錢買百雞，問雞翁、雞母、雞雛各幾何？2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部【分析分析】在本題中可以設(shè)雞翁為在本題中可以設(shè)雞翁為x只，雞母為只，雞母為y只，雞雛為只，雞雛為z只。由題意給出一只。由題意給出一共要用共要用100錢買一百只雞，可將問題簡化為三元一次方程組：錢買一百只雞，可將問題簡化為三元一次方程組：

34、x+y+z=100 （1） 5x+3y+z/3=100 （2）這里這里x,y,z為正整數(shù)，由于雞和錢的總數(shù)都是為正整數(shù)，由于雞和錢的總數(shù)都是100，可以確定，可以確定x，y，z的取值范的取值范圍：圍：0 x20、0y33、0z100。下面用枚舉的方法設(shè)計(jì)本題算法。下面用枚舉的方法設(shè)計(jì)本題算法。2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部算法設(shè)計(jì)一：根據(jù)問題中的約束算法設(shè)計(jì)一：根據(jù)問題中的約束條件，排除一些明顯的不可能的條件，排除一些明顯的不可能的情況，將可能的情況一一列舉出情況，將可能的情況一一列舉出來，即遍歷來，即遍歷x，y，z的所有可能的所有可能組合，最后得到問題的

35、解。流程組合，最后得到問題的解。流程圖如圖所示。圖如圖所示。開始0=x=20輸出x、y、z的值z=z+10=y=335x+3y+z/3=100結(jié)束x=x+1NYYYNN0=z=100 x+y+z=100y=y+1NNYY2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部算法設(shè)計(jì)二：在假設(shè)了雞翁和雞母的算法設(shè)計(jì)二：在假設(shè)了雞翁和雞母的只數(shù)為只數(shù)為x和和y之后，雞雛的數(shù)量就可確之后，雞雛的數(shù)量就可確定為定為100 xy，那么此時(shí)只對，那么此時(shí)只對x，y進(jìn)行枚舉即可，而約束條件就只有一進(jìn)行枚舉即可，而約束條件就只有一個(gè)個(gè)5x3yz/3100，流程圖如圖，流程圖如圖5.13所示。所示

36、。開始0=x=20輸出x、y、z的值0=y=335x+3y+z/3=100結(jié)束x=x+1NYYYNNz=100-x-yy=y+12.遞推策略2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部遞推策略在數(shù)學(xué)上又稱為迭代法或輾轉(zhuǎn)法，其基本思想是從給定的初始條遞推策略在數(shù)學(xué)上又稱為迭代法或輾轉(zhuǎn)法，其基本思想是從給定的初始條件出發(fā)，通過算法（遞推公式）推出可求的新值，再由所得新值代替舊值，然件出發(fā)，通過算法（遞推公式）推出可求的新值，再由所得新值代替舊值，然后按著同樣的算法（遞推公式）又可求得另一個(gè)新值，依此類推，經(jīng)過有限次后按著同樣的算法（遞推公式）又可求得另一個(gè)新值，依此類推，經(jīng)

37、過有限次推導(dǎo)，即可求得最終結(jié)果。遞推的過程就是找出舊值和新值（即相鄰兩項(xiàng)或幾推導(dǎo)，即可求得最終結(jié)果。遞推的過程就是找出舊值和新值（即相鄰兩項(xiàng)或幾項(xiàng)）之間的關(guān)系，即遞推公式。然后通過給定的初始條件，再按照這一規(guī)律來項(xiàng)）之間的關(guān)系，即遞推公式。然后通過給定的初始條件，再按照這一規(guī)律來計(jì)算序列中其余各項(xiàng)。遞推策略更多地用于計(jì)算，如利用輾轉(zhuǎn)相除法求兩個(gè)正計(jì)算序列中其余各項(xiàng)。遞推策略更多地用于計(jì)算，如利用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)的最大公約數(shù)，就體現(xiàn)了這一算法思想。整數(shù)的最大公約數(shù)，就體現(xiàn)了這一算法思想。2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部【例【例5-8】猴子吃桃問題。一只猴

38、子第一天摘下若干猴子吃桃問題。一只猴子第一天摘下若干桃子，當(dāng)即吃了一半，還不過癮，又多吃了一個(gè)，第二桃子，當(dāng)即吃了一半，還不過癮，又多吃了一個(gè)，第二早上又將剩下的桃子吃掉一半，又多吃了一個(gè)。以后每早上又將剩下的桃子吃掉一半，又多吃了一個(gè)。以后每天早上都吃了前一天剩下的一半再多一個(gè)。到第天早上都吃了前一天剩下的一半再多一個(gè)。到第10天早天早上想再吃時(shí)，見只剩下一個(gè)桃子了。求猴子第一天共摘上想再吃時(shí)，見只剩下一個(gè)桃子了。求猴子第一天共摘了多少個(gè)桃子？了多少個(gè)桃子？ 【分析分析】這是一個(gè)遞推問題，因?yàn)楹镒用看纬缘羟耙贿@是一個(gè)遞推問題，因?yàn)楹镒用看纬缘羟耙惶斓囊话胗侄嘁粋€(gè)，則若設(shè)天的一半又多一個(gè)，則若

39、設(shè)xn為第為第n天的桃子數(shù)，它就天的桃子數(shù)，它就是第是第n-1天的桃子數(shù)的一半減天的桃子數(shù)的一半減1個(gè)，即個(gè)，即 那么第那么第n-1天的桃子數(shù)的遞推公式為：天的桃子數(shù)的遞推公式為：1211nnxx211-）（nnxx3. 遞歸策略2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部遞歸策略是利用大問題與其子問題的遞推關(guān)系來解決問題。它通常把一個(gè)大遞歸策略是利用大問題與其子問題的遞推關(guān)系來解決問題。它通常把一個(gè)大型復(fù)雜的問題層層轉(zhuǎn)化為一個(gè)與原問題相似的但規(guī)模較小的問題來求解。遞歸型復(fù)雜的問題層層轉(zhuǎn)化為一個(gè)與原問題相似的但規(guī)模較小的問題來求解。遞歸的能力在于用有限的語句來定義對象的

40、無限集合。遞歸策略只需少量的程序就的能力在于用有限的語句來定義對象的無限集合。遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。在算可描述出解題過程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。在算法或程序設(shè)計(jì)中，具體的處理辦法是一個(gè)過程或函數(shù)在其定義或說明中又直接法或程序設(shè)計(jì)中，具體的處理辦法是一個(gè)過程或函數(shù)在其定義或說明中又直接或間接地調(diào)用自身?；蜷g接地調(diào)用自身。2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部【例【例5-9】斐波那契（】斐波那契（Fibonacci）是中世紀(jì)意大利數(shù)學(xué)家，他在算盤書中）是中世紀(jì)意大利數(shù)學(xué)家，他在算

41、盤書中提出了提出了1對兔子的繁殖問題：如果每對兔子成熟后每月能生對兔子的繁殖問題：如果每對兔子成熟后每月能生1對小兔子，而每對對小兔子，而每對小兔子在出生后的第三個(gè)月開始，每月再生小兔子在出生后的第三個(gè)月開始，每月再生1對小兔子，假定在不發(fā)生死亡的對小兔子，假定在不發(fā)生死亡的情況下，最初的一對兔子在一年末能繁殖成多少對兔子（假定以上兔子都是雌情況下，最初的一對兔子在一年末能繁殖成多少對兔子（假定以上兔子都是雌雄成對）？雄成對）？ 【分析分析】根據(jù)問題描述，可以看出新生兔到第三個(gè)月開始生小兔，之后就可根據(jù)問題描述，可以看出新生兔到第三個(gè)月開始生小兔，之后就可每月生一對小兔，而且不發(fā)生死亡情況，每

42、月生一對小兔，而且不發(fā)生死亡情況，下下表可清楚地分析兔子數(shù)的變化規(guī)律表可清楚地分析兔子數(shù)的變化規(guī)律月份月份1月月2月月3月月4月月5月月6月月7月月8月月9月月10月月11月月12月月小兔小兔111235813213455大兔大兔1123581321345589合計(jì)合計(jì)11235813213455891442022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部假設(shè)第假設(shè)第n個(gè)月的兔子數(shù)目是個(gè)月的兔子數(shù)目是fib(n)，根據(jù)上述分析，可得如下關(guān)系式：，根據(jù)上述分析，可得如下關(guān)系式：2)2()1(21)(nnfibnfibnnfib該公式遞歸地定義了該公式遞歸地定義了Fibonacc

43、i數(shù)列的各項(xiàng)。數(shù)列的各項(xiàng)。用用C程序設(shè)計(jì)語言描述其遞歸函數(shù)為：程序設(shè)計(jì)語言描述其遞歸函數(shù)為：int fib(int n) int f;if(n=0)printf( n=0，數(shù)據(jù)錯(cuò)誤！，數(shù)據(jù)錯(cuò)誤！);else if (n= =1|n= =2)f=1; else f= fib(n-1)+fib(n-2);return f; 開 始fib(1)=1fib(2)=1i=n輸 出 fib(1)、 fib(2)、 、 fib(n)的 值i=3fib(i)=fib(i-1)+fib(i-2)i=i+1結(jié) 束NY4.分治策略2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部在計(jì)算機(jī)科學(xué)中，分

44、治策略是一種很重要的算法策略。字面上的解釋是在計(jì)算機(jī)科學(xué)中，分治策略是一種很重要的算法策略。字面上的解釋是“分分而治之而治之”，就是把一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或相似的子問題，再，就是把一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或相似的子問題，再把子問題分成更小的子問題把子問題分成更小的子問題直到最后子問題可以簡單的直接求解，原問題直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。的解即子問題的解的合并。分治策略的一個(gè)要點(diǎn)是子問題與原問題結(jié)構(gòu)相同，因此子問題也同樣可以利分治策略的一個(gè)要點(diǎn)是子問題與原問題結(jié)構(gòu)相同，因此子問題也同樣可以利用分治策略進(jìn)行求解。用分治策略進(jìn)行求解。如果原

45、問題可分割成如果原問題可分割成k個(gè)子問題，個(gè)子問題，1max，則，則max=A(2)；S3：取：取A(3)和和max比較，如果比較，如果A(3)max，則，則max=A(3)；S4：?。喝(4)和和max比較，如果比較，如果A(4)max，則，則max=A(4)；依此類推依此類推S10：?。喝(10)和和max比較，如果比較，如果A(10)max，則，則max=A(10)；S11：輸出該數(shù)列最大值：輸出該數(shù)列最大值max。開始max=A(1)i=2imax結(jié)束NYYN2.排序問題2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部排序是數(shù)據(jù)處理中最常見的問題之一，它要求將一

46、組數(shù)據(jù)按遞增或遞減的排序是數(shù)據(jù)處理中最常見的問題之一，它要求將一組數(shù)據(jù)按遞增或遞減的次序排列，例如對一個(gè)班的學(xué)生考試成績排序，公司內(nèi)多個(gè)銷售部門月銷售次序排列，例如對一個(gè)班的學(xué)生考試成績排序，公司內(nèi)多個(gè)銷售部門月銷售額排序等等。額排序等等。排序算法有很多種，最常用的有選擇排序法、冒泡排序法、插入排序法、排序算法有很多種，最常用的有選擇排序法、冒泡排序法、插入排序法、合并排序法、希爾排序法等等。不同算法的執(zhí)行效率不同，因此在處理數(shù)據(jù)合并排序法、希爾排序法等等。不同算法的執(zhí)行效率不同，因此在處理數(shù)據(jù)量很大的排序問題時(shí)選擇適當(dāng)?shù)乃惴ň惋@得很重要了。量很大的排序問題時(shí)選擇適當(dāng)?shù)乃惴ň惋@得很重要了。下面

47、以例下面以例5-11為處理對象，比較冒泡排序法、選擇排序法和插入排序法的為處理對象，比較冒泡排序法、選擇排序法和插入排序法的算法思想和操作特點(diǎn)。算法思想和操作特點(diǎn)。2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部【例【例5-11】將數(shù)列】將數(shù)列A中的元素中的元素8，6，9，3，2，7按升序排列。按升序排列。 冒泡排序法冒泡排序法冒泡法排序（升序）的基本思路是：從第一個(gè)元素開始，對數(shù)列中兩兩相冒泡法排序（升序）的基本思路是：從第一個(gè)元素開始，對數(shù)列中兩兩相鄰的元素進(jìn)行比較，如不符合順序要求，就立即交換，直到該數(shù)列的最后一個(gè)鄰的元素進(jìn)行比較，如不符合順序要求，就立即交換，直到該

48、數(shù)列的最后一個(gè)元素。按此方法，數(shù)列中的數(shù)據(jù)經(jīng)過一輪比較移位后，數(shù)列中一些較小的數(shù)就元素。按此方法，數(shù)列中的數(shù)據(jù)經(jīng)過一輪比較移位后，數(shù)列中一些較小的數(shù)就如同氣泡一樣上?。ㄇ耙疲┮粋€(gè)位置，一些較大的數(shù)會下沉（后移）一個(gè)位置如同氣泡一樣上?。ㄇ耙疲┮粋€(gè)位置，一些較大的數(shù)會下沉（后移）一個(gè)位置，而最大的數(shù)會沉底，成為數(shù)列中的最后一個(gè)元素。這時(shí)稱第一輪冒泡排序結(jié)，而最大的數(shù)會沉底，成為數(shù)列中的最后一個(gè)元素。這時(shí)稱第一輪冒泡排序結(jié)束。第二輪冒泡排序只對前束。第二輪冒泡排序只對前n-1個(gè)數(shù)列元素進(jìn)行比較移位即可。依此類推，個(gè)數(shù)列元素進(jìn)行比較移位即可。依此類推，n個(gè)個(gè)數(shù)，經(jīng)過數(shù)，經(jīng)過n-1輪比較移位后完成排序

49、。輪比較移位后完成排序。冒泡排序重復(fù)地走訪要排序的數(shù)列，一次次比較交換，完成排序，這體現(xiàn)冒泡排序重復(fù)地走訪要排序的數(shù)列，一次次比較交換，完成排序，這體現(xiàn)了枚舉策略的思想。了枚舉策略的思想。2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部選擇法排序選擇法排序選擇法排序（升序）的基本思路是：每一趟從待排序的數(shù)據(jù)元素中選出最小的選擇法排序（升序）的基本思路是：每一趟從待排序的數(shù)據(jù)元素中選出最小的一個(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完一個(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。例例5-11用自然語言用自然語言描述算法為：描述算

50、法為：S1：從：從6個(gè)數(shù)中選出最小的數(shù)，與第個(gè)數(shù)中選出最小的數(shù)，與第 1個(gè)數(shù)交換位置；個(gè)數(shù)交換位置；S2：在除第：在除第1 個(gè)數(shù)外的其余個(gè)數(shù)外的其余5個(gè)數(shù)中選最小的數(shù)，與第個(gè)數(shù)中選最小的數(shù)，與第2個(gè)數(shù)交換位置；個(gè)數(shù)交換位置；S3：依此類推，選擇了：依此類推，選擇了5趟后，這個(gè)數(shù)列已按升序排列。趟后，這個(gè)數(shù)列已按升序排列。插入法排序2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部插入排序的基本思想是：把插入排序的基本思想是：把n個(gè)待排序的數(shù)據(jù)分為兩部分：個(gè)待排序的數(shù)據(jù)分為兩部分：R1，R2，Ri-1為已排好序的有序表，為已排好序的有序表，Ri，Ri+1，Rn為未排序的無序表（

51、初始時(shí)，令為未排序的無序表（初始時(shí)，令i=2）。把未排序的無序表中的第）。把未排序的無序表中的第1個(gè)數(shù)據(jù)個(gè)數(shù)據(jù)Ri依次與依次與R，Ri-1比較，并插比較，并插入到有序表的適當(dāng)位置上，使得入到有序表的適當(dāng)位置上，使得R1，R2，Ri-1變?yōu)橐粋€(gè)新的有序表，直變?yōu)橐粋€(gè)新的有序表，直到未排序表中的數(shù)據(jù)元素全部插入到有序表中。圖到未排序表中的數(shù)據(jù)元素全部插入到有序表中。圖5.21說明了例說明了例5-11的數(shù)據(jù)的數(shù)據(jù)按插入排序法進(jìn)行排序的全過程。按插入排序法進(jìn)行排序的全過程。3.查找問題2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部查找是數(shù)據(jù)處理中經(jīng)常使用的一種重要算法。查找過程就

52、是在給定的一列數(shù)查找是數(shù)據(jù)處理中經(jīng)常使用的一種重要算法。查找過程就是在給定的一列數(shù)據(jù)中尋找指定的數(shù)據(jù)及該數(shù)據(jù)在數(shù)列中的位置。常見的查找算法有：順序查據(jù)中尋找指定的數(shù)據(jù)及該數(shù)據(jù)在數(shù)列中的位置。常見的查找算法有：順序查找法和二分法查找法。找法和二分法查找法。（1）順序查找法）順序查找法順序查找，是最原始的要求最低的查找辦法，指的是從數(shù)列的第一個(gè)元素開順序查找，是最原始的要求最低的查找辦法，指的是從數(shù)列的第一個(gè)元素開始，將要查找的數(shù)據(jù)與數(shù)列中的每個(gè)元素，依次進(jìn)行比較，如果二者相等，始，將要查找的數(shù)據(jù)與數(shù)列中的每個(gè)元素，依次進(jìn)行比較，如果二者相等，則查找成功，結(jié)束查找并記錄位置；否則，查找失敗。則查找

53、成功，結(jié)束查找并記錄位置；否則，查找失敗。2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部（2）二分查找）二分查找二分查找又稱折半查找，是一種查找效率較高的查找方法。但該方二分查找又稱折半查找，是一種查找效率較高的查找方法。但該方法要求待查數(shù)據(jù)列必須是有序的，即數(shù)據(jù)是由小到大或由大到小排列的。法要求待查數(shù)據(jù)列必須是有序的，即數(shù)據(jù)是由小到大或由大到小排列的。二分查找二分查找的的基本的思想基本的思想為（為（假設(shè)數(shù)列中元素按升序排列假設(shè)數(shù)列中元素按升序排列）：）：首先，將查找的數(shù)與待查數(shù)列中處于中間位置的數(shù)據(jù)（中點(diǎn)數(shù)據(jù)）首先，將查找的數(shù)與待查數(shù)列中處于中間位置的數(shù)據(jù)（中點(diǎn)數(shù)據(jù)）進(jìn)

54、行比較，如果兩者相等，則查找成功；否則利用中間位置將數(shù)列分成前進(jìn)行比較，如果兩者相等，則查找成功；否則利用中間位置將數(shù)列分成前、后兩個(gè)子數(shù)列，若待查數(shù)據(jù)小于中點(diǎn)數(shù)據(jù)，則進(jìn)一步查找前一子數(shù)列，、后兩個(gè)子數(shù)列，若待查數(shù)據(jù)小于中點(diǎn)數(shù)據(jù)，則進(jìn)一步查找前一子數(shù)列，否則進(jìn)一步查找后一子數(shù)列。其次，在子數(shù)列中重復(fù)以上過程，直到找到否則進(jìn)一步查找后一子數(shù)列。其次，在子數(shù)列中重復(fù)以上過程，直到找到滿足條件的數(shù)據(jù)，使查找成功，或直到再分解的子數(shù)列不存在為止，此時(shí)滿足條件的數(shù)據(jù)，使查找成功，或直到再分解的子數(shù)列不存在為止，此時(shí)查找不成功。查找不成功。2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)

55、部【例【例5-12】 假設(shè)有一組從小到大排列的數(shù)列假設(shè)有一組從小到大排列的數(shù)列A：A(1)、A(2)、A(3)、A(4)、A(5)、A(6)、A(7)、A(8)、A(9)、A(10)，用二分法查找此數(shù)列中是否含有數(shù)據(jù)值為，用二分法查找此數(shù)列中是否含有數(shù)據(jù)值為x的數(shù)。若有，則輸出這個(gè)數(shù)在數(shù)列中的下標(biāo)。若不在，則顯示該數(shù)不存在。的數(shù)。若有，則輸出這個(gè)數(shù)在數(shù)列中的下標(biāo)。若不在，則顯示該數(shù)不存在?！痉治龇治觥考僭O(shè)假設(shè)Low為查找區(qū)間下界的數(shù)列元素下標(biāo)，初值為為查找區(qū)間下界的數(shù)列元素下標(biāo)，初值為0；High為查找區(qū)間為查找區(qū)間上界的數(shù)列元素上標(biāo)，初值為上界的數(shù)列元素上標(biāo)，初值為10，即，即Low=0，H

56、igh=10；需要查找的數(shù)為；需要查找的數(shù)為x。二分查找的算法描述如下二分查找的算法描述如下：S1：求出查找區(qū)間的中間位置元素下標(biāo)：求出查找區(qū)間的中間位置元素下標(biāo)Mid=(int)(High +Low)/2) ；S2：若：若A(Mid)）=x成立，則找到，否則進(jìn)行下面的判斷；成立，則找到，否則進(jìn)行下面的判斷；S3：若：若A(Mid)x），則表明），則表明x在在A(Low)到到A(Mid-1)區(qū)間內(nèi)，則設(shè)置區(qū)間內(nèi)，則設(shè)置High=Mid-1，使查找區(qū)間上界移動(dòng)到新位置；，使查找區(qū)間上界移動(dòng)到新位置；S5：重復(fù)執(zhí)行以上操作；：重復(fù)執(zhí)行以上操作；S6：結(jié)束查找的條件有兩個(gè)：已經(jīng)找到或找不到（：結(jié)束查

57、找的條件有兩個(gè)：已經(jīng)找到或找不到（Low High）。）。5.3 數(shù)據(jù)結(jié)構(gòu)2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部數(shù)據(jù)結(jié)構(gòu)是主要研究組織大量數(shù)據(jù)的方法，即計(jì)算機(jī)存儲、組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是主要研究組織大量數(shù)據(jù)的方法，即計(jì)算機(jī)存儲、組織數(shù)據(jù)的方式及其相互關(guān)系。它用來反映一個(gè)數(shù)據(jù)的內(nèi)部構(gòu)成，即一個(gè)數(shù)據(jù)由哪些成方式及其相互關(guān)系。它用來反映一個(gè)數(shù)據(jù)的內(nèi)部構(gòu)成，即一個(gè)數(shù)據(jù)由哪些成分?jǐn)?shù)據(jù)構(gòu)成，以什么方式構(gòu)成，呈什么結(jié)構(gòu)。分?jǐn)?shù)據(jù)構(gòu)成，以什么方式構(gòu)成，呈什么結(jié)構(gòu)。5.3.1 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)是相互之間存在某種特定關(guān)系的數(shù)據(jù)元素的集合。因此，數(shù)據(jù)結(jié)構(gòu)是相互之

58、間存在某種特定關(guān)系的數(shù)據(jù)元素的集合。因此，也可以把數(shù)據(jù)結(jié)構(gòu)看成是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。也可以把數(shù)據(jù)結(jié)構(gòu)看成是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容可以包含以下幾個(gè)方面：數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容可以包含以下幾個(gè)方面： （1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；（2）在對數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲關(guān)系，即數(shù)據(jù)的）在對數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)；存儲結(jié)構(gòu)；（3）對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。）對各種

59、數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。5.3.2 5.3.2 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部數(shù)據(jù)結(jié)構(gòu)是指相互之間具有一定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)元素之間的關(guān)數(shù)據(jù)結(jié)構(gòu)是指相互之間具有一定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)元素之間的關(guān)系可以是元素之間代表某種含義的自然關(guān)系，也可以是為處理問題方便而人為系可以是元素之間代表某種含義的自然關(guān)系，也可以是為處理問題方便而人為定義的關(guān)系，這種自然或人為定義的定義的關(guān)系，這種自然或人為定義的“關(guān)系關(guān)系”稱為數(shù)據(jù)元素之間的邏輯關(guān)系，稱為數(shù)據(jù)元素之間的邏輯關(guān)系，相應(yīng)的結(jié)構(gòu)稱為邏輯結(jié)構(gòu)。相應(yīng)的結(jié)構(gòu)稱為邏輯結(jié)構(gòu)。數(shù)據(jù)元素之間

60、的邏輯結(jié)構(gòu)有四種基本類型數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)有四種基本類型： 集合集合、線性結(jié)構(gòu)線性結(jié)構(gòu)、樹型結(jié)構(gòu)樹型結(jié)構(gòu)、圖狀結(jié)構(gòu)圖狀結(jié)構(gòu)集合 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 圖形結(jié)構(gòu)5.3.3 5.3.3 數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)2022-3-7太原理工大學(xué).計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院.計(jì)算機(jī)基礎(chǔ)教學(xué)部數(shù)據(jù)元素在計(jì)算機(jī)存儲空間的存放形式就是數(shù)據(jù)的物理結(jié)構(gòu)，也稱為數(shù)據(jù)的存儲數(shù)據(jù)元素在計(jì)算機(jī)存儲空間的存放形式就是數(shù)據(jù)的物理結(jié)構(gòu)，也稱為數(shù)據(jù)的存儲結(jié)構(gòu)。它是數(shù)據(jù)的邏輯結(jié)構(gòu)在存儲器里的實(shí)現(xiàn)，包括數(shù)據(jù)元素的存儲和元素之間結(jié)構(gòu)。它是數(shù)據(jù)的邏輯結(jié)構(gòu)在存儲器里的實(shí)現(xiàn)，包括數(shù)據(jù)元素的存儲和元素之間關(guān)系的表示。關(guān)系的表示。元素之間的關(guān)系在