大學(xué)計(jì)算機(jī)第7講-算法程序與計(jì)算系統(tǒng)之靈魂

1、第7講統(tǒng)進(jìn)行問(wèn)題求解的關(guān)鍵是發(fā)現(xiàn)、構(gòu)造與設(shè)計(jì)求解問(wèn)題的算法。理解：構(gòu)造與設(shè)計(jì)任何一個(gè)算法要經(jīng)過(guò)哪些步驟，在每一步驟中要做哪些事情？算法是計(jì)算學(xué)科和計(jì)算系統(tǒng)的，各學(xué)科利用計(jì)算系內(nèi)容提要2/55基本目標(biāo): 理解算法類問(wèn)題求解框架SpecificGeneralCourse具體實(shí)例一般過(guò)程課程算法類問(wèn)題數(shù)學(xué)建模數(shù)學(xué)建模，離散數(shù)學(xué)(集合論與圖論、數(shù)理邏輯)等問(wèn)題算法策略設(shè)計(jì)求解的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)過(guò)+算法與數(shù)據(jù)結(jié)構(gòu)程算法過(guò)程(控及制結(jié)構(gòu))設(shè)計(jì)思維方程序設(shè)計(jì)語(yǔ)言及高級(jí)語(yǔ)言程序設(shè)計(jì)法算法實(shí)現(xiàn)復(fù)雜性TSP貪心算法程序（C語(yǔ)言）TSP問(wèn)題貪心算法過(guò)程設(shè)計(jì)TSP問(wèn)題貪心算法數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)求解TSP問(wèn)題的算法策略設(shè)計(jì)貪心T

2、SP問(wèn)題數(shù)學(xué)模型TSP問(wèn)題3/551. 算法與算法類問(wèn)題求解算法與算法類問(wèn)題求解-什么是算法-算法類問(wèn)題及求解概述4/551.1 什么是算法?算法u 算法-計(jì)算學(xué)科和計(jì)算?！八惴ā?Algorithm)一詞源于數(shù)學(xué)家的名字：公元825年，的數(shù)學(xué)家阿科瓦里茨米(AlKhowarizmi)寫了著名的波斯教科書(Persian Textbook)，書中概括了進(jìn)行四則算術(shù)運(yùn)算的計(jì)算規(guī)則。u 算法是一個(gè)有窮規(guī)則的集合，它用規(guī)則規(guī)定了解決某一特定類型問(wèn)題的運(yùn)算序列，或者規(guī)定了任務(wù)執(zhí)行或問(wèn)題求解的一系列步驟。如音樂樂譜、太極拳譜等都可看作廣義的算法5/551.2 為什么算法很重要呢?算法、語(yǔ)言與計(jì)算機(jī)程序步

3、驟書寫的規(guī)范、語(yǔ)則、標(biāo)準(zhǔn)的集合是人和計(jì)算機(jī)都能理解的語(yǔ)言計(jì)算機(jī)語(yǔ)言算法程序解決問(wèn)題的步驟計(jì)算機(jī)能夠理解與執(zhí)行的解決問(wèn)題的步驟“是否會(huì)編程序”，本質(zhì)上是“能否想出求解問(wèn)題的算法”，其次才是將算法用計(jì)算機(jī)可以識(shí)別的形式書寫出來(lái)1. 算法與算法類問(wèn)題求解1.3 什么是計(jì)算學(xué)科中的算法?6/55算法示例u 歐幾里德算法：求解兩個(gè)數(shù)的最大公約數(shù)的算法(公元前300年)ü 表述了最大公約數(shù)的求解過(guò)程ü 表述了一個(gè)判定過(guò)程，即判定“m和n是互質(zhì)的”（即除1以外，m和n沒有公約數(shù)）命題的真假。ü 該算法體現(xiàn)了輸入、輸出、有窮規(guī)則、確定性和能行性等算法的基本特征。尋找兩個(gè)正整數(shù)的最

4、大公約數(shù)的歐幾里德算法輸入：正整數(shù)M和正整數(shù)N輸出：M和N的最大公約數(shù)(設(shè)M>N) 算法步驟：Step 1. M除以N,記余數(shù)為RStep 2. 如果R不是0，將N的值賦給M, R的值賦給N, 返回Step 1; 否則, 最大公約數(shù)是N, 輸出N, 算法結(jié)束。7/551.4 具備什么特征才能被認(rèn)為是算法?算法的基本特征ü 有窮性：一個(gè)算法在執(zhí)行有窮步規(guī)則之后必須結(jié)束。ü 確定性：算法的每一個(gè)步驟必須要確切地定義，不得有歧義性。ü 輸入：算法有零個(gè)或多個(gè)的輸入。ü 輸出：算法有一個(gè)或多個(gè)的輸出/結(jié)果，即與輸入有某個(gè)特定關(guān)系的量。ü 能行性：

