算法程序與計(jì)算系統(tǒng)之靈魂最全課件

算法程序與計(jì)算系統(tǒng)之靈魂算法程序與計(jì)算系統(tǒng)之靈魂基本目標(biāo):

理解算法類問題求解框架內(nèi)容提要基本目標(biāo):理解算法類問題求解框架內(nèi)容提要算法：程序與計(jì)算系統(tǒng)之靈魂1.算法與算法類問題求解算法與算法類問題求解----什么是算法----算法類問題及求解概述算法：程序與計(jì)算系統(tǒng)之靈魂算法與算法類問題求解算法算法---計(jì)算學(xué)科和計(jì)算機(jī)器的靈魂?！八惴ā?Algorithm)一詞源于數(shù)學(xué)家的名字：公元825年，阿拉伯?dāng)?shù)學(xué)家阿科瓦里茨米(AlKhowarizmi)寫了著名的《波斯教科書》(PersianTextbook)，書中概括了進(jìn)行四則算術(shù)運(yùn)算的計(jì)算規(guī)則。算法是一個(gè)有窮規(guī)則的集合，它用規(guī)則規(guī)定了解決某一特定類型問題的運(yùn)算序列，或者規(guī)定了任務(wù)執(zhí)行或問題求解的一系列步驟。1.算法與算法類問題求解1.1什么是算法?如音樂樂譜、太極拳譜等都可看作廣義的算法算法算法---計(jì)算學(xué)科和計(jì)算機(jī)器的靈魂。“算法”(Algor算法解決問題的步驟程序計(jì)算機(jī)能夠理解與執(zhí)行的解決問題的步驟計(jì)算機(jī)語言步驟書寫的規(guī)范、語法規(guī)則、標(biāo)準(zhǔn)的集合是人和計(jì)算機(jī)都能理解的語言算法、語言與計(jì)算機(jī)程序1.算法與算法類問題求解1.2為什么算法很重要呢?“是否會(huì)編程序”，本質(zhì)上是“能否想出求解問題的算法”，其次才是將算法用計(jì)算機(jī)可以識(shí)別的形式書寫出來算法解決問題程序計(jì)算機(jī)能夠理解與計(jì)算機(jī)語言步驟書寫的規(guī)范、語歐幾里德算法：求解兩個(gè)數(shù)的最大公約數(shù)的算法(公元前300年)表述了最大公約數(shù)的求解過程表述了一個(gè)判定過程，即判定“m和n是互質(zhì)的”（即除1以外，m和n沒有公約數(shù)）命題的真假。該算法體現(xiàn)了輸入、輸出、有窮規(guī)則、確定性和能行性等算法的基本特征。尋找兩個(gè)正整數(shù)的最大公約數(shù)的歐幾里德算法輸入：正整數(shù)M和正整數(shù)N輸出：M和N的最大公約數(shù)(設(shè)M>N)算法步驟：Step1.

M除以N,記余數(shù)為RStep2.如果R不是0，將N的值賦給M,R的值賦給N,返回Step1;否則,最大公約數(shù)是N,輸出N,算法結(jié)束。算法示例1.算法與算法類問題求解1.3什么是計(jì)算學(xué)科中的算法?歐幾里德算法：求解兩個(gè)數(shù)的最大公約數(shù)的算法(公元前300年)有窮性：一個(gè)算法在執(zhí)行有窮步規(guī)則之后必須結(jié)束。確定性：算法的每一個(gè)步驟必須要確切地定義，不得有歧義性。輸入：算法有零個(gè)或多個(gè)的輸入。輸出：算法有一個(gè)或多個(gè)的輸出/結(jié)果，即與輸入有某個(gè)特定關(guān)系的量。能行性：算法中有待執(zhí)行的運(yùn)算和操作必須是相當(dāng)基本的(可以由機(jī)器自動(dòng)完成)。并能在有限時(shí)間內(nèi)完成。算法的基本特征1.算法與算法類問題求解1.4具備什么特征才能被認(rèn)為是算法?基本運(yùn)算：除法、賦值、邏輯判斷典型的“重復(fù)/循環(huán)”與“迭代”尋找兩個(gè)正整數(shù)的最大公約數(shù)的歐幾里德算法輸入：正整數(shù)M和正整數(shù)N輸出：M和N的最大公約數(shù)(設(shè)M>N)算法步驟：Step1.

M除以N,記余數(shù)為RStep2.如果R不是0，將N的值賦給M,R的值賦給N,返回Step1;否則,最大公約數(shù)是N,輸出N,算法結(jié)束。有窮性：一個(gè)算法在執(zhí)行有窮步規(guī)則之后必須結(jié)束。算法的基本特征算法(類)問題：尋找一個(gè)(唯一的)方法(算法)以解決同一類型的無窮多個(gè)單個(gè)問題系列的問題。典型問題：哥尼斯堡七橋問題：“尋找走遍這7座橋且只許走過每座橋一次最后又回到原出發(fā)點(diǎn)的路徑”“對(duì)給定的任意一個(gè)河道圖與任意多座橋判定可能不可能每座橋恰好走過一次?”。梵天塔問題：有三根柱子，梵天將64個(gè)直徑大小不一的金盤子按照從大到小的順序依次套放在第一根柱子上形成一座金塔，要求每次只能移動(dòng)一個(gè)盤子，盤子只能在三根柱子上來回移動(dòng)不能放在他處，在移動(dòng)過程中三根柱子上的盤子必須始終保持大盤在下小盤在上。其他如：背包問題，丟番圖方程可解性問題；……1.算法與算法類問題求解1.5你知道一些典型的算法類問題嗎?算法類問題：由一個(gè)算法可以解決的問題算法(類)問題：尋找一個(gè)(唯一的)方法(算法)以解決同一類型TSP問題(TravelingSalesmanProblem，旅行商問題)，威廉哈密爾頓爵士和英國(guó)數(shù)學(xué)家克克曼于19世紀(jì)初提出TSP問題．TSP問題：有若干個(gè)城市，任何兩個(gè)城市之間的距離都是確定的，現(xiàn)要求一旅行商從某城市出發(fā)必須經(jīng)過每一個(gè)城市且只能在每個(gè)城市逗留一次，最后回到原出發(fā)城市，問如何事先確定好一條最短的路線使其旅行的費(fèi)用最少。TSP是最有代表性的組合優(yōu)化問題之一，在半導(dǎo)體制造(線路規(guī)劃)、物流運(yùn)輸(路徑規(guī)劃)等行業(yè)有著廣泛的應(yīng)用。城市之間的距離1.算法與算法類問題求解1.6你知道TSP問題嗎?算法類問題示例TSP問題(TravelingSalesmanProbl問題抽象及數(shù)學(xué)建模：將問題抽象為一個(gè)數(shù)學(xué)問題，并給出求解該數(shù)學(xué)問題的算法模型。算法策略設(shè)計(jì)算法的數(shù)據(jù)結(jié)構(gòu)和控制結(jié)構(gòu)設(shè)計(jì)：將數(shù)學(xué)模型轉(zhuǎn)換為可由計(jì)算機(jī)自動(dòng)計(jì)算的算法。算法的實(shí)現(xiàn)：用程序設(shè)計(jì)語言編寫算法實(shí)現(xiàn)的程序。算法的分析：分析算法的正確性和復(fù)雜性，判斷能行性！1.算法與算法類問題求解1.7你知道算法類問題求解的一般步驟嗎?算法類問題求解框架問題抽象及數(shù)學(xué)建模：將問題抽象為一個(gè)數(shù)學(xué)問題，并給出求解該數(shù)算法：程序與計(jì)算系統(tǒng)之靈魂2.數(shù)學(xué)建模與算法策略設(shè)計(jì)---算法思想數(shù)學(xué)建模與算法策略設(shè)計(jì)---算法思想----數(shù)學(xué)建模----有不同的算法求解策略算法：程序與計(jì)算系統(tǒng)之靈魂數(shù)學(xué)建模與算法策略設(shè)計(jì)---算法思算法類問題求解的第一步就是要數(shù)學(xué)建模。數(shù)學(xué)建模：是一種數(shù)學(xué)的思考方法，是運(yùn)用數(shù)學(xué)的語言和方法，通過抽象、簡(jiǎn)化建立對(duì)問題進(jìn)行精確描述和定義的數(shù)學(xué)模型。簡(jiǎn)單而言，數(shù)學(xué)建模是用數(shù)學(xué)語言描述實(shí)際現(xiàn)象的過程，即建立數(shù)學(xué)模型的過程。數(shù)學(xué)模型是對(duì)實(shí)際問題的一種數(shù)學(xué)表述，是關(guān)于部分現(xiàn)實(shí)世界為某種目的的一個(gè)抽象的簡(jiǎn)化的數(shù)學(xué)結(jié)構(gòu)。2.數(shù)學(xué)建模與算法策略設(shè)計(jì)---算法思想2.1為什么說數(shù)學(xué)建模對(duì)于算法很重要?將現(xiàn)實(shí)世界的問題抽象成數(shù)學(xué)模型，就可能發(fā)現(xiàn)問題的本質(zhì)及其能否求解，甚至找到求解該問題的方法和算法。算法類問題求解的第一步就是要數(shù)學(xué)建模。2.數(shù)學(xué)建模與算法策略哥尼斯堡七橋問題被抽象成一個(gè)“圖(Graph)”--由節(jié)點(diǎn)和邊所構(gòu)成的一種結(jié)構(gòu)，--依據(jù)“圖”，可發(fā)現(xiàn)該問題所蘊(yùn)含的許多性質(zhì)：“回路---從一個(gè)節(jié)點(diǎn)出發(fā)最后又回到該節(jié)點(diǎn)的一條路徑”“連通----兩個(gè)節(jié)點(diǎn)間有路徑相連接”“可達(dá)----從一個(gè)節(jié)點(diǎn)出發(fā)能夠到達(dá)另一個(gè)節(jié)點(diǎn)”“經(jīng)過圖中每邊一次且僅一次的回路”“經(jīng)過圖中每個(gè)節(jié)點(diǎn)一次且僅一次的回路”

什么情況下有解，什么情況下無解？注：《離散數(shù)學(xué)》或者《集合論與圖論》課程將介紹圖的有關(guān)性質(zhì)和方法。2.數(shù)學(xué)建模與算法策略設(shè)計(jì)---算法思想2.1為什么說數(shù)學(xué)建模對(duì)于算法很重要?如果能抽象成數(shù)學(xué)模型，則可將一個(gè)具體問題的求解，推廣為一類問題的求解！哥尼斯堡七橋問題被抽象成一個(gè)“圖(Graph)”2.數(shù)學(xué)建模TSP問題的數(shù)學(xué)模型2.數(shù)學(xué)建模與算法策略設(shè)計(jì)---算法思想2.2數(shù)學(xué)建模要做到怎樣?TSP問題的數(shù)學(xué)模型2.數(shù)學(xué)建模與算法策略設(shè)計(jì)---算法思想算法策略設(shè)計(jì)---算法思想當(dāng)數(shù)學(xué)建模完成后，就要設(shè)計(jì)算法的策略或者說問題求解的策略。TSP問題的基本求解策略遍歷：列出每一條可供選擇的路線，計(jì)算出每條路線的總里程，最后從中選出一條最短的路線。出現(xiàn)的問題是：組合爆炸路徑組合數(shù)目：(n-1)!20個(gè)城市，遍歷總數(shù)1.216×1017計(jì)算機(jī)以每秒檢索1000萬條路線的計(jì)算速度，需386年。所有路徑組合及其長(zhǎng)度城市之間的距離2.數(shù)學(xué)建模與算法策略設(shè)計(jì)---算法思想2.3算法思想或者算法策略對(duì)問題求解有什么影響?算法策略設(shè)計(jì)---算法思想當(dāng)數(shù)學(xué)建模完成后，就要設(shè)計(jì)算法的策TSP問題的難解性：隨著城市數(shù)量的上升，TSP問題的“遍歷”方法計(jì)算量劇增，計(jì)算資源將難以承受。2001年解決了德國(guó)15112個(gè)城市的TSP問題，使用了美國(guó)Rice大學(xué)和普林斯頓大學(xué)之間互連的、速度為500MHz

的CompaqEV6Alpha處理器組成的110臺(tái)計(jì)算機(jī)，所有計(jì)算機(jī)花費(fèi)的時(shí)間之和為22.6年。AnoptimalTSPtourthroughGermany’s15largestcities.Itistheshortestamong43589145600possibletoursvisitingeachcityexactlyonce.2.數(shù)學(xué)建模與算法策略設(shè)計(jì)---算法思想2.3算法思想或者算法策略對(duì)問題求解有什么影響?TSP問題的難解性：隨著城市數(shù)量的上升，TSP問題的“遍歷”TSP問題，有沒有其他求解算法呢？最優(yōu)解

vs.可行解不同的算法設(shè)計(jì)策略：遍歷、搜索算法分治算法貪心算法動(dòng)態(tài)規(guī)劃算法……可選取一種合適的策略來求解TSP問題可行解最優(yōu)解TSP問題的可行解與最優(yōu)解示意2.數(shù)學(xué)建模與算法策略設(shè)計(jì)---算法思想2.4有哪些算法策略?算法策略設(shè)計(jì)---算法思想TSP問題，有沒有其他求解算法呢？可行解最優(yōu)解TSP問題的可貪心算法是一種算法策略，或者說問題求解的策略?；舅枷搿敖癯芯平癯怼?。一定要做當(dāng)前情況下的最好選擇，否則將來可能會(huì)后悔，故名“貪心”。TSP問題的貪心算法求解思想從某一個(gè)城市開始，每次選擇一個(gè)城市，直到所有城市都被走完。每次在選擇下一個(gè)城市的時(shí)候，只考慮當(dāng)前情況，保證迄今為止經(jīng)過的路徑總距離最短。城市之間的距離2.數(shù)學(xué)建模與算法策略設(shè)計(jì)---算法思想2.5為什么稱為“貪心算法”?貪心算法貪心算法是一種算法策略，或者說問題求解的策略。基本思想“今朝算法：程序與計(jì)算系統(tǒng)之靈魂3.算法設(shè)計(jì)---算法思想的精確表達(dá)算法設(shè)計(jì)---算法思想的精確表達(dá)(I)----算法的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)----算法的控制結(jié)構(gòu)設(shè)計(jì)及其表達(dá)方法----TSP算法解讀算法：程序與計(jì)算系統(tǒng)之靈魂算法設(shè)計(jì)---3.算法設(shè)計(jì)---算法思想的精確表達(dá)3.1算法設(shè)計(jì)包括什么?算法設(shè)計(jì)算法的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)---問題或算法相關(guān)的數(shù)據(jù)之間的邏輯關(guān)系及存儲(chǔ)關(guān)系的設(shè)計(jì)算法的控制結(jié)構(gòu)設(shè)計(jì)---算法的計(jì)算規(guī)則或計(jì)算步驟設(shè)計(jì)如何構(gòu)造和表達(dá)處理的規(guī)則，以便能夠按規(guī)則逐步計(jì)算出結(jié)果?如何將數(shù)學(xué)模型中的數(shù)據(jù)轉(zhuǎn)為計(jì)算機(jī)可以存儲(chǔ)和處理的數(shù)據(jù)？3.算法設(shè)計(jì)---算法思想的精確表達(dá)算法設(shè)計(jì)算法的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gò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ù)的存儲(chǔ)結(jié)構(gòu)：在反映數(shù)據(jù)邏輯關(guān)系的原則下，數(shù)據(jù)在存儲(chǔ)器中的存儲(chǔ)方式。典型的有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。面向數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的基本運(yùn)算：(1)建立數(shù)據(jù)結(jié)構(gòu)；(2)清除數(shù)據(jù)結(jié)構(gòu)；(3)插入數(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ù)等。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其操作的總稱，它提供了問題求解/算法的數(shù)據(jù)操縱機(jī)制。3.算法設(shè)計(jì)---算法思想的精確表達(dá)3.2什么是數(shù)據(jù)結(jié)構(gòu)?數(shù)據(jù)結(jié)構(gòu)3.算法設(shè)計(jì)---算法思想的精確表達(dá)3.算法設(shè)計(jì)---算法思想的精確表達(dá)3.2什么是數(shù)據(jù)結(jié)構(gòu)?典型的數(shù)據(jù)結(jié)構(gòu)---“樹”示例存儲(chǔ)結(jié)構(gòu)中,用一個(gè)指針表達(dá)數(shù)據(jù)之間的邏輯關(guān)系150120160數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)503070100數(shù)據(jù)元素對(duì)應(yīng)數(shù)據(jù)元素的指針—指向該元素的父元素?cái)?shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)3.算法設(shè)計(jì)---算法思想的精確表達(dá)典型的數(shù)據(jù)結(jié)構(gòu)---150120160503070100數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)通過指針的變化,不改變數(shù)據(jù)的存儲(chǔ),但卻改變了數(shù)據(jù)之間的邏輯關(guān)系數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)3.算法設(shè)計(jì)---算法思想的精確表達(dá)3.2什么是數(shù)據(jù)結(jié)構(gòu)?150120160503070100數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)150120160503070100數(shù)據(jù)元素對(duì)應(yīng)數(shù)據(jù)元素的左指針—指向該元素的左側(cè)子結(jié)點(diǎn)對(duì)應(yīng)數(shù)據(jù)元素的右指針—指向該元素的右側(cè)子結(jié)點(diǎn)3.算法設(shè)計(jì)---算法思想的精確表達(dá)3.3同樣的邏輯結(jié)構(gòu)可以有不同的存儲(chǔ)結(jié)構(gòu)嗎?數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)典型的數(shù)據(jù)結(jié)構(gòu)---“樹”示例另一種存儲(chǔ)結(jié)構(gòu),用兩個(gè)指針表達(dá)數(shù)據(jù)之間的邏輯關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)不同，數(shù)據(jù)之間的操作方法也是不同的150120160503070100數(shù)據(jù)元素對(duì)應(yīng)數(shù)據(jù)元素的左1501201605030701003.算法設(shè)計(jì)---算法思想的精確表達(dá)3.3同樣的邏輯結(jié)構(gòu)可以有不同的存儲(chǔ)結(jié)構(gòu)嗎?數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)典型的數(shù)據(jù)結(jié)構(gòu)---“樹”示例另一種存儲(chǔ)結(jié)構(gòu),用兩個(gè)指針(左指針和右指針)表達(dá)數(shù)據(jù)之間的邏輯關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)150120160503070100數(shù)據(jù)的邏輯結(jié)構(gòu)110Null動(dòng)手練習(xí)一下1501201605030701003.算法設(shè)計(jì)---算法向量或列表或數(shù)組。矩陣或表向量實(shí)例n=4;Sum=0; ForJ=0tonStep1

