第4章 問(wèn)題求解與計(jì)算思維

.,第4章問(wèn)題求解與計(jì)算思維,主講教師：鄭立垠,計(jì)算機(jī)與通信工程學(xué)院計(jì)算機(jī)應(yīng)用技術(shù)系,.,中國(guó)自古就有喝茶的歷史習(xí)俗，有同學(xué)知道泡茶的流程嗎？燒水溫具置茶沖泡奉茶賞茶續(xù)水,引入,.,有一個(gè)牧羊人帶著一只羊,一匹狼和一顆大白菜準(zhǔn)備過(guò)河,他找到一只很小的船,每次只能帶一樣?xùn)|西過(guò)去,可是如果讓狼與羊單獨(dú)在一起,狼會(huì)吃羊,讓羊與白菜單獨(dú)在一起,羊會(huì)吃白菜，牧羊人應(yīng)如何過(guò)河？,過(guò)河的方案:第一步：人和羊過(guò)河，人返回，留下羊；第二步：人和狼過(guò)河，人和羊返回，留下狼；第三步：人和菜過(guò)河，人返回，留下菜；第四步：人和羊過(guò)河。,人在解決問(wèn)題時(shí)，要先對(duì)問(wèn)題進(jìn)行分析思考，然后確定解決問(wèn)題的方法和步驟，這種解決問(wèn)題的方法和步驟就稱為算法。,引入,.,1、算法2、計(jì)算思維,本章內(nèi)容,.,算法的由來(lái),算法算法被譽(yù)為計(jì)算學(xué)科和計(jì)算機(jī)器的靈魂“算法”（Algorithm）一詞源于：公元825年，阿拉伯?dāng)?shù)學(xué)家阿科瓦里茨米（AlKhowarizmi）寫了著名的波斯教科書（PersianTextbook），書中概括了進(jìn)行四則算術(shù)運(yùn)算的法則。,.,算法的定義：一個(gè)有窮規(guī)則的集合，規(guī)則規(guī)定了一個(gè)解決某一特定類型問(wèn)題的運(yùn)算序列。定義了任務(wù)執(zhí)行/問(wèn)題求解的一系列步驟。算法的特征：輸入：有零個(gè)或多個(gè)的輸入。輸出：有一個(gè)或多個(gè)的輸出。有窮性：一個(gè)算法在執(zhí)行有窮步之后必須結(jié)束。確定性：算法的每一個(gè)步驟必須要確切地定義，不得有歧義性?？尚行裕核惴ㄔ瓌t上能夠精確地運(yùn)行。,算法的定義及特征,.,算法描述,自然語(yǔ)言容易引起歧義，造成誤解；對(duì)較復(fù)雜的問(wèn)題，難以表達(dá)準(zhǔn)確流程圖直觀形象，但計(jì)算機(jī)不能識(shí)別和執(zhí)行程序代碼用計(jì)算機(jī)能理解和執(zhí)行的程序設(shè)計(jì)語(yǔ)言把算法表示出來(lái)，然后由計(jì)算機(jī)按照預(yù)定的算法去解決問(wèn)題。,.,算法設(shè)計(jì)數(shù)學(xué)建模數(shù)據(jù)結(jié)構(gòu)控制流程算法策略遍歷搜索遞歸動(dòng)態(tài)規(guī)劃貪心.,算法設(shè)計(jì),.,算法的正確性：?jiǎn)栴}求解的過(guò)程、方法算法是正確的嗎？算法的輸出是問(wèn)題的解嗎？20世紀(jì)60年代，美國(guó)一架發(fā)往金星的航天飛機(jī)由于控制程序出錯(cuò)而永久丟失在太空中算法的效果評(píng)價(jià)：算法的輸出是最優(yōu)解還是可行解？如果是可行解，與最優(yōu)解的偏差多大？?jī)煞N方法：分析方法：利用數(shù)學(xué)方法證明仿真分析方法：產(chǎn)生或選取大量的、具有代表性的問(wèn)題實(shí)例，利用該算法對(duì)這些問(wèn)題實(shí)例進(jìn)行求解，并對(duì)算法產(chǎn)生的結(jié)果進(jìn)行統(tǒng)計(jì)分析,算法分析,.,算法的效率：時(shí)間效率和空間效率時(shí)間復(fù)雜性:如果一個(gè)問(wèn)題的規(guī)模是n，解這一問(wèn)題的某一算法所需要的時(shí)間為T(n)，它是n的某一函數(shù)，T(n)稱為這一算法的“時(shí)間復(fù)雜性”?！按驩記法”：基本參數(shù)n問(wèn)題實(shí)例的規(guī)模把復(fù)雜性或運(yùn)行時(shí)間表達(dá)為n的函數(shù)?！癘”表示量級(jí)(order)，允許使用“=”代替“”，如n2+n+1=(n2)算法的空間復(fù)雜度：算法在執(zhí)行過(guò)程中所占存儲(chǔ)空間的大小。,算法效率,.,算法的復(fù)雜性,當(dāng)算法的時(shí)間復(fù)雜度的表示函數(shù)是一個(gè)多項(xiàng)式，如O(n2)時(shí)，計(jì)算機(jī)對(duì)于大規(guī)模問(wèn)題可以處理算法的時(shí)間復(fù)雜度用一個(gè)指數(shù)函數(shù)表示，如O(2n)，當(dāng)n很大（如10000）時(shí)計(jì)算機(jī)是無(wú)法處理的，在計(jì)算復(fù)雜性中將這一類問(wèn)題稱為難解性問(wèn)題。,算法效率,當(dāng)n值增大時(shí)，各種時(shí)間復(fù)雜度存在下列關(guān)系：O(log2n)O(n)O(nlog2n)O(n2)C-B-A,示例,旅行商問(wèn)題,城市之間的距離,.,問(wèn)題求解中的過(guò)程控制,問(wèn)題求解過(guò)程中需要組織并控制操作、指令的過(guò)程和順序,TSP問(wèn)題求解的流程控制,求解TSP問(wèn)題需要控制指令、基本操作的邏輯過(guò)程/流程遍歷所有的組合路徑判斷某條路徑的距離是不是比另外一條短，并據(jù)此作出不同的處理累加一條路徑的距離之和,旅行商問(wèn)題,.,算法策略,可行解與最優(yōu)解遍歷能夠獲得最優(yōu)解，然而，由于組合爆炸，對(duì)于較大規(guī)模的某些問(wèn)題，無(wú)法在可接受的時(shí)間內(nèi)獲得最優(yōu)解退而求其次，在可接受的時(shí)間內(nèi)獲得足夠好的（可行）解,TSP問(wèn)題的可行解與最優(yōu)解,旅行商問(wèn)題,.,算法策略貪心,貪心算法“今朝有酒今朝醉”一定要做當(dāng)前情況下的最好選擇，否則將來(lái)可能會(huì)后悔，故名“貪心”,TSP問(wèn)題的貪心求解示例,每次在選擇下一個(gè)城市的時(shí)候，只考慮當(dāng)前情況，保證迄今為止經(jīng)過(guò)的路徑總距離最短,城市之間的距離,旅行商問(wèn)題,.,TSP問(wèn)題貪心算法的模擬與分析,TSP問(wèn)題貪心算法的正確性：直觀上只需檢查算法的輸出結(jié)果中，每個(gè)城市出現(xiàn)且僅出現(xiàn)一次，該結(jié)果即是TSP問(wèn)題的可行解，說(shuō)明算法正確的求解了這些問(wèn)題實(shí)例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é)果的比較。,旅行商問(wèn)題,.,TSP問(wèn)題算法的效率,TSP問(wèn)題遍歷算法：列出每一條可供選擇的路線，計(jì)算出每條路線的總里程，最后從中選出一條最短的路線組合爆炸：路徑組合數(shù)目為(n-1)!時(shí)間復(fù)雜度是O(n-1)!)計(jì)算機(jī)不能處理TSP問(wèn)題貪心算法：時(shí)間復(fù)雜度是O(n3)。計(jì)算機(jī)可以處理,旅行商問(wèn)題,.,問(wèn)題求解總結(jié),.,1.科學(xué)與思維的含義(1)科學(xué)達(dá)爾文曾給科學(xué)下過(guò)一個(gè)定義：“科學(xué)就是整理事實(shí)，從中發(fā)現(xiàn)規(guī)律，作出結(jié)論”?？茖W(xué)一般包含：自然科學(xué)、社會(huì)科學(xué)和思維科學(xué)。(2)思維思維是高級(jí)的心理活動(dòng)，是認(rèn)識(shí)的高級(jí)形式。思維是人腦對(duì)現(xiàn)實(shí)事物概括、加工、揭露本質(zhì)特征。人腦對(duì)信息的處理包括分析、抽象、綜合、概括等。2.人類文明進(jìn)步和科學(xué)發(fā)現(xiàn)的三大科學(xué)(1)理論科學(xué)、實(shí)驗(yàn)科學(xué)和計(jì)算科學(xué)作為科學(xué)發(fā)現(xiàn)三大支柱，正推動(dòng)著人類文明進(jìn)步和科技發(fā)展。(2)該說(shuō)法已被科學(xué)文獻(xiàn)廣泛引用，并在美國(guó)得到國(guó)會(huì)聽(tīng)證、聯(lián)邦和私人企業(yè)報(bào)告的承同。,計(jì)算思維,.,3.科學(xué)思維(1)一般而論，三種科學(xué)對(duì)應(yīng)著三種思維：理論科學(xué)理論思維：理論思維又叫推理思維，以推理和演繹為特征，以數(shù)學(xué)學(xué)科為代表。實(shí)驗(yàn)科學(xué)實(shí)驗(yàn)思維：實(shí)驗(yàn)思維又叫實(shí)證思維，以觀察和總結(jié)自然規(guī)律為特征，以物理學(xué)科為代表。計(jì)算科學(xué)計(jì)算思維：計(jì)算思維又叫構(gòu)造思維，以設(shè)計(jì)和構(gòu)造為特征，以計(jì)算機(jī)學(xué)科為代表。(2)科學(xué)思維的含義及重要性：一般指的是理性認(rèn)識(shí)及其過(guò)程，也即經(jīng)過(guò)感性階段獲得的大量材料，通過(guò)整理和改造，形成概念、判斷和推理，以反映事物的本質(zhì)和規(guī)律。國(guó)科發(fā)財(cái)2008197號(hào)文關(guān)于創(chuàng)新方法工作的若干意見(jiàn)認(rèn)為“科學(xué)思維不僅是一切科學(xué)研究和技術(shù)發(fā)展的起點(diǎn)，而且始終貫穿于科學(xué)研究和技術(shù)發(fā)展的全過(guò)程，是創(chuàng)新的靈魂”。,計(jì)算思維,.,計(jì)算思維,計(jì)算思維(ComputationalThinking，CT)是運(yùn)用計(jì)算的基礎(chǔ)概念(FundamentalConcept)去求解問(wèn)題、設(shè)計(jì)系統(tǒng)和理解人類行為的一種方法(Approach)。CT的本質(zhì)是抽象(Abstract)和自動(dòng)化(Automation)。它是如同所有人都具備“讀、寫、算”（簡(jiǎn)稱3R）能力一樣，都必須具備的思維能力?；靖拍睿杭s簡(jiǎn)、嵌入、轉(zhuǎn)化、仿真、遞歸、并行、多維分析、類型、抽象、分解、SoC，保護(hù)、冗余、容錯(cuò)、糾錯(cuò)、系統(tǒng)恢復(fù)、啟發(fā)式、規(guī)劃、學(xué)習(xí)、調(diào)度、折衷。,.,程序設(shè)計(jì)課程中問(wèn)題求解能力培養(yǎng),問(wèn)題表示(如何建立模型)問(wèn)題求解（如何設(shè)計(jì)算法）效率（如何有效地求解）,.,尋找兩個(gè)正整數(shù)的最大公約數(shù)的歐幾里德算法輸入：正整數(shù)M和正整數(shù)N輸出：M和N的最大公約數(shù)算法過(guò)程：Step1.將較大的數(shù)賦給M,較小的數(shù)賦給N;Step2.M除以N,記余數(shù)為RStep3.如果R不是0,將N的值賦給M,R的值賦給N,返回Step2;否則,最大公約數(shù)是N,輸出N,算法結(jié)束,歐幾里德算法：求解兩個(gè)數(shù)的最大公因子的算法（公元前300年）表述了最大公因子的求解過(guò)程表述了一個(gè)判定過(guò)程，即判定“m和n是互質(zhì)的”（即除1以外，m和n沒(méi)有公因子）命題的真假。,求最大公約數(shù),.,乒乓球挑選,有13個(gè)乒乓球，其中有一個(gè)是壞的，其質(zhì)量與其它球不同，請(qǐng)?jiān)O(shè)計(jì)算法將其挑出。,建模與設(shè)計(jì),.,解答1：步驟1：將13個(gè)球分成4,4,4,1四份，分別記為a，b，c，d組；步驟2：先比較a，b兩組的輕重，若a與b一樣重，取c中任意4個(gè)球與a或b比較，若都一樣重，則d組為次品，若不一樣重，則可知次品在c組取出的4個(gè)球中，并且可判斷次品是輕還是重；若a與b不一樣重，取c組與a或b進(jìn)行稱量對(duì)比，得出含有次品組為a組或者b組以及判斷出次品是輕還是重。步驟3：從步驟2中得到含有4個(gè)球的次品組，將這4個(gè)球平分成2組稱量，根據(jù)次品是輕或重得到含有次品組e，再將次品組e中2個(gè)球分別放置天平兩端，根據(jù)次品輕重判斷得到次品球。,乒乓球挑選,.,解答2：（1）將13個(gè)球分為三個(gè)部分，6，6,1，將6,6兩部分進(jìn)行稱量，若平衡，則1所代表物品為次品；否則（2）（2）取一組6，將其平分為兩組計(jì)為a，b；另一組6再平分為c,d；取a,b,c兩兩稱量，若都平衡則次品在d中，轉(zhuǎn)到（3）；若有一次不平衡，則次品在a,b,c之中，轉(zhuǎn)到（3）（3）將三個(gè)任取兩個(gè)稱量，若平衡，則次品為未稱量的物品；若不平衡，則轉(zhuǎn)到（4）（4）若不平衡再測(cè)一次即可得次品。,乒乓球挑選,.,解答3：將13個(gè)球記為1,2,3,4,5,5,6,7,8,9,10,11,12,13。16記為A，712號(hào)記為B；步驟1：將AB組球放在天平上，若天平平衡，則次品為13號(hào)球；若不平衡，則轉(zhuǎn)向步驟2；步驟2：取較輕的一組，不妨設(shè)為A,將A組重新分成兩組放在天平兩端，若平衡，則轉(zhuǎn)向步驟3，不平衡轉(zhuǎn)向步驟4；步驟3：將B組分成兩組記為a,b，放在天平兩端，（由步驟2值次品較重），取較重的一組，不妨設(shè)其為a，任取兩個(gè)球放在天平兩端，若天平平衡，則為a中的另一個(gè)球；若不平衡，則較重的為次品；步驟4：將A組分成兩組，取較重的一組（三個(gè)球），任取兩個(gè)放在天平兩端，若平衡，則為三個(gè)中的另一個(gè)，若不平衡，則為較重的的球；,乒乓球挑選,.,解答4：步驟1：從這堆產(chǎn)品中任意拿出2產(chǎn)品，放在天平兩端；步驟2：記下天平兩端是否相平；相平執(zhí)行步驟3；否則執(zhí)行步驟5；步驟3：從天平的右端拿下產(chǎn)品，再?gòu)氖Ｓ喈a(chǎn)品中任意拿出一個(gè)放在右端，記下是否相平；步驟4：若相平，重復(fù)步驟3，直到不平為止，則此時(shí)右端產(chǎn)品為劣質(zhì)；步驟5：拿下右端產(chǎn)品，再?gòu)氖Ｓ喈a(chǎn)品中任意拿出放在右端，若相平，則之前拿下的為劣質(zhì)；否則左端為劣質(zhì),乒乓球挑選,.,兩