5、算法中有待執(zhí)行的運(yùn)算和操作必須是相當(dāng)基本的(可以由時(shí)間內(nèi)完成。自動(dòng)完成)。并能在有限 典型的“重復(fù)/循環(huán)”與“迭代”基本運(yùn)算：除法、賦值、邏輯判斷尋找兩個(gè)正整數(shù)的最大公約數(shù)的歐幾里德算法輸入：正整數(shù)M和正整數(shù)N輸出：M和N的最大公約數(shù)(設(shè)M>N) 算法步驟：Step 1. M除以N,記余數(shù)為RStep 2. 如果R不是0，將N的值賦給M, R的值賦給N, 返回Step 1; 否則, 最大公約數(shù)是N, 輸出N, 算法結(jié)束。8/551.5 你知道一些典型的算法類問(wèn)題嗎?算法類問(wèn)題：由一個(gè)算法可以解決的問(wèn)題u 算法(類)問(wèn)題：尋找一個(gè)(唯一的)方法(算法)以解決同一類型的無(wú)窮多個(gè)單個(gè)問(wèn)題系列的

6、問(wèn)題。u 典型問(wèn)題：ü 哥尼斯堡七橋問(wèn)題：“尋找走遍這7座橋且只許走過(guò)每座橋一次最后又回到原出發(fā)點(diǎn)的路徑”“對(duì)給定的任意一個(gè)河道圖與任意多座橋判定 可能不可能每座橋恰好走過(guò)一次?”。ü 梵天塔問(wèn)題：有三根柱子，梵天將64個(gè)直徑大小不一的金盤子按照從大到小的順序依次套放 在第一根柱子上形成一座金塔，要求每次只能移動(dòng) 一個(gè)盤子，盤子只能在三根柱子上來(lái)回移動(dòng)不能放 在他處，在移動(dòng)過(guò)程中三根柱子上的盤子必須始終 保持大盤在下小盤在上。ü 其他如：背包問(wèn)題，丟番圖方程可解性問(wèn)題；9/551.6 你知道TSP問(wèn)題嗎?算法類問(wèn)題示例u TSP問(wèn)題(Traveling Sales

7、man Problem，旅行商問(wèn)題)，威廉哈密爾頓爵士和英國(guó)數(shù)學(xué)家克克曼T.P.Kirkman于19世紀(jì)初提出TSP問(wèn)題u TSP問(wèn)題：有若干個(gè)城市，任何兩個(gè)城市之間的距離都是確定的，現(xiàn)要 求一旅行商從某城市出發(fā)必須經(jīng)過(guò)每一個(gè)城市且只能在每個(gè)城市逗留一次， 最后回到原出發(fā)城市，問(wèn)如何事先確定好一條最短的路線使其旅行的費(fèi)用最少。u TSP是最有代表性的組合優(yōu)化問(wèn)題之一，在半導(dǎo)體制造(線路規(guī)劃)、物流運(yùn)輸(路徑規(guī)劃)等行業(yè)有著廣泛的應(yīng)用。城市之間的距離10/551.7 你知道算法類問(wèn)題求解的一般步驟嗎?算法類問(wèn)題求解框架u 問(wèn)題抽象及數(shù)學(xué)建模：將問(wèn)題抽象為一個(gè)數(shù)學(xué)問(wèn)題，并給出求解該數(shù)學(xué)問(wèn)題的算法模

8、型。u 算法策略設(shè)計(jì)u 算法的數(shù)據(jù)結(jié)構(gòu)和控制結(jié)構(gòu)設(shè)計(jì)：將數(shù)學(xué)模型轉(zhuǎn)換為可由計(jì)算機(jī)自動(dòng)計(jì)算的算法。u 算法的實(shí)現(xiàn)：用程序設(shè)計(jì)語(yǔ)言編寫算法實(shí)現(xiàn)的程序。u 算法的分析：分析算法的正確性和復(fù)雜性，判斷能行性！SpecificGeneralCourse具體實(shí)例一般過(guò)程課程算法類問(wèn)題數(shù)學(xué)建模數(shù)學(xué)建模，離散數(shù)學(xué)(集合論與圖論、數(shù)理邏輯)等問(wèn)題算法策略設(shè)計(jì)求解的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)過(guò)+算法與數(shù)據(jù)結(jié)構(gòu)程算法過(guò)程(控及制結(jié)構(gòu))設(shè)計(jì)思維方程序設(shè)計(jì)語(yǔ)言及高級(jí)語(yǔ)言程序設(shè)計(jì)法算法實(shí)現(xiàn)復(fù)雜性TSP貪心算法程序（C語(yǔ)言）TSP問(wèn)題貪心算法過(guò)程設(shè)計(jì)TSP問(wèn)題貪心算法數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)求解TSP問(wèn)題的算法策略設(shè)計(jì)貪心TSP問(wèn)題數(shù)學(xué)模型TSP問(wèn)