{

Sum=Sum+mark[J]; }

NextJ

Avg=Sum/n;

多元素變量及其程序處理(前講介紹的)3.算法設(shè)計(jì)---算法思想的精確表達(dá)3.4多元素變量結(jié)構(gòu)是怎樣的?112522254539844212801003483751612341234行列M[2,3]表實(shí)例Sum=0; ForI=1to4Step1{ForJ=1to4Step1{Sum=Sum+M[I][J];}NextJ

}NextI

Avg=Sum/16;向量或列表或數(shù)組。向量實(shí)例n=4;多元素?cái)?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，用D[i][j]或D[i,j]來確定欲處理的每一個(gè)元素訪問路徑/解:一維數(shù)組S，用S[j]來確定每一個(gè)元素1432{A->D->C->B->A}SS[1]S[2]S[3]S[4]DD[2][3]3.算法設(shè)計(jì)---算法思想的精確表達(dá)3.5一個(gè)問題中應(yīng)該設(shè)計(jì)哪些數(shù)據(jù)結(jié)構(gòu)?TSP問題的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)就是針對(duì)選定的算法策略，設(shè)計(jì)其相應(yīng)的數(shù)據(jù)結(jié)構(gòu)及其算法：程序與計(jì)算系統(tǒng)之靈魂3.算法設(shè)計(jì)---算法思想的精確表達(dá)算法設(shè)計(jì)---算法思想的精確表達(dá)(II)----算法的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)----算法的控制結(jié)構(gòu)設(shè)計(jì)及其表達(dá)方法----TSP算法解讀算法：程序與計(jì)算系統(tǒng)之靈魂算法設(shè)計(jì)---順序結(jié)構(gòu)：“執(zhí)行A，然后執(zhí)行B”，是按順序執(zhí)行一條條規(guī)則的一種結(jié)構(gòu)。分支結(jié)構(gòu)：“如果Q成立，那么執(zhí)行A，否則執(zhí)行B”，Q是某些邏輯條件，即按條件判斷結(jié)果決定執(zhí)行哪些規(guī)則的一種結(jié)構(gòu)。循環(huán)結(jié)構(gòu)：控制指令或規(guī)則的多次執(zhí)行的一種結(jié)構(gòu)---迭代(iteration)循環(huán)結(jié)構(gòu)又分為有界循環(huán)結(jié)構(gòu)和條件循環(huán)結(jié)構(gòu)。有界循環(huán)：“執(zhí)行A指令N次”，其中N是一個(gè)整數(shù)。條件循環(huán)：某些時(shí)候稱為無界循環(huán)，“重復(fù)執(zhí)行A直到條件Q成立”或“當(dāng)Q成立時(shí)反復(fù)執(zhí)行A”，其中Q是條件。算法與程序的基本控制結(jié)構(gòu)3.算法設(shè)計(jì)---算法思想的精確表達(dá)3.6怎樣表達(dá)算法的步驟呢?順序結(jié)構(gòu)：“執(zhí)行A，然后執(zhí)行B”，是按順序執(zhí)行一條條規(guī)則的一流程圖的基本表示符號(hào)