9、題11/552. 數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想-數(shù)學(xué)建模-有不同的算法求解策略2. 數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想2.1 為什么說(shuō)數(shù)學(xué)建模對(duì)于算法很重要?12/55算法類問(wèn)題求解的第一步就是要數(shù)學(xué)建模。u 數(shù)學(xué)建模：是一種數(shù)學(xué)的思考方法，是運(yùn)用數(shù)學(xué)的語(yǔ)言和方法，通過(guò)抽象、簡(jiǎn)化建立對(duì)問(wèn)題進(jìn)行精確描述和定義的數(shù)學(xué)模型。簡(jiǎn)單而言，數(shù)學(xué)建模是用數(shù)學(xué)語(yǔ)言描述實(shí)際現(xiàn)象的過(guò)程，即建立數(shù)學(xué)模型的過(guò)程。u 數(shù)學(xué)模型是對(duì)實(shí)際問(wèn)題的一種數(shù)學(xué)表述，是關(guān)于部分現(xiàn)實(shí)世界為某種目的的一個(gè)抽象的簡(jiǎn)化的數(shù)學(xué)結(jié)構(gòu)。將現(xiàn)實(shí)世界的問(wèn)題抽象成數(shù)學(xué)模型，就可能發(fā)現(xiàn)問(wèn)題的本質(zhì)及其能否求解，甚至找到求解

10、該問(wèn)題的方法和算法。2. 數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想2.1 為什么說(shuō)數(shù)學(xué)建模對(duì)于算法很重要?13/55哥尼斯堡七橋問(wèn)題被抽象成一個(gè)“圖(Graph)”-由節(jié)點(diǎn)和邊所構(gòu)成的一種結(jié)構(gòu)，-依據(jù)“圖”，可發(fā)現(xiàn)該問(wèn)題所蘊(yùn)含的許多性質(zhì)：u “回路-從一個(gè)節(jié)點(diǎn)出發(fā)最后又回到該節(jié)點(diǎn)的一條路徑”u “連通兩個(gè)節(jié)點(diǎn)間有路徑相連接”u “可達(dá)從一個(gè)節(jié)點(diǎn)出發(fā)能夠到達(dá)另一個(gè)節(jié)點(diǎn)”u “經(jīng)過(guò)圖中每邊一次且僅一次的回路”u “經(jīng)過(guò)圖中每個(gè)節(jié)點(diǎn)一次且僅一次的回路”u 什么情況下有解，什么情況下無(wú)解？u 注：離散數(shù)學(xué)或者集合論與圖論課程將介紹圖的有關(guān)性質(zhì)和方法。如果能抽象成數(shù)學(xué)模型，則可將一個(gè)具體問(wèn)題的求解，推廣為一類問(wèn)

11、題的求解！2.數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想2.2 數(shù)學(xué)建模要做到怎樣?14/55TSP問(wèn)題的數(shù)學(xué)模型2.數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想2.3 算法思想或者算法策略對(duì)問(wèn)題求解有什么影響?15/55算法策略設(shè)計(jì)-算法思想當(dāng)數(shù)學(xué)建模完成后，就要設(shè)計(jì)算法的策略或者說(shuō)問(wèn)題求解的策略。u TSP問(wèn)題的基本求解策略u(píng) 遍歷：列出每一條可供選擇的路線，計(jì)算出每條路線的總里程，最后從中選出一條最短的路線。u 出現(xiàn)的問(wèn)題是：組合ü 路徑組合數(shù)目：(n-1)!ü 20個(gè)城市，遍歷總數(shù)1.216×1017ü 計(jì)算機(jī)以每秒檢索1000萬(wàn)條路線的計(jì)算所有路徑組合及其長(zhǎng)度速度，

12、需386年。城市之間的距離2.數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想2.3 算法思想或者算法策略對(duì)問(wèn)題求解有什么影響?16/55u TSP問(wèn)題的難解性：隨著城市數(shù)量的上升，TSP問(wèn)題的“遍歷”方法計(jì)算量劇增，計(jì)算將難以承受。u 2001年解決了德國(guó)15112個(gè)城市的TSP問(wèn)題，使用了美國(guó)Rice大學(xué)和普林斯頓大學(xué)之間Alpha 處理器組成的110臺(tái)計(jì)算機(jī)，所有計(jì)互連的、速度為500MHz 的CompaqEV6算機(jī)花費(fèi)的時(shí)間之和為22.6年。AnoptimalTSPtourthrough largest cities. It is theGermanys 15shortest among 43 589

13、 145 600 possible tours visiting each city exactly once.2.數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想2.4 有哪些算法策略?17/55算法策略設(shè)計(jì)-算法思想u TSP問(wèn)題，有沒有其他求解算法呢？u 最優(yōu)解 vs. 可行解u 不同的算法設(shè)計(jì)策略：ü 遍歷、搜索算法ü 分治算法ü 貪心算法ü 動(dòng)態(tài)規(guī)劃算法ü u 可選取一種合適的策略來(lái)求解TSP問(wèn)題最優(yōu)解可行解TSP問(wèn)題的可行解與最優(yōu)解示意2.數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想2.5 為什么稱為“貪心算法”?18/55貪心算法城市之間的距離u 貪心算法是

14、一種算法策略，或者說(shuō)問(wèn)題求解的策略?；舅枷搿敖癯芯平癯怼薄?#252; 一定要做當(dāng)前情況下的最好選擇，否則將來(lái)可能會(huì)后悔，故名“貪心”。u TSP問(wèn)題的貪心算法求解思想ü 從某一個(gè)城市開始，每次選擇一個(gè)城市，直到所有 城市都被走完。ü 每次在選擇下一個(gè)城市的時(shí)候，只考慮當(dāng)前情況，保證迄今為止經(jīng)過(guò)的路徑總距離最短。026813AAAAABBBBCCCDDA(a)(b)(c)(d)(e)19/553.算法設(shè)計(jì)-算法思想的精確表達(dá)算法設(shè)計(jì)-算法思想的精確表達(dá)(I)-算法的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)-算法的控制結(jié)構(gòu)設(shè)計(jì)及其表達(dá)方法-TSP算法解讀3. 算法設(shè)計(jì)-算法思想的精確表達(dá)3.1 算

15、法設(shè)計(jì)包括什么?20/55算法設(shè)計(jì)n 算法的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)-問(wèn)題或算法相關(guān)的數(shù)據(jù)之間的邏輯關(guān)系及關(guān)系的設(shè)計(jì) 如何將數(shù)學(xué)模型中的數(shù)據(jù)轉(zhuǎn)為計(jì)算機(jī)可以和處理的數(shù)據(jù)？ n 算法的控制結(jié)構(gòu)設(shè)計(jì)-算法的計(jì)算規(guī)則或計(jì)算步驟設(shè)計(jì) 如何構(gòu)造和表達(dá)處理的規(guī)則，以便能夠按規(guī)則逐步計(jì)算出結(jié)果?3. 算法設(shè)計(jì)-算法思想的精確表達(dá)3.2 什么是數(shù)據(jù)結(jié)構(gòu)?21/55數(shù)據(jù)結(jié)構(gòu)u 如何組織、記憶、改變和操作數(shù)據(jù)的集合呢？數(shù)據(jù)存在什么結(jié)構(gòu)呢？ü 數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)之間的關(guān)系；數(shù)學(xué)模型中反映的通常是數(shù)據(jù)的邏輯結(jié)構(gòu)。ü 數(shù)據(jù)的的有順序結(jié)構(gòu)：在反映數(shù)據(jù)邏輯關(guān)系的原則下，數(shù)據(jù)在器中的方式。典型結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)。結(jié)構(gòu)的基

16、本運(yùn)算：(1)建立數(shù)據(jù)結(jié)構(gòu)；(2)清除數(shù)據(jù)結(jié)構(gòu)；(3)ü 面向數(shù)據(jù)數(shù)據(jù)元素；(4)刪除數(shù)據(jù)元素；(5)更新數(shù)據(jù)元素；(6)查找數(shù)據(jù)元素；(7)按序重新排列；(8)判定某個(gè)數(shù)據(jù)結(jié)構(gòu)是否為空，或是否已達(dá)到最大允許的容量；(9)統(tǒng)計(jì)數(shù)據(jù)元素的個(gè)數(shù)等。u 數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)、結(jié)構(gòu)及其操作的總稱，它提供了問(wèn)題求解/算法的數(shù)據(jù)機(jī)制。3. 算法設(shè)計(jì)-算法思想的精確表達(dá)3.2 什么是數(shù)據(jù)結(jié)構(gòu)?22/55數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)典型的數(shù)據(jù)結(jié)構(gòu)- “樹”示例結(jié)構(gòu)中, 用一個(gè)指針表達(dá)數(shù)據(jù)之間的邏輯關(guān)系數(shù)據(jù)的結(jié)構(gòu)數(shù)據(jù)元素對(duì)應(yīng)數(shù)據(jù)元素的指針指向該元素的父元素?cái)?shù)據(jù)的邏輯結(jié)構(gòu)1601207030150501003.

17、算法設(shè)計(jì)-算法思想的精確表達(dá)3.2 什么是數(shù)據(jù)結(jié)構(gòu)?23/55數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)通過(guò)指針的變化, 不改變數(shù)據(jù)的, 但卻改變了數(shù)據(jù)之間的邏輯關(guān)系數(shù)據(jù)的結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)70301003. 算法設(shè)計(jì)-算法思想的精確表達(dá)3.3 同樣的邏輯結(jié)構(gòu)可以有不同的24/55結(jié)構(gòu)嗎?數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)數(shù)據(jù)的結(jié)構(gòu)典型的數(shù)據(jù)結(jié)構(gòu)- “樹”示例數(shù)據(jù)元素結(jié)構(gòu), 用兩個(gè)指針另一種表達(dá)數(shù)據(jù)之間的邏輯關(guān)系對(duì)應(yīng)數(shù)據(jù)元素的指針指向該元的左側(cè)子結(jié)點(diǎn)對(duì)應(yīng)數(shù)據(jù)元素的指針指向該元的右側(cè)子結(jié)點(diǎn)數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)不同，數(shù)據(jù)之間的操作方法也是不同的7030100左素右素3. 算法設(shè)計(jì)-算法思想的精確表達(dá)3.3 同樣的邏輯結(jié)構(gòu)可以有不同的25/55