矩形框：表示一組順序執(zhí)行的規(guī)則或者程序語句。菱形框：表示條件判斷，并根據(jù)判斷結(jié)果執(zhí)行不同的分支。圓形框：表示算法或程序的開始或結(jié)束。箭頭線：表示算法或程序的走向。算法與程序構(gòu)造的表達(dá)方法：程序流程圖3.算法設(shè)計(jì)---算法思想的精確表達(dá)3.7怎樣繪制流程圖?流程圖的基本表示符號(hào)算法與程序構(gòu)造的表達(dá)方法：程序流程圖3三種控制結(jié)構(gòu)的流程圖表示方法示意開始第1條規(guī)則或語句第n條規(guī)則或語句結(jié)束順序結(jié)構(gòu)的流程圖開始條件成立否？是否條件成立時(shí)執(zhí)行的規(guī)則或語句結(jié)束條件不成立時(shí)執(zhí)行的規(guī)則或語句分支結(jié)構(gòu)的流程圖循環(huán)結(jié)構(gòu)的流程圖初始化部分開始循環(huán)控制條件成立？修改部分需循環(huán)執(zhí)行的規(guī)則或語句。即：循環(huán)體結(jié)束是否循環(huán)結(jié)束3.算法設(shè)計(jì)---算法思想的精確表達(dá)3.7怎樣繪制流程圖?算法與程序構(gòu)造的表達(dá)方法：程序流程圖三種控制結(jié)構(gòu)的流程圖表示方法示意開始第1條規(guī)則或語句第n條規(guī)循環(huán)結(jié)構(gòu)的兩種情況的流程圖表示方法示意初始化部分開始循環(huán)控制條件成立？修改部分需循環(huán)執(zhí)行的規(guī)則或語句結(jié)束是否循環(huán)結(jié)束有界循環(huán)結(jié)構(gòu)的流程圖(循環(huán)次數(shù)確定)初始化部分開始循環(huán)控制條件成立？修改部分需循環(huán)執(zhí)行的規(guī)則或語句結(jié)束否循環(huán)未結(jié)束是條件循環(huán)結(jié)構(gòu)的流程圖(循環(huán)次數(shù)不確定)3.算法設(shè)計(jì)---算法思想的精確表達(dá)3.7怎樣繪制流程圖?算法與程序構(gòu)造的表達(dá)方法：程序流程圖循環(huán)結(jié)構(gòu)的兩種情況的流程圖表示方法示意初始化部分開始循環(huán)控制算法思想及算法流程圖表示示例歐幾里德算法流程圖3.算法設(shè)計(jì)---算法思想的精確表達(dá)3.7怎樣繪制流程圖?算法與程序構(gòu)造的表達(dá)方法：程序流程圖算法思想及算法流程圖表示示例3.算法設(shè)計(jì)---算法思想的精步驟描述法，即用人們?nèi)粘Ｊ褂玫恼Z言和數(shù)學(xué)語言描述算法的步驟。