18、結(jié)構(gòu)嗎?數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)典型的數(shù)據(jù)結(jié)構(gòu)- “樹”示例結(jié)構(gòu), 用兩個(gè)指針(左指針和右指針)表達(dá)數(shù)據(jù)之間的邏輯關(guān)系另一種 動(dòng)手練習(xí)一下Null數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)703070301101001003. 算法設(shè)計(jì)-算法思想的精確表達(dá)3.4 多元素變量結(jié)構(gòu)是怎樣的?26/55多元素變量及其程序處理(前講介紹的)u 向量或列表或數(shù)組。列M2,3u 矩陣或表12341向量實(shí)例2表實(shí)例行34Sum=0;For I =1 to 4 Step 1n = 4;Sum=0;For J =0 to n Step 1For J =1 to 4 Step 1 Sum = Sum + MIJ;Next JSum =

19、Sum + mark J ;Next JAvg = Sum/n;Next IAvg = Sum/16;11252225453984421280100348375163. 算法設(shè)計(jì)-算法思想的精確表達(dá)3.5 一個(gè)問(wèn)題中應(yīng)該設(shè)計(jì)哪些數(shù)據(jù)結(jié)構(gòu)?27/55TSP問(wèn)題的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)u 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)就是針對(duì)選定的算法策略，設(shè)計(jì)其相應(yīng)的數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算規(guī)則。不同的算法可能有不同的數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算規(guī)則！為編號(hào): A-1, B-2, C-3, D-4城市城市間距離關(guān)系: 表或二維數(shù)組D，用Dij或Di,j來(lái)確定欲處理的每一個(gè)元素DD23路徑/解: 一維數(shù)組S，用Sj來(lái)確定每一個(gè)元素SA->D->C-

20、>B->AS1S2S3S4143228/553.算法設(shè)計(jì)-算法思想的精確表達(dá)算法設(shè)計(jì)-算法思想的精確表達(dá)(II)-算法的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)-算法的控制結(jié)構(gòu)設(shè)計(jì)及其表達(dá)方法-TSP算法解讀3. 算法設(shè)計(jì)-算法思想的精確表達(dá)3.6 怎樣表達(dá)算法的步驟呢?29/55算法與程序的基本控制結(jié)構(gòu)ü 順序結(jié)構(gòu)：“”，是按順序執(zhí)行一條條規(guī)則的一種結(jié)構(gòu) 。ü 分支結(jié)構(gòu)：“” ，Q是某些邏輯條件，即按條件判斷結(jié)果決定執(zhí)行哪些規(guī)則的一種結(jié)構(gòu) 。ü 循環(huán)結(jié)構(gòu)：控制指令或規(guī)則的多次執(zhí)行的一種結(jié)構(gòu)-迭代(iteration)u 循環(huán)結(jié)構(gòu)又分為有界循環(huán)結(jié)構(gòu)和條件循環(huán)結(jié)構(gòu)。ü 有

21、界循環(huán)： “”，其中N是一個(gè)整數(shù)。ü 條件循環(huán)：某些時(shí)候稱為循環(huán)，“”或”，其中Q是條件?！爱?dāng)Q成立時(shí)反復(fù)執(zhí)行A重復(fù)執(zhí)行A直到條件Q成立執(zhí)行A指令N次如果Q成立，那么執(zhí)行A，否則執(zhí)行B執(zhí)行A，然后執(zhí)行B3. 算法設(shè)計(jì)-算法思想的精確表達(dá)3.7 怎樣繪制流程圖?30/55算法與程序構(gòu)造的表達(dá)方法：程序流程圖流程圖的基本表示符號(hào)ü 矩形框：表示一組順序執(zhí)行的規(guī)則或者程序語(yǔ)句。ü 菱形框：表示條件判斷，并根據(jù)判斷結(jié)果執(zhí)行不同的分支。ü 圓形框：表示算法或程序的開始或結(jié)束。ü 箭頭線：表示算法或程序的。矩形框表示一組順序執(zhí)行的語(yǔ)句菱形框表示判斷語(yǔ)句，決

22、定下一步程序的圓形框表示程序的起始和結(jié)束帶箭頭的線段表示程序的3. 算法設(shè)計(jì)-算法思想的精確表達(dá)3.7 怎樣繪制流程圖?31/55算法與程序構(gòu)造的表達(dá)方法：程序流程圖開始u 三種控制結(jié)構(gòu)的流程圖表示方法示意開始開始否循環(huán)控制條件成立？是否條件成立否？是需循環(huán)執(zhí)行的規(guī)則或語(yǔ)句。即：循環(huán)體循環(huán)結(jié)束修改部分結(jié)束結(jié)束結(jié)束順序結(jié)構(gòu)的流程圖分支結(jié)構(gòu)的流程圖循環(huán)結(jié)構(gòu)的流程圖第n條規(guī)則或語(yǔ)句條件成立時(shí)執(zhí)行的規(guī)則或語(yǔ)句條件不成立時(shí)執(zhí)行的規(guī)則或語(yǔ)句第1條規(guī)則或語(yǔ)句初始化部分3. 算法設(shè)計(jì)-算法思想的精確表達(dá)3.7 怎樣繪制流程圖?32/55算法與程序構(gòu)造的表達(dá)方法：程序流程圖開始u 循環(huán)結(jié)構(gòu)的兩種情況的流程圖表示

23、方法示意開始循環(huán)未結(jié)束否循環(huán)控制條件成立？是循環(huán)控制條件成立？循環(huán)結(jié)束需循環(huán)執(zhí)行的規(guī)則或語(yǔ)句是否修改部分結(jié)束有界循環(huán)結(jié)構(gòu)的流程圖(循環(huán)次數(shù)確定)條件循環(huán)結(jié)構(gòu)的流程圖(循環(huán)次數(shù)不確定)結(jié)束修改部分初始化部分需循環(huán)執(zhí)行的規(guī)則或語(yǔ)句初始化部分算法與程序構(gòu)造的表達(dá)方法：程序流程圖u 算法思想及算法流程圖表示示例u 歐幾里德算法流程圖3. 算法設(shè)計(jì)-算法思想的精確表達(dá)33/553.7 怎樣繪制流程圖?開始否r=0?是結(jié)束輸出n將n置換為m，r 置換為n以n除m，并令所得余數(shù)為r3. 算法設(shè)計(jì)-算法思想的精確表達(dá)3.8 自然語(yǔ)言表述算法有什么問(wèn)題?34/55算法與程序構(gòu)造的表達(dá)方法：步驟描述法u 步驟描述

24、法，即用人們?nèi)粘Ｊ褂玫恼Z(yǔ)言和數(shù)學(xué)語(yǔ)言描述算法的步驟。u 例如：sum=1+2+3+4+n求和問(wèn)題的算法描述自然語(yǔ)言表示的算法容易出現(xiàn)二義性、不確定性等問(wèn)題Start of the algorithm(算法開始)(1) 輸入N的值；(2) 設(shè) i 的值為1；sum的值為0；(3) 如果 i<=N，則執(zhí)行第(4)步，否則轉(zhuǎn)到第(7)步執(zhí)行； (4)計(jì)算 sum + i，并將結(jié)果賦給sum；(5)計(jì)算 i+1，并將結(jié)果賦給i; (6)返回到第3步繼續(xù)執(zhí)行； (7)輸出sum的結(jié)果。End of the algorithm(算法結(jié)束)35/553.算法設(shè)計(jì)-算法思想的精確表達(dá)算法設(shè)計(jì)-算法思想的

25、精確表達(dá)(III)-算法的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)-算法的控制結(jié)構(gòu)設(shè)計(jì)及其表達(dá)方法-TSP算法解讀3. 算法設(shè)計(jì)-算法思想的精確表達(dá)3.9 算法的控制結(jié)構(gòu)如何設(shè)計(jì)?36/55開始求解TSP問(wèn)題的遍歷算法ü 遍歷所有的組合路徑；ü 累加一條路徑的距離之和；ü 判斷某條路徑的距離是不是比當(dāng)前最短路徑距離短；ü 如果是，則用新路徑取代當(dāng)前將思想/策略轉(zhuǎn)變?yōu)椤安襟E”最短路徑，并其距離；比當(dāng)前最短距離小嗎？否ü 直到所有路徑比較完畢；u 是將該路徑為當(dāng)前最短路徑，并用其距離值更新當(dāng)前最短距離是否所有路徑組合完畢否？結(jié)束輸出當(dāng)前最短路徑及當(dāng)前最短距離組合一條新路徑并計(jì)

26、算該路徑的距離當(dāng)前最短路徑設(shè)為空，當(dāng)前最短距離設(shè)為最大值3. 算法設(shè)計(jì)-算法思想的精確表達(dá)3.9 算法的控制結(jié)構(gòu)如何設(shè)計(jì)?37/55步驟描述法表示的求解TSP問(wèn)題的貪心算法ü 城市用數(shù)字編號(hào)來(lái)表示,1,2,Nü 任何兩個(gè)城市的距離中在數(shù)組Di,jü 依次在S1,的城市記過(guò)的城市編號(hào)被S2, , SN中,即第i 次錄在Si中。ü Step(1)：從第1個(gè)城市開始將城市編號(hào)1賦值給S1。起，ü Step(6)：第I次的城市為城市j，其距第I-1次城市的距離最短。Start of the Algorithm(1) S1=1;(2) Sum=0;(3)