例如：sum=1+2+3+4+…+n求和問題的算法描述

Startofthealgorithm(算法開始)(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é)果。Endofthealgorithm(算法結(jié)束)

3.算法設(shè)計(jì)---算法思想的精確表達(dá)3.8自然語言表述算法有什么問題?算法與程序構(gòu)造的表達(dá)方法：步驟描述法自然語言表示的算法容易出現(xiàn)二義性、不確定性等問題步驟描述法，即用人們?nèi)粘Ｊ褂玫恼Z言和數(shù)學(xué)語言描述算法的步驟。算法：程序與計(jì)算系統(tǒng)之靈魂3.算法設(shè)計(jì)---算法思想的精確表達(dá)算法設(shè)計(jì)---算法思想的精確表達(dá)(III)----算法的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)----算法的控制結(jié)構(gòu)設(shè)計(jì)及其表達(dá)方法----TSP算法解讀算法：程序與計(jì)算系統(tǒng)之靈魂算法設(shè)計(jì)---求解TSP問題的遍歷算法遍歷所有的組合路徑；累加一條路徑的距離之和；判斷某條路徑的距離是不是比當(dāng)前最短路徑距離短；如果是，則用新路徑取代當(dāng)前最短路徑，并記錄其距離；直到所有路徑比較完畢；……當(dāng)前最短路徑設(shè)為空，當(dāng)前最短距離設(shè)為最大值開始所有路徑組合完畢否？結(jié)束否是組合一條新路徑并計(jì)算該路徑的距離比當(dāng)前最短距離小嗎？將該路徑記錄為當(dāng)前最短路徑，并用其距離值更新當(dāng)前最短距離輸出當(dāng)前最短路徑及當(dāng)前最短距離是否3.算法設(shè)計(jì)---算法思想的精確表達(dá)3.9算法的控制結(jié)構(gòu)如何設(shè)計(jì)?將思想/策略轉(zhuǎn)變?yōu)椤安襟E”求解TSP問題的遍歷算法當(dāng)前最短路徑設(shè)為空，當(dāng)前最短距離設(shè)為步驟描述法表示的求解TSP問題的貪心算法城市用數(shù)字編號(hào)來表示,1,2…,N任何兩個(gè)城市的距離記錄在數(shù)組D[i,j]中依次訪問過的城市編號(hào)被記錄在S[1],S[2],…,S[N}中,即第i次訪問的城市記錄在S[i]中。Step(1)：從第1個(gè)城市開始訪問起，將城市編號(hào)1賦值給S[1]。Step(6)：第I次訪問的城市為城市j，其距第I-1次訪問城市的距離最短。3.算法設(shè)計(jì)---算法思想的精確表達(dá)3.9算法的控制結(jié)構(gòu)如何設(shè)計(jì)?StartoftheAlgorithm(1)S[1]=1;(2)Sum=0;(3)初始化距離數(shù)組D[N,N];(4)I=2;(5)從所有未訪問過的城市中查找距離S[I-1]最近的城市j;(6)S[I]=j;(7)I=I+1;(8)Sum=Sum+Dtemp;(9)如果I<=N，轉(zhuǎn)步驟(5)，否則，轉(zhuǎn)步驟(10);(11)Sum=Sum+D[1,j]；(12)逐個(gè)輸出S[N]中的全部元素;(13)輸出Sum。EndoftheAlgorithm步驟描述法表示的求解TSP問題的貪心算法3.算法設(shè)計(jì)---步驟描述法表示的求解TSP問題的貪心算法(Cont.)前述第5步“從所有未訪問過的城市中查找距離S[I-1]最近的城市j”還是不夠明確，需要進(jìn)一步細(xì)化3.算法設(shè)計(jì)---算法思想的精確表達(dá)3.9算法的控制結(jié)構(gòu)如何設(shè)計(jì)?(5.1)K=2;(5.2)將Dtemp設(shè)為一個(gè)大數(shù)(比所有兩個(gè)城市之間的距離都大)(5.3)L=1；(5.4)如果S[L]==K，轉(zhuǎn)步驟5.8；//該城市已出現(xiàn)過，跳過(5.5)L=L+1；(5.6)如果L<I，轉(zhuǎn)5.4；(5.7)如果D[K,S[I-1]]<Dtemp;j=K;Dtemp＝D[K,S[I-1]]；(5.8)K=K+1;(5.9)如果K<=N，轉(zhuǎn)步驟5.3。步驟描述法表示的求解TSP問題的貪心算法(Cont.)3.數(shù)學(xué)建模與算法策略設(shè)計(jì)---算法思想徑大小不一的金盤子按照從大到小的順序依次套放將現(xiàn)實(shí)世界的問題抽象成數(shù)學(xué)模型，就可能發(fā)現(xiàn)問題的本質(zhì)及其能否求解，甚至找到求解該問題的方法和算法。如果R不是0，將N的值賦給M,R的值賦給N,返回Step1;否則,最大公約數(shù)是N,輸出N,算法結(jié)束。如果實(shí)例的最優(yōu)解已知（問題規(guī)模小或問題已被成功求解），利用統(tǒng)計(jì)方法對(duì)若干問題實(shí)例的算法結(jié)果與最優(yōu)解進(jìn)行對(duì)比分析，即可對(duì)其進(jìn)行效果評(píng)價(jià)；數(shù)學(xué)建模：是一種數(shù)學(xué)的思考方法，是運(yùn)用數(shù)學(xué)的語言和方法，通過抽象、簡(jiǎn)化建立對(duì)問題進(jìn)行精確描述和定義的數(shù)學(xué)模型。TSP問題的貪心算法求解思想條件不成立時(shí)執(zhí)行的規(guī)則或語句2什么是數(shù)據(jù)結(jié)構(gòu)?分支結(jié)構(gòu)：“如果Q成立，那么執(zhí)行A，否則執(zhí)行B”，Q是某些邏輯條件，即按條件判斷結(jié)果決定執(zhí)行哪些規(guī)則的一種結(jié)構(gòu)。S[1]S[2]S[3]S[4]算法設(shè)計(jì)---算法思想的精確表達(dá)TSP問題貪心算法程序?qū)嵗?12)逐個(gè)輸出S[N]中的全部元素;算法與程序構(gòu)造的表達(dá)方法：步驟描述法NextJ(5)計(jì)算i+1，并將結(jié)果賦給i;程序設(shè)計(jì)過程：一般經(jīng)過編輯源程序編譯鏈接執(zhí)行。流程圖表示的求解TSP問題的貪心算法3.算法設(shè)計(jì)---算法思想的精確表達(dá)3.9算法的控制結(jié)構(gòu)如何設(shè)計(jì)?數(shù)學(xué)建模與算法策略設(shè)計(jì)---算法思想流程圖表示的求解TSP問算法思想解讀計(jì)算學(xué)科的學(xué)生不僅能夠設(shè)計(jì)算法，而且會(huì)描述和表達(dá)算法，更要能讀懂算法。外層循環(huán)，I從2至N循環(huán)；I-1個(gè)城市已訪問過，正在找與第I-1個(gè)城市最近距離的城市；已訪問過的城市號(hào)存儲(chǔ)在S[]中。中層循環(huán),K從第2個(gè)城市至第N個(gè)城市循環(huán),判斷D[K,S[I-1]]是否是最小值，j記錄了最小距離的城市號(hào)K。內(nèi)層循環(huán)，L從1至I-1,循環(huán)判斷第K個(gè)城市是否是已訪問過的城市，如是則不參加最小距離的比較；3.算法設(shè)計(jì)---算法思想的精確表達(dá)3.10你能夠讀懂流程圖嗎?算法思想解讀外層循環(huán)，I從2至N循環(huán)；I-1個(gè)城市已訪問過，算法：程序與計(jì)算系統(tǒng)之靈魂4.算法實(shí)現(xiàn)---程序設(shè)計(jì)算法實(shí)現(xiàn)---程序設(shè)計(jì)算法：程序與計(jì)算系統(tǒng)之靈魂算法實(shí)現(xiàn)---程序設(shè)計(jì)一個(gè)盤子，盤子只能在三根柱子上來回移動(dòng)不能放數(shù)學(xué)建模與算法策略設(shè)計(jì)---算法思想算法設(shè)計(jì)---算法思想的精確表達(dá)列出每一條可供選擇的路線，計(jì)算出每條路線的總里程，最后從中選出一條最短的路線----算法的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)TSP問題貪心算法程序?qū)嵗齌SP問題貪心算法的效果評(píng)價(jià)：循環(huán)結(jié)構(gòu)的兩種情況的流程圖表示方法示意算法設(shè)計(jì)---算法思想的精確表達(dá)訪問路徑/解:一維數(shù)組S，用S[j]來確定每一個(gè)元素算法的實(shí)現(xiàn)程序是算法的一種機(jī)器相容(Compatible)的表示，是利用計(jì)算機(jī)程序設(shè)計(jì)語言對(duì)算法描述的結(jié)果，是可以在計(jì)算機(jī)上執(zhí)行的算法。計(jì)算機(jī)語言是書寫算法步驟地規(guī)范、標(biāo)準(zhǔn)、語法規(guī)則等，以便使人和計(jì)算機(jī)能夠理解用計(jì)算機(jī)語言編寫出的程序(注：更重要的是使計(jì)算機(jī)能夠理解)。4.算法實(shí)現(xiàn)---程序設(shè)計(jì)4.1算法實(shí)現(xiàn)要選定計(jì)算機(jī)語言，你知道嗎?一個(gè)盤子，盤子只能在三根柱子上來回移動(dòng)不能放算法的實(shí)現(xiàn)程序是程序設(shè)計(jì)過程：一般經(jīng)過編輯源程序