27、 初始化距離數(shù)組DN, N; (4) I=2;(5) 從所有未過(guò)的城市中查找距離SI-1最近的城市j;(6) SI=j;(7) I=I+1;(8) Sum=Sum+Dtemp;(9) 如果I<=N，轉(zhuǎn)步驟(5)，否則，轉(zhuǎn)步驟(10);(11) Sum=Sum+D1, j；(12) 逐個(gè)輸出SN中的全部元素; (13)輸出Sum。End of the Algorithm3. 算法設(shè)計(jì)-算法思想的精確表達(dá)3.9 算法的控制結(jié)構(gòu)如何設(shè)計(jì)?38/55步驟描述法表示的求解TSP問(wèn)題的貪心算法(Cont.)u 前述第5步“從所有未一步細(xì)化過(guò)的城市中查找距離SI-1最近的城市j”還是不夠明確，需要進(jìn)(

28、5.1)K=2;(5.2)將Dtemp設(shè)為一個(gè)大數(shù)(比所有兩個(gè)城市之間的距離都大)(5.3)L=1；(5.4)如果SL=K，轉(zhuǎn)步驟5.8；/該城市已出現(xiàn)過(guò)，跳過(guò)(5.5)L=L+1；(5.6)如果L<I，轉(zhuǎn)5.4；(5.7)如果DK,SI-1<Dtemp; j=K; DtempDK,SI-1；(5.8)K=K+1;(5.9)如果K<=N，轉(zhuǎn)步驟5.3。3. 算法設(shè)計(jì)-算法思想的精確表達(dá)3.9 算法的控制結(jié)構(gòu)如何設(shè)計(jì)?39/55流程圖表示的求解TSP問(wèn)題的貪心算法3. 算法設(shè)計(jì)-算法思想的精確表達(dá)3.10 你能夠讀懂流程圖嗎?40/55算法思想解讀u 計(jì)算學(xué)科的學(xué)生不僅能夠設(shè)計(jì)

29、算法，而且會(huì)描述和表達(dá)算法，更要能讀懂算法。內(nèi)層循環(huán)，L從1至I-1, 循環(huán)判斷第K個(gè)城市是否是已過(guò)的城市，如是則不參加最小距離的比較；中層循環(huán), K從第2個(gè)城市至第N個(gè)城市循環(huán), 判斷DK, SI-1是否是最小值，j了最小距離的城市號(hào)K。外層循環(huán)，I從2至N循環(huán)；I-1個(gè)城市過(guò)，正在找與第I-1個(gè)城市最 已近距離的城市；已在S中。過(guò)的城市號(hào)41/554.算法實(shí)現(xiàn)-程序設(shè)計(jì)算法實(shí)現(xiàn)-程序設(shè)計(jì)4. 算法實(shí)現(xiàn)-程序設(shè)計(jì)4.1 算法實(shí)現(xiàn)要選定計(jì)算機(jī)語(yǔ)言，42/55?算法的實(shí)現(xiàn)u 程序是算法的一種相容(Compatible)的表示，是利用計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言對(duì)算法描述的結(jié)果，是可以在計(jì)算機(jī)上執(zhí)行的算法。

30、u 計(jì)算機(jī)語(yǔ)言是書寫算法步驟地規(guī)范、標(biāo)準(zhǔn)、語(yǔ)則等，以便使人和計(jì)算機(jī)能夠理解用計(jì)算機(jī)語(yǔ)言編寫出的程序(注：更重要的是使計(jì)算機(jī)能夠理解)。4. 算法實(shí)現(xiàn)-程序設(shè)計(jì)4.1 算法實(shí)現(xiàn)要選定計(jì)算機(jī)語(yǔ)言，43/55?算法的實(shí)現(xiàn)u 程序設(shè)計(jì)過(guò)程：一般經(jīng)過(guò)編輯源程序è編譯èè執(zhí)行。所謂編輯源程序是利用程序編輯器，按照計(jì)算機(jī)語(yǔ)言的規(guī)范書寫程序的過(guò)程；所謂編譯是將編制好的源程序代碼程序(又稱為目標(biāo)代碼)的過(guò)程。所謂翻譯成可以執(zhí)行的是將目標(biāo)代碼與公用函數(shù)庫(kù)中的函數(shù)實(shí)現(xiàn)代碼集成起來(lái)形成最終可執(zhí)行程序的過(guò)程。所謂執(zhí)行就是程序的運(yùn)行過(guò)程。u 計(jì)算機(jī)語(yǔ)言程序設(shè)計(jì)環(huán)境通常由一套書寫程序的語(yǔ)則、一

31、個(gè)編譯程序、一個(gè)程序和一組編譯好的公用函數(shù)庫(kù)構(gòu)成。有些計(jì)算機(jī)語(yǔ)言同時(shí)也提供了相應(yīng)的編程環(huán)境、調(diào)試環(huán)境及集成開發(fā)環(huán)境等。4. 算法實(shí)現(xiàn)-程序設(shè)計(jì)44/554.2 你能用某一種計(jì)算機(jī)語(yǔ)言書寫出TSP問(wèn)題貪心算法的程序嗎?算法的實(shí)現(xiàn)TSP 問(wèn)題貪心算法程序?qū)嵗?5/555.高級(jí)問(wèn)題初探: 算法分析與計(jì)算復(fù)雜性高級(jí)問(wèn)題初探:算法分析與計(jì)算復(fù)雜性5. 高級(jí)問(wèn)題初探: 算法分析與計(jì)算復(fù)雜性5.1 算法是正確的嗎?46/55算法分析與計(jì)算復(fù)雜性算法是正確的嗎? uu 算法的正確性問(wèn)題：ü 問(wèn)題求解的過(guò)程、方法算法是正確的嗎？算法的輸出是問(wèn)題的解嗎？ü 20世紀(jì)60年代，美國(guó)一架發(fā)往金星的

32、航天飛機(jī)由于控制程序出錯(cuò)而u 算法的效果評(píng)價(jià)：ü 算法的輸出是最優(yōu)解還是可行解？如果是可行解，與最優(yōu)解的偏差多大？u 兩種評(píng)價(jià)方法：ü 證明方法：利用數(shù)學(xué)方法證明；丟失在太空中ü分析方法：產(chǎn)生或選取大量的、具有代表性的問(wèn)題實(shí)例，利用該算法對(duì)這些問(wèn)題實(shí)例進(jìn)行求解，并對(duì)算法產(chǎn)生的結(jié)果進(jìn)行統(tǒng)計(jì)分析。算法獲得的解是最優(yōu)的嗎?5. 高級(jí)問(wèn)題初探: 算法分析與計(jì)算復(fù)雜性5.1 算法是正確的嗎?47/55算法分析與計(jì)算復(fù)雜性算法分析示例：TSP問(wèn)題貪心u TSP問(wèn)題貪心算法的正確性評(píng)價(jià)：ü 直觀上只需檢查算法的輸出結(jié)果中，每個(gè)城市出現(xiàn)且僅出現(xiàn)一次，該結(jié)果即是TSP問(wèn)題

33、的可 行解，說(shuō)明算法正確地求解了這些問(wèn)題實(shí)例u TSP問(wèn)題貪心算法的效果評(píng)價(jià)：ü 如果實(shí)例的最優(yōu)解已知（問(wèn)題規(guī)模小或問(wèn)題已被成功求解），利用統(tǒng)計(jì)方法對(duì)若干問(wèn)題實(shí)例 的算法結(jié)果與最優(yōu)解進(jìn)行對(duì)比分析，即可對(duì)其進(jìn)行效果評(píng)價(jià)；ü 對(duì)于較大規(guī)模的問(wèn)題實(shí)例，其最優(yōu)解往往是未知的，因此，算法的效果評(píng)價(jià)只能借助于與前人算法結(jié)果的比較。5.高級(jí)問(wèn)題初探: 算法分析與計(jì)算復(fù)雜性5.2 算法的計(jì)算時(shí)間有多長(zhǎng)?48/55算法分析與計(jì)算復(fù)雜性算法獲得結(jié)果的時(shí)間有多長(zhǎng)?u 另一個(gè)問(wèn)題：算法是能夠執(zhí)行的嗎？u 分析u 算法的效率：時(shí)間效率和空間效率u 時(shí)間復(fù)雜性:如果一個(gè)問(wèn)題的規(guī)模是n，解這一問(wèn)題的某一算法所需要的時(shí)間為T(n)，它是n的某一函數(shù)，T(n)稱為這一算法的“時(shí)間復(fù)雜性”。u “大O記法”：ü 基本參數(shù) n問(wèn)題實(shí)例的規(guī)模ü 把復(fù)雜性或運(yùn)行時(shí)間表達(dá)為n的函數(shù)。ü “O”表示量級(jí) (order)，允許使用“=”代替“”，如n2+n+1 =(n2) 。u 算法的空間復(fù)雜度：算法在執(zhí)行過(guò)程中所占空間的大小。5.高級(jí)問(wèn)題初探: 算法分析與計(jì)算復(fù)雜性5.2 算法的計(jì)算時(shí)間有多長(zhǎng)?49/55算法分析與計(jì)算復(fù)雜性算法復(fù)雜性分析示例主要關(guān)注點(diǎn)：循環(huán)的層數(shù)sum=0；（1次）for( i