編譯

鏈接

執(zhí)行。所謂編輯源程序是利用程序編輯器，按照計(jì)算機(jī)語言的規(guī)范書寫程序的過程；所謂編譯是將編制好的源程序翻譯成機(jī)器可以執(zhí)行的機(jī)器代碼程序(又稱為目標(biāo)代碼)的過程。所謂鏈接是將目標(biāo)代碼與公用函數(shù)庫中的函數(shù)實(shí)現(xiàn)代碼集成起來形成最終可執(zhí)行程序的過程。所謂執(zhí)行就是程序的運(yùn)行過程。計(jì)算機(jī)語言程序設(shè)計(jì)環(huán)境通常由一套書寫程序的語法規(guī)則、一個(gè)編譯程序、一個(gè)鏈接程序和一組編譯好的公用函數(shù)庫構(gòu)成。有些計(jì)算機(jī)語言同時(shí)也提供了相應(yīng)的編程環(huán)境、調(diào)試環(huán)境及集成開發(fā)環(huán)境等。算法的實(shí)現(xiàn)4.算法實(shí)現(xiàn)---程序設(shè)計(jì)4.1算法實(shí)現(xiàn)要選定計(jì)算機(jī)語言，你知道嗎?程序設(shè)計(jì)過程：一般經(jīng)過編輯源程序編譯鏈接執(zhí)行。所謂編輯TSP問題貪心算法程序?qū)嵗惴ǖ膶?shí)現(xiàn)4.算法實(shí)現(xiàn)---程序設(shè)計(jì)4.2你能用某一種計(jì)算機(jī)語言書寫出TSP問題貪心算法的程序嗎?TSP問題貪心算法程序?qū)嵗惴ǖ膶?shí)現(xiàn)4.算法實(shí)現(xiàn)---程序算法：程序與計(jì)算系統(tǒng)之靈魂5.高級(jí)問題初探:算法分析與計(jì)算復(fù)雜性高級(jí)問題初探:算法分析與計(jì)算復(fù)雜性算法：程序與計(jì)算系統(tǒng)之靈魂高級(jí)問題初探:算法分析與計(jì)算復(fù)雜性算法的模擬與分析算法的正確性問題：?jiǎn)栴}求解的過程、方法——算法是正確的嗎？算法的輸出是問題的解嗎？20世紀(jì)60年代，美國(guó)一架發(fā)往金星的航天飛機(jī)由于控制程序出錯(cuò)而永久丟失在太空中算法的效果評(píng)價(jià)：算法的輸出是最優(yōu)解還是可行解？如果是可行解，與最優(yōu)解的偏差多大？?jī)煞N評(píng)價(jià)方法：證明方法：利用數(shù)學(xué)方法證明；仿真分析方法：產(chǎn)生或選取大量的、具有代表性的問題實(shí)例，利用該算法對(duì)這些問題實(shí)例進(jìn)行求解，并對(duì)算法產(chǎn)生的結(jié)果進(jìn)行統(tǒng)計(jì)分析。5.高級(jí)問題初探:算法分析與計(jì)算復(fù)雜性5.1算法是正確的嗎?算法是正確的嗎?算法獲得的解是最優(yōu)的嗎?算法分析與計(jì)算復(fù)雜性算法的模擬與分析5.高級(jí)問題初探:算法算法分析示例：TSP問題貪心算法的模擬與分析TSP問題貪心算法的正確性評(píng)價(jià)：直觀上只需檢查算法的輸出結(jié)果中，每個(gè)城市出現(xiàn)且僅出現(xiàn)一次，該結(jié)果即是TSP問題的可行解，說明算法正確地求解了這些問題實(shí)例TSP問題貪心算法的效果評(píng)價(jià)：如果實(shí)例的最優(yōu)解已知（問題規(guī)模小或問題已被成功求解），利用統(tǒng)計(jì)方法對(duì)若干問題實(shí)例的算法結(jié)果與最優(yōu)解進(jìn)行對(duì)比分析，即可對(duì)其進(jìn)行效果評(píng)價(jià)；對(duì)于較大規(guī)模的問題實(shí)例，其最優(yōu)解往往是未知的，因此，算法的效果評(píng)價(jià)只能借助于與前人算法結(jié)果的比較。5.高級(jí)問題初探:算法分析與計(jì)算復(fù)雜性5.1算法是正確的嗎?算法分析與計(jì)算復(fù)雜性算法分析示例：TSP問題貪心算法的模擬與分析5.高級(jí)問題初探另一個(gè)問題：算法是能夠執(zhí)行的嗎？算法的復(fù)雜性分析算法的效率：時(shí)間效率和空間效率時(shí)間復(fù)雜性:如果一個(gè)問題的規(guī)模是n，解這一問題的某一算法所需要的時(shí)間為T(n)，它是n的某一函數(shù)，T(n)稱為這一算法的“時(shí)間復(fù)雜性”?！按驩記法”：基本參數(shù)n——問題實(shí)例的規(guī)模把復(fù)雜性或運(yùn)行時(shí)間表達(dá)為n的函數(shù)。“O”表示量級(jí)(order)，允許使用“=”代替“≈”，如n2+n+1=Ο(n2)。算法的空間復(fù)雜度：算法在執(zhí)行過程中所占存儲(chǔ)空間的大小。5.高級(jí)問題初探:算法分析與計(jì)算復(fù)雜性5.2算法的計(jì)算