大學(xué)計(jì)算機(jī)基礎(chǔ)-基于計(jì)算思維（Windows 10+Office 2016）（第2版） 教案-教學(xué)設(shè)計(jì) 第10章 算法思維與應(yīng)用

《信息技術(shù)——基于WPS+數(shù)據(jù)思維》教案第10章算法思維與應(yīng)用10.1算法初步《信息技術(shù)——office2016+計(jì)算思維》授課導(dǎo)航第10章算法思維與應(yīng)用10.1算法初步授課時(shí)間授課地點(diǎn)內(nèi)容摘要1.了解什么是算法。教學(xué)目標(biāo)知識(shí)目標(biāo)1.明晰該項(xiàng)目要求。技能目標(biāo)1.能明確項(xiàng)目要求，做好學(xué)習(xí)計(jì)劃。教學(xué)設(shè)備教學(xué)多媒體設(shè)備，計(jì)算機(jī)材料準(zhǔn)備教學(xué)課件、軟件；視頻教學(xué)資料、網(wǎng)絡(luò)教學(xué)資源。教法案例教學(xué)法、啟示法、直觀教學(xué)法、歸納總結(jié)法等。學(xué)法合作學(xué)習(xí)法、自主學(xué)習(xí)法等。教學(xué)重點(diǎn)1.了解算法的基本性質(zhì)。教學(xué)難點(diǎn)1.掌握算法設(shè)計(jì)的要求。備注

教學(xué)環(huán)節(jié)教學(xué)內(nèi)容與教師活動(dòng)學(xué)生活動(dòng)組織教學(xué)課前準(zhǔn)備好多媒體課件，上課時(shí)引導(dǎo)學(xué)生就坐，宣布課堂紀(jì)律。課前預(yù)習(xí)10.1.1什么是算法算法思想早在古代的許多數(shù)學(xué)著作中就有所體現(xiàn)，例如：①古希臘人亞歷山大所著《幾何原本》中描述了一個(gè)求兩個(gè)數(shù)的最大公約數(shù)的步驟，現(xiàn)在被稱作歐幾里德算法。②中國(guó)古代數(shù)學(xué)典籍《數(shù)術(shù)記遺》中記載了各種計(jì)數(shù)法：太一算、兩儀算、三才算、五行算、八卦算、九宮算、珠算等，這些方法中已經(jīng)體現(xiàn)了現(xiàn)代程序中的選擇設(shè)計(jì)思想、并行原則、搜索原則等。③中國(guó)古代劉徽所著《九章算術(shù)》中的“賈憲三角”“增乘開(kāi)方法”“秦九韶法”等都是數(shù)學(xué)中的經(jīng)典算法，開(kāi)創(chuàng)了中國(guó)傳統(tǒng)數(shù)學(xué)構(gòu)造性和機(jī)械化的算法模式。這些思想不僅對(duì)今天的數(shù)學(xué)問(wèn)題的解決有極大的啟發(fā)作用，也為算法學(xué)奠定了基礎(chǔ)，可以說(shuō)“算法”（Algorithm）源于“算術(shù)”（Algorism）。算法的概念是建立在20世紀(jì)30年代哥德?tīng)?、圖靈等數(shù)學(xué)家對(duì)于“算法可計(jì)算”概念嚴(yán)格的數(shù)學(xué)刻畫基礎(chǔ)上。算法是一系列解決問(wèn)題的清晰指令，也就是說(shuō)，對(duì)于符合一定規(guī)范的輸入，能夠在有限時(shí)間內(nèi)獲得所要求的輸出，如圖10-1所示。其中的“computer”就是能夠理解和執(zhí)行所給出算法指令的人或物，在當(dāng)今特指能夠高速自動(dòng)運(yùn)算的電子計(jì)算機(jī)。算法表現(xiàn)為解決問(wèn)題的步驟描述，可以使用語(yǔ)言文字或各種圖形來(lái)描述（稱作推理實(shí)現(xiàn)的算法），也可以直接使用計(jì)算機(jī)中的各種語(yǔ)言工具描述并執(zhí)行得到結(jié)果（稱作操作實(shí)現(xiàn)的算法）。算法可以看作是解決問(wèn)題的一類特殊方法——它雖然不是問(wèn)題的答案，但它是經(jīng)過(guò)準(zhǔn)確定義以獲得答案的過(guò)程。因此，無(wú)論是否涉及計(jì)算機(jī)，特定的算法設(shè)計(jì)技術(shù)都能看作問(wèn)題求解的有效策略。當(dāng)然，算法思想固有的精確性限制了它所能夠解決的問(wèn)題種類。比如說(shuō)，找不到一種使人長(zhǎng)生不老的算法，也找不到一種能夠準(zhǔn)確預(yù)判股票漲跌的算法。隨著計(jì)算機(jī)技術(shù)和信息技術(shù)的飛速發(fā)展，算法不僅是計(jì)算機(jī)科學(xué)的核心，也是一種一般性的智能工具，它已滲透到宇宙學(xué)、物理學(xué)、生物學(xué)乃至經(jīng)濟(jì)學(xué)和社會(huì)科學(xué)等諸多領(lǐng)域，必定有助于對(duì)其他學(xué)科的理解和應(yīng)用。自由討論自主問(wèn)答10.1.2算法的基本性質(zhì)通過(guò)前2章的問(wèn)題解決，不難理解算法的下面5個(gè)基本性質(zhì)：①具有零個(gè)輸入或多個(gè)輸入：輸入的目的是為算法提供原始數(shù)據(jù)或初始狀態(tài)，輸入可以來(lái)自鍵盤、文件或其他輸入設(shè)備。對(duì)于絕大多數(shù)算法，輸入都是必要的，但對(duì)于個(gè)別情況，輸入可以是零個(gè)。②有窮性：指算法必須保證在執(zhí)行有限次步驟后能自動(dòng)結(jié)束，且需要的時(shí)間是在可接受的范圍之內(nèi)，而不會(huì)出現(xiàn)無(wú)限循環(huán)。③確定性：算法的每一步驟都具有確定的含義，不會(huì)出現(xiàn)二義性，以保證在一定條件下只有一條執(zhí)行路徑，相同的輸入只能有唯一的輸出結(jié)果。④可行性：算法的每一步都必須是可行的，都能夠通過(guò)執(zhí)行有限次基本運(yùn)算完成，即算法可以轉(zhuǎn)換為程序上機(jī)運(yùn)行，并得到正確的結(jié)果。⑤至少有一個(gè)或多個(gè)輸出：輸出即算法的結(jié)果，沒(méi)有輸出的算法是沒(méi)有用的。輸出的形式通常通過(guò)屏幕顯示，也可以寫入到文件中，或通過(guò)其他輸出設(shè)備輸出。所以，在設(shè)計(jì)算法時(shí)，首先要確定需要哪些輸入（數(shù)量、類型、輸入設(shè)備），想得到什么輸出（數(shù)量、類型、輸出設(shè)備），然后通過(guò)若干步驟實(shí)現(xiàn)（順序、選擇、循環(huán)），避免陷入死循環(huán)。認(rèn)真聽(tīng)課做好筆記10.1.3算法設(shè)計(jì)的要求對(duì)于同一個(gè)問(wèn)題的解決可能存在多種算法，通過(guò)算法分析比較總會(huì)得到相對(duì)滿意的算法。一個(gè)好的算法應(yīng)該滿足以下4點(diǎn)要求：①正確性：對(duì)于任何合法的輸入都能夠得到正確的結(jié)果。②健壯性：對(duì)于不合法的輸入，也能做出相關(guān)處理，而不會(huì)產(chǎn)生中斷等異常情況或無(wú)法解釋的結(jié)果。③可讀性：好的算法要便于閱讀、理解和交流，才能使后續(xù)工作輕松（包括程序代碼的編寫、調(diào)試和修改）。而晦澀難懂的算法往往隱含錯(cuò)誤，不易被發(fā)現(xiàn)，也難于調(diào)試和修改。在算法中增加注釋語(yǔ)句，對(duì)重要變量和決策語(yǔ)句的用途進(jìn)行說(shuō)明是個(gè)很好的習(xí)慣。④時(shí)間效率高和存儲(chǔ)量需求低：時(shí)間效率指算法的執(zhí)行時(shí)間，執(zhí)行時(shí)間越短效率越高；存儲(chǔ)量需求指算法程序運(yùn)行時(shí)所占用的內(nèi)存或外部硬盤存儲(chǔ)空間。用最少的存儲(chǔ)空間，花最少的時(shí)間，求出同樣的結(jié)果就是好的算法。以上特征是評(píng)價(jià)一個(gè)算法好壞的準(zhǔn)則，也是設(shè)計(jì)算法時(shí)應(yīng)充分考慮的幾個(gè)方面。下面介紹一些計(jì)算機(jī)科學(xué)中最為淺顯和常用的基本算法，這些算法的思想容易理解，所需要的數(shù)據(jù)結(jié)構(gòu)也最為簡(jiǎn)單，體現(xiàn)了計(jì)算機(jī)科學(xué)發(fā)展中沉淀下來(lái)的智慧與一般性問(wèn)題處理的優(yōu)化原則，對(duì)于處理同類問(wèn)題或更復(fù)雜問(wèn)題都是值得學(xué)習(xí)和借鑒的。認(rèn)真總結(jié)本課程相關(guān)知識(shí)。作業(yè)布置認(rèn)真完成學(xué)生活動(dòng)評(píng)價(jià)設(shè)計(jì)1.學(xué)生平時(shí)成績(jī)?cè)u(píng)定表（40%）平時(shí)成績(jī)?cè)u(píng)定表序號(hào)考核內(nèi)容評(píng)價(jià)標(biāo)準(zhǔn)分值得分1出勤情況全勤20請(qǐng)假1次扣1分，曠課1次扣2分2學(xué)習(xí)態(tài)度學(xué)習(xí)態(tài)度端正，認(rèn)真好學(xué)，積極主動(dòng)20其他情況，視實(shí)際表現(xiàn)酌情減扣分3課堂表現(xiàn)課堂紀(jì)律好，認(rèn)真聽(tīng)講，積極思考、討論、回答問(wèn)題20其他情況，視實(shí)際表現(xiàn)酌情減扣分4作業(yè)情況全部按時(shí)完成作業(yè)，保質(zhì)保量20其他情況，視實(shí)際表現(xiàn)酌情減扣分5文明禮貌尊師愛(ài)友，文明禮貌，誠(chéng)實(shí)守信，助人為樂(lè)，品德良好20其他情況，視實(shí)際表現(xiàn)酌情減扣分合計(jì)滿分100分，權(quán)重0.2分：2.項(xiàng)目/任務(wù)成績(jī)（60%）項(xiàng)目成績(jī)占總成績(jī)的60%。項(xiàng)目成績(jī)主要以每個(gè)項(xiàng)目/任務(wù)學(xué)習(xí)結(jié)束后，以理論知識(shí)考試及實(shí)操技能考核為依據(jù)。項(xiàng)目成績(jī)?cè)u(píng)定表見(jiàn)下表：成績(jī)?cè)u(píng)定表序號(hào)評(píng)分標(biāo)準(zhǔn)分值評(píng)分1任務(wù)需求的明確和實(shí)現(xiàn)策略確定202掌握算法設(shè)計(jì)的要求603任務(wù)完成程度20備注合計(jì)：滿分100分，權(quán)重0.6教師簽名：教學(xué)反思

10.2蠻力算法《信息技術(shù)——office2016+計(jì)算思維》授課導(dǎo)航第10章算法思維與應(yīng)用10.2蠻力算法授課時(shí)間授課地點(diǎn)內(nèi)容摘要本任務(wù)需要實(shí)現(xiàn)成績(jī)計(jì)算的制作，包括知識(shí)點(diǎn)解析和任務(wù)實(shí)現(xiàn)，總結(jié)提高。包含以下內(nèi)容：1.問(wèn)題分析2.算法實(shí)現(xiàn)3.運(yùn)行結(jié)果4.問(wèn)題總結(jié)教學(xué)目標(biāo)知識(shí)目標(biāo)1.熟悉決該問(wèn)題的最直接的方法。2.明確任務(wù)的要求及實(shí)現(xiàn)方法。技能目標(biāo)能掌握：?jiǎn)栴}分析；算法實(shí)現(xiàn)；運(yùn)行結(jié)果；問(wèn)題總結(jié)。教學(xué)設(shè)備教學(xué)多媒體設(shè)備，計(jì)算機(jī)材料準(zhǔn)備教學(xué)課件、軟件；視頻教學(xué)資料、網(wǎng)絡(luò)教學(xué)資源。教法案例教學(xué)法、啟示法、直觀教學(xué)法、歸納總結(jié)法等。學(xué)法合作學(xué)習(xí)法、自主學(xué)習(xí)法等。教學(xué)重點(diǎn)1.進(jìn)行問(wèn)題總結(jié)。教學(xué)難點(diǎn)1.掌握算法實(shí)現(xiàn)。備注教學(xué)環(huán)節(jié)教學(xué)內(nèi)容與教師活動(dòng)學(xué)生活動(dòng)組織教學(xué)課前準(zhǔn)備好多媒體課件，上課時(shí)引導(dǎo)學(xué)生就坐，宣布課堂紀(jì)律。課前預(yù)習(xí)10.2.1簡(jiǎn)單蠻力法【問(wèn)題1】某國(guó)際型運(yùn)動(dòng)會(huì)開(kāi)幕式準(zhǔn)備策劃一個(gè)大型團(tuán)體操，人數(shù)在50~500之間，但根據(jù)隊(duì)形變化要求，每10人排成一行要余2人領(lǐng)操，每12人排成一行要余4人領(lǐng)操，每4人排成一行要不多不少，問(wèn)需要的人數(shù)可以有多少種方案。1．問(wèn)題分析解決該問(wèn)題的最直接的方法是：既然已知所有可能解的范圍為50~500，那么就從下限50開(kāi)始判斷其是否滿足所有要求（稱為約束條件），是即輸出，不是就不輸出，同理再逐一判斷51、52、53直至上限500是否滿足要求，即可求出所有的方案。2.算法實(shí)現(xiàn)①在所有可能解的范圍50~500中逐一判斷，明顯用循環(huán)結(jié)構(gòu)實(shí)現(xiàn)。設(shè)一個(gè)循環(huán)變量number初值為50，終值為500，且按步長(zhǎng)值為1遞增，據(jù)此首先構(gòu)建一層循環(huán)結(jié)構(gòu)如圖10-2（a）所示。②循環(huán)體內(nèi)判斷number是否滿足所有要求，滿足則輸出number的值，否則不輸出。同時(shí)滿足3個(gè)條件可用邏輯運(yùn)算符and連接，3個(gè)條件類似，都是判斷number除以某數(shù)的余數(shù)，可用求余運(yùn)算符mod，所以循環(huán)體內(nèi)的流程圖如圖10-2（b）所示。3．運(yùn)行結(jié)果團(tuán)體操方案的Raptor流程圖的運(yùn)行結(jié)果如圖10-3所示。4．問(wèn)題總結(jié)上述求解問(wèn)題的算法是直接根據(jù)問(wèn)題的描述，從可能的集合中一一枚舉各個(gè)元素，用給定的約束條件判定哪些是問(wèn)題的解，哪些不是問(wèn)題的解，這種最簡(jiǎn)單的“justdoit”的設(shè)計(jì)策略稱為蠻力法（bruteforce）。這里的“力”是指計(jì)算機(jī)的“計(jì)算能力”，而不是人的“智力”。自由討論自主問(wèn)答10.2.2復(fù)雜蠻力法【問(wèn)題2】劉老師帶了41名同學(xué)去公園劃船，共租了10條船。每條大船坐6人，每條小船坐4人，問(wèn)大船、小船各租幾條則剛好坐下所有人？1．問(wèn)題分析對(duì)于此問(wèn)題，我們可以馬上列出一個(gè)二元一次方程組：用消元法可以很快解出該方程組，但怎么讓計(jì)算機(jī)來(lái)解這個(gè)方程組呢？用上述的蠻力法試試。①確定窮舉對(duì)象，分別以小船和大船的條數(shù)為窮舉對(duì)象，分別設(shè)為small和big。②確定窮舉范圍，從第1個(gè)約束條件可知，small和big的范圍都是0~10。③確定約束條件，明顯就是方程組中的2個(gè)方程。④一一窮舉可能的解，應(yīng)該從（0，0）開(kāi)始，然后依次判斷（0，1）、（0，2）、（0，3）…（0，10），（1，0）、（1，1）…(10，10)是否同時(shí)滿足兩個(gè)約束條件，這樣窮舉11×11=121次即可得到問(wèn)題的解。2．算法實(shí)現(xiàn)①怎樣窮舉出上述可能的解呢？用循環(huán)結(jié)構(gòu)內(nèi)再嵌套循環(huán)結(jié)構(gòu)（即雙循環(huán)）來(lái)實(shí)現(xiàn)。此問(wèn)題中，用small作為外循環(huán)還是用big作為外循環(huán)，都不影響結(jié)果。假設(shè)用small作外循環(huán)，big作內(nèi)循環(huán)，當(dāng)small=0時(shí)，big分別從0取到10，判斷每種組合是否滿足兩個(gè)約束條件；然后再取small=1，big又從0取到10，再判斷；最后small=10時(shí)，big又從0取到10，再判斷，這樣就能窮舉所有可能的解。操作實(shí)現(xiàn)時(shí)，則應(yīng)先搭好完整的外層循環(huán)結(jié)構(gòu)（small從0到10），然后在其內(nèi)的循環(huán)體內(nèi)再搭建內(nèi)層循環(huán)（big從0到10）。②在內(nèi)層循環(huán)體內(nèi)（big層內(nèi)）再判斷是否同時(shí)滿足2個(gè)約束條件，是則輸出small和big的值，否則不輸出3．運(yùn)行結(jié)果租船問(wèn)題的raptor流程圖的運(yùn)行結(jié)果。4．算法優(yōu)化在蠻力算法中，窮舉對(duì)象和窮舉范圍的選擇非常重要，它直接影響著算法的時(shí)間復(fù)雜度。認(rèn)真聽(tīng)課做好筆記10.2.3算法總結(jié)通過(guò)上述2個(gè)問(wèn)題的解決，我們對(duì)蠻力算法做個(gè)總結(jié)：①蠻力法是利用計(jì)算機(jī)運(yùn)算速度快的特點(diǎn)，對(duì)問(wèn)題的所有可能情況一個(gè)不漏地檢驗(yàn)，從中找出符合要求的答案，所以算法的正確性比較容易證明，但其是通過(guò)犧牲時(shí)間來(lái)?yè)Q取答案的全面性。②理論上，蠻力法可以解決可計(jì)算領(lǐng)域的各種問(wèn)題。例如前面2章中求一組數(shù)中的最大數(shù)、計(jì)算n個(gè)數(shù)的和等，實(shí)際也是蠻力算法的體現(xiàn)。③蠻力法經(jīng)常用來(lái)解決一些規(guī)模較小的問(wèn)題。如果問(wèn)題的規(guī)模不大，用蠻力法設(shè)計(jì)的算法的執(zhí)行時(shí)間是可以接受的，那么，可以不必花較高代價(jià)設(shè)計(jì)一個(gè)更高效的算法。④蠻力法可以作為某類問(wèn)題求解的時(shí)間性能的底線，來(lái)衡量同樣問(wèn)題的更高效算法。⑤對(duì)于蠻力算法，選擇適當(dāng)?shù)母F舉對(duì)象，縮小窮舉范圍，加強(qiáng)約束條件，是算法優(yōu)化的主要考慮方向。認(rèn)真總結(jié)本課程相關(guān)知識(shí)。作業(yè)布置認(rèn)真完成學(xué)生活動(dòng)評(píng)價(jià)設(shè)計(jì)1.學(xué)生平時(shí)成績(jī)?cè)u(píng)定表（40%）平時(shí)成績(jī)?cè)u(píng)定表序號(hào)考核內(nèi)容評(píng)價(jià)標(biāo)準(zhǔn)分值得分1出勤情況全勤20請(qǐng)假1次扣1分，曠課1次扣2分2學(xué)習(xí)態(tài)度學(xué)習(xí)態(tài)度端正，認(rèn)真好學(xué)，積極主動(dòng)20其他情況，視實(shí)際表現(xiàn)酌情減扣分3課堂表現(xiàn)課堂紀(jì)律好，認(rèn)真聽(tīng)講，積極思考、討論、回答問(wèn)題20其他情況，視實(shí)際表現(xiàn)酌情減扣分4作業(yè)情況全部按時(shí)完成作業(yè)，保質(zhì)保量20其他情況，視實(shí)際表現(xiàn)酌情減扣分5文明禮貌尊師愛(ài)友，文明禮貌，誠(chéng)實(shí)守信，助人為樂(lè)，品德良好20其他情況，視實(shí)際表現(xiàn)酌情減扣分合計(jì)滿分100分，權(quán)重0.2分：2.項(xiàng)目/任務(wù)成績(jī)（60%）項(xiàng)目成績(jī)占總成績(jī)的60%。項(xiàng)目成績(jī)主要以每個(gè)項(xiàng)目/任務(wù)學(xué)習(xí)結(jié)束后，以理論知識(shí)考試及實(shí)操技能考核為依據(jù)。項(xiàng)目成績(jī)?cè)u(píng)定表見(jiàn)下表：成績(jī)?cè)u(píng)定表序號(hào)評(píng)分標(biāo)準(zhǔn)分值評(píng)分1任務(wù)需求的明確和實(shí)現(xiàn)策略確定202能夠掌握問(wèn)題分析；算法實(shí)現(xiàn)；運(yùn)行結(jié)果；問(wèn)題總結(jié)。603任務(wù)完成程度20備注合計(jì)：滿分100分，權(quán)重0.6教師簽名：教學(xué)反思

10.3排序算法《信息技術(shù)——office2016+計(jì)算思維》授課導(dǎo)航第10章算法思維與應(yīng)用10.3排序算法授課時(shí)間授課地點(diǎn)內(nèi)容摘要本任務(wù)需要設(shè)計(jì)設(shè)計(jì)內(nèi)容幻燈片，包括知識(shí)點(diǎn)解析和任務(wù)實(shí)現(xiàn)，總結(jié)提高。包含以下內(nèi)容：1.冒泡排序2.選擇排序3.直接插入排序教學(xué)目標(biāo)知識(shí)目標(biāo)1.熟悉子程序input。2.明確任務(wù)的要求及實(shí)現(xiàn)方法。技能目標(biāo)能掌握：冒泡排序；選擇排序；直接插入排序。教學(xué)設(shè)備教學(xué)多媒體設(shè)備，計(jì)算機(jī)材料準(zhǔn)備教學(xué)課件、軟件；視頻教學(xué)資料、網(wǎng)絡(luò)教學(xué)資源。教法案例教學(xué)法、啟示法、直觀教學(xué)法、歸納總結(jié)法等。學(xué)法合作學(xué)習(xí)法、自主學(xué)習(xí)法等。教學(xué)重點(diǎn)1.了解算法實(shí)現(xiàn)。教學(xué)難點(diǎn)1.掌握設(shè)計(jì)輸出子程序outpu的方法。備注

教學(xué)環(huán)節(jié)教學(xué)內(nèi)容與教師活動(dòng)學(xué)生活動(dòng)組織教學(xué)課前準(zhǔn)備好多媒體課件，上課時(shí)引導(dǎo)學(xué)生就坐，宣布課堂紀(jì)律。課前預(yù)習(xí)知識(shí)點(diǎn)解析在日常生活、學(xué)習(xí)和工作中，排序無(wú)處不在，例如：①玩撲克牌時(shí)，為了便于快速出牌，會(huì)邊抓牌邊按一定規(guī)則排列整理好手中的牌。②軍訓(xùn)時(shí)，為了隊(duì)形好看，會(huì)按身高排列隊(duì)形。③班級(jí)名冊(cè)的管理會(huì)按學(xué)號(hào)排序。④評(píng)獎(jiǎng)學(xué)金會(huì)按學(xué)習(xí)成績(jī)排序。⑤圖書館中的圖書也會(huì)按分類索引排在適當(dāng)?shù)臅?、層次和位置，以便于查找。⑥大型運(yùn)動(dòng)會(huì)開(kāi)幕式，各國(guó)按國(guó)名的字母順序排列出場(chǎng)。⑦為了便于查找，手機(jī)中的通訊錄按姓名的字母順序排序。在實(shí)際應(yīng)用中，排序的目的大致可分為：①為比較或選拔而進(jìn)行排序（價(jià)格的排序、成績(jī)的排序）。②為提高查找效率進(jìn)行的排序（圖書館圖書的排序、各種字詞典中的條目排序）。所以，排序（sorting）在計(jì)算機(jī)科學(xué)中是研究得較多的問(wèn)題，也是一般算法研究的基礎(chǔ)性問(wèn)題?，F(xiàn)在已經(jīng)開(kāi)發(fā)出了幾十種不同的排序算法，但沒(méi)有一種算法在任何情況下都是最優(yōu)的，各有各的適用場(chǎng)合。下面介紹3種較簡(jiǎn)單的基本排序算法：冒泡排序、選擇排序和直接插入排序。10.3.1冒泡排序【問(wèn)題3】大學(xué)入學(xué)軍訓(xùn)時(shí)要求n人一列從低到高排列，現(xiàn)在已知n人的身高（無(wú)序），請(qǐng)按要求完成任務(wù)。1．問(wèn)題分析在現(xiàn)實(shí)中對(duì)于幾個(gè)人按高矮排列，總會(huì)比來(lái)比去，交換來(lái)交換去，花點(diǎn)時(shí)間。那么對(duì)于較多的甚至海量的復(fù)雜數(shù)據(jù)，怎么比和怎么交換就是關(guān)鍵，直接影響了排序算法的時(shí)間效率。冒泡排序（bubblesort）的過(guò)程類似水中冒氣泡的過(guò)程，將待排序的n個(gè)身高數(shù)據(jù)看作是垂直排列的重量不同的氣泡。根據(jù)重氣泡不能在輕氣泡上面的原則，從上往下掃描，比較相鄰數(shù)據(jù)，如果它們是逆序的話就交換它們的位置，重復(fù)多次后，最大數(shù)據(jù)就“沉到”了最后位置，稱為第1趟掃描冒泡。第2遍操作對(duì)剩余的數(shù)據(jù)進(jìn)行掃描冒泡，將第二大的數(shù)據(jù)沉下去。這樣一直做，經(jīng)過(guò)n-1趟以后，所有數(shù)據(jù)就排好序了。下面我們采用自底向上的問(wèn)題解決方法，即先解決各子問(wèn)題，再解決總問(wèn)題，從而實(shí)現(xiàn)【問(wèn)題3】的冒泡排序算法。2．算法實(shí)現(xiàn)（1）設(shè)計(jì)輸入子程序input（2）設(shè)計(jì)輸出子程序output（3）設(shè)計(jì)main子圖（4）設(shè)計(jì)冒泡子程序bubble（5）完善main子圖3．運(yùn)行結(jié)果圖10-17所示為該冒泡排序程序某次運(yùn)行的結(jié)果（10個(gè)元素）自由討論自主問(wèn)答10.3.2選擇排序1．問(wèn)題分析在上述冒泡排序算法的每趟冒泡中，相鄰元素只要逆序，就交換，那每趟冒泡可能交換多次。對(duì)此，我們可以進(jìn)行改進(jìn)：先比較找出最小元素，然后只和a[1]交換，即最小元素放到a[1]中，同理找出剩下元素的最小放到a[2]中，如此反復(fù)，就可得到有序的列表，該改進(jìn)的算法稱為選擇排序（selectionsort）。2．算法實(shí)現(xiàn)（1）設(shè)計(jì)選擇排序子程序select（2）其他子程序認(rèn)真聽(tīng)課做好筆記10.3.3直接插入排序1．問(wèn)題分析在實(shí)際生活中數(shù)據(jù)量往往是動(dòng)態(tài)變化的，例如班級(jí)花名冊(cè)已按學(xué)號(hào)排好了，但突然轉(zhuǎn)來(lái)了其他幾位學(xué)生（已有學(xué)號(hào)，入學(xué)后就不會(huì)變），此時(shí)怎樣將這幾位同學(xué)也按學(xué)號(hào)排到花名冊(cè)中呢?又如軍訓(xùn)已有某些人按高低順序排好了隊(duì)，后來(lái)又來(lái)了一些人，這些人怎樣插入到隊(duì)列中而不影響隊(duì)伍的高低順序呢？上述介紹的冒泡排序和選擇排序只能對(duì)已經(jīng)存在的不變的無(wú)序線性表進(jìn)行排序，對(duì)于臨時(shí)產(chǎn)生的無(wú)序數(shù)據(jù)要實(shí)現(xiàn)實(shí)時(shí)排序，就要采用直接插入排序（InsertSort）。2．算法實(shí)現(xiàn)（1）設(shè)計(jì)main子圖粗框圖（2）設(shè)計(jì)輸入和輸出子程序（input、output）（3）設(shè)計(jì)直接插入排序子程序insert粗框圖（4）設(shè)計(jì)找插入位置子程序location（5）設(shè)計(jì)插入子程序into（6）完善insert子程序和main子圖10.3.4算法總結(jié)①冒泡排序每趟冒泡是直接比較相鄰元素，只要逆序就交換。而選擇排序是對(duì)冒泡排序的改進(jìn)，每次掃描只交換一次。②冒泡排序和選擇排序也是蠻力法在排序問(wèn)題中的應(yīng)用。③冒泡排序和選擇排序只能對(duì)已經(jīng)存在的不變的無(wú)序線性表進(jìn)行排序，是較為常見(jiàn)的方法。④直接插入排序因?yàn)闊o(wú)序數(shù)據(jù)和有序數(shù)據(jù)分開(kāi)存儲(chǔ)，對(duì)于臨時(shí)產(chǎn)生的無(wú)序數(shù)據(jù)可以實(shí)現(xiàn)實(shí)時(shí)排序。作業(yè)布置認(rèn)真完成學(xué)生活動(dòng)評(píng)價(jià)設(shè)計(jì)1.學(xué)生平時(shí)成績(jī)?cè)u(píng)定表（40%）平時(shí)成績(jī)?cè)u(píng)定表序號(hào)考核內(nèi)容評(píng)價(jià)標(biāo)準(zhǔn)分值得分1出勤情況全勤20請(qǐng)假1次扣1分，曠課1次扣2分2學(xué)習(xí)態(tài)度學(xué)習(xí)態(tài)度端正，認(rèn)真好學(xué)，積極主動(dòng)20其他情況，視實(shí)際表現(xiàn)酌情減扣分3課堂表現(xiàn)課堂紀(jì)律好，認(rèn)真聽(tīng)講，積極思考、討論、回答問(wèn)題20其他情況，視實(shí)際表現(xiàn)酌情減扣分4作業(yè)情況全部按時(shí)完成作業(yè)，保質(zhì)保量20其他情況，視實(shí)際表現(xiàn)酌情減扣分5文明禮貌尊師愛(ài)友，文明禮貌，誠(chéng)實(shí)守信，助人為樂(lè)，品德良好20其他情況，視實(shí)際表現(xiàn)酌情減扣分合計(jì)滿分100分，權(quán)重0.2分：2.項(xiàng)目/任務(wù)成績(jī)（60%）項(xiàng)目成績(jī)占總成績(jī)的60%。項(xiàng)目成績(jī)主要以每個(gè)項(xiàng)目/任務(wù)學(xué)習(xí)結(jié)束后，以理論知識(shí)考試及實(shí)操技能考核為依據(jù)。項(xiàng)目成績(jī)?cè)u(píng)定表見(jiàn)下表：成績(jī)?cè)u(píng)定表序號(hào)評(píng)分標(biāo)準(zhǔn)分值評(píng)分1任務(wù)需求的明確和實(shí)現(xiàn)策略確定202能掌握：冒泡排序；選擇排序；直接插入排序。603任務(wù)完成程度20備注合計(jì)：滿分100分，權(quán)重0.6教師簽名：教學(xué)反思

10.4查找算法《信息技術(shù)——office2016+計(jì)算思維》授課導(dǎo)航第10章算法思維與應(yīng)用10.4查找算法授課時(shí)間授課地點(diǎn)內(nèi)容摘要本任務(wù)需要設(shè)計(jì)設(shè)計(jì)內(nèi)容幻燈片，包括知識(shí)點(diǎn)解析和任務(wù)實(shí)現(xiàn)，總結(jié)提高。包含以下內(nèi)容：1.順序查找2.二分查找教學(xué)目標(biāo)知識(shí)目標(biāo)1.熟悉子程序的操作。2.明確任務(wù)的要求及實(shí)現(xiàn)方法。技能目標(biāo)能掌握：順序查找；二分查找。教學(xué)設(shè)備教學(xué)多媒體設(shè)備，計(jì)算機(jī)材料準(zhǔn)備教學(xué)課件、軟件；視頻教學(xué)資料、網(wǎng)絡(luò)教學(xué)資源。教法案例教學(xué)法、啟示法、直觀教學(xué)法、歸納總結(jié)法等。學(xué)法合作學(xué)習(xí)法、自主學(xué)習(xí)法等。教學(xué)重點(diǎn)1.如何設(shè)計(jì)輸出子程序output。教學(xué)難點(diǎn)1.設(shè)計(jì)main子圖。備注

教學(xué)環(huán)節(jié)教學(xué)內(nèi)容與教師活動(dòng)學(xué)生活動(dòng)組織教學(xué)課前準(zhǔn)備好多媒體課件，上課時(shí)引導(dǎo)學(xué)生就坐，宣布課堂紀(jì)律。課前預(yù)習(xí)知識(shí)點(diǎn)解析查找也是我們?nèi)粘Ｉ?、學(xué)習(xí)和工作中經(jīng)常要做的工作，例如：①在手機(jī)中查找聯(lián)系人。②在圖書館中查找圖書。③在網(wǎng)絡(luò)中尋找有指定內(nèi)容的網(wǎng)頁(yè)。④用字典查找某個(gè)詞語(yǔ)的釋義。⑤查找最佳旅游路線。通常，查找（search）是從較大的數(shù)據(jù)集中找出或定位某個(gè)給定值（鍵值）的過(guò)程。根據(jù)數(shù)據(jù)集的不同特點(diǎn)，可以采用不同的查找算法來(lái)提高查找速度，實(shí)現(xiàn)高效搜索。10.4.1順序查找【問(wèn)題4】數(shù)據(jù)文件“data1.txt”中，有若干英語(yǔ)單詞（每行一個(gè)），現(xiàn)從鍵盤輸入一個(gè)單詞，請(qǐng)?jiān)谖募胁檎以撛~，若找到則給出其位置（第幾行），若沒(méi)找到，提示“nofound”。1．問(wèn)題分析由于數(shù)據(jù)集是存儲(chǔ)在文本文件中的，所以首先要按順序讀出這些數(shù)據(jù)存放到某數(shù)組中，然后在數(shù)組中查找。但這些數(shù)據(jù)是無(wú)序的，所以只能從數(shù)組第1個(gè)元素（或最后1個(gè)元素）開(kāi)始，按正序（或逆序）逐個(gè)掃描每個(gè)元素是否和鍵值相等，若相等則數(shù)組下標(biāo)即為其位置，若掃描結(jié)束都不相等，則表明沒(méi)有所查的數(shù)據(jù)（稱為查找失敗），所以稱這種查找算法為順序查找（sequentialsearch）。2．算法實(shí)現(xiàn)（1）設(shè)計(jì)輸入子程序input（2）設(shè)計(jì)輸出子程序output（3）設(shè)計(jì)main子圖（4）設(shè)計(jì)冒泡子程序bubble（5）完善main子圖自由討論自主問(wèn)答10.4.2二分查找【問(wèn)題5】某體校要招各類體育專長(zhǎng)人員，根據(jù)專業(yè)不同，對(duì)身高有不同的要求。現(xiàn)有若干人的身高數(shù)據(jù)按從低到高的順序存放在數(shù)據(jù)文件“data2.txt”中（每行一個(gè)），當(dāng)招生人員從鍵盤輸入一個(gè)身高值，請(qǐng)?jiān)谖募胁檎以撋砀咧?，若找到則給出其位置（第幾行），若沒(méi)找到，提示“nofound”。1．問(wèn)題分析對(duì)于此問(wèn)題當(dāng)然可以采用上述的順序查找算法實(shí)現(xiàn)，但和前一問(wèn)題不同的是數(shù)據(jù)集中的數(shù)據(jù)是有序的，已按從低到高的順序排好，那能不能利用這一條件提高查找效率呢？先看這樣一個(gè)游戲：猜某件商品的價(jià)格，已知商品的價(jià)格范圍（假設(shè)為1~100元），每猜一次主持人可以回答游戲者所猜價(jià)格比實(shí)際價(jià)格高了還是低了，若在規(guī)定次數(shù)內(nèi)就能猜對(duì)者，就可免費(fèi)獲得該商品。為了減少猜的次數(shù)，提高命中的效率，你會(huì)怎樣猜呢？通常會(huì)從1到100元的中間值50元開(kāi)始猜，如果高了，則進(jìn)一步從1到50元的中間值25再開(kāi)始猜；而如果低了，則從50到100元的中間值75開(kāi)始猜，這種猜價(jià)格的方法稱為折半方法。把折半方法應(yīng)用在查找中，就稱為折半查找法（又稱二分查找），它是在一個(gè)有序的元素列表中查找特定值的一種方法，該順序可以是升序，也可以是降序。二分查找法的具體過(guò)程如下：假設(shè)表中元素是按升序排列的，將表中間位置元素的值和要查找的值比較，如果二者相等，則查找成功；否則利用中間位置將所有數(shù)據(jù)分成前、后兩個(gè)部分，如果中間位置元素的值大于要查找的值，則進(jìn)一步查找前一部分的元素，否則進(jìn)一步查找后一部分的元素。重復(fù)以上過(guò)程，直到找到待查找的值，則查找成功，或直到表中不存在待找值為止，則查找不成功。2.算法實(shí)現(xiàn)（1）設(shè)計(jì)折半查找子程序halfsearch（2）其他子程序認(rèn)真聽(tīng)課做好筆記10.4.3算法總結(jié)①順序查找又稱為線性查找，是一種最簡(jiǎn)單的查找方法，數(shù)據(jù)集無(wú)須事先排序。但其平均查找次數(shù)較大，對(duì)于有n個(gè)數(shù)的序列，找到第1個(gè)數(shù)，只需查找1次即可，找到第2個(gè)數(shù)，要查找2次，找到第3個(gè)數(shù)，要查找3次……找到第n個(gè)數(shù)，要查找n次，則平均查找次數(shù)就是（1+2+3+…+n）/n=(1+n)/2。②二分查找要求待查的數(shù)據(jù)序列為有序的，因此適用于不經(jīng)常變動(dòng)而查找頻繁的有序數(shù)據(jù)列表。其優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好，適宜數(shù)據(jù)量很大的情況。③二分查找每執(zhí)行一次都可以將查找空間減少一半，是計(jì)算機(jī)科學(xué)中分治思想的完美體現(xiàn)。對(duì)于有n個(gè)數(shù)的序列，最多查找次數(shù)為log2n，平均查找次數(shù)約為log(n+1)-1作業(yè)布置認(rèn)真完成學(xué)生活動(dòng)評(píng)價(jià)設(shè)計(jì)1.學(xué)生平時(shí)成績(jī)?cè)u(píng)定表（40%）平時(shí)成績(jī)?cè)u(píng)定表序號(hào)考核內(nèi)容評(píng)價(jià)標(biāo)準(zhǔn)分值得分1出勤情況全勤20請(qǐng)假1次扣1分，曠課1次扣2分2學(xué)習(xí)態(tài)度學(xué)習(xí)態(tài)度端正，認(rèn)真好學(xué)，積極主動(dòng)20其他情況，視實(shí)際表現(xiàn)酌情減扣分3課堂表現(xiàn)課堂紀(jì)律好，認(rèn)真聽(tīng)講，積極思考、討論、回答問(wèn)題20其他情況，視實(shí)際表現(xiàn)酌情減扣分4作業(yè)情況全部按時(shí)完成作業(yè)，保質(zhì)保量20其他情況，視實(shí)際表現(xiàn)酌情減扣分5文明禮貌尊師愛(ài)友，文明禮貌，誠(chéng)實(shí)守信，助人為樂(lè)，品德良好20其他情況，視實(shí)際表現(xiàn)酌情減扣分合計(jì)滿分100分，權(quán)重0.2分：2.項(xiàng)目/任務(wù)成績(jī)（60%）項(xiàng)目成績(jī)占總成績(jī)的60%。項(xiàng)目成績(jī)主要以每個(gè)項(xiàng)目/任務(wù)學(xué)習(xí)結(jié)束后，以理論知識(shí)考試及實(shí)操技能考核為依據(jù)。項(xiàng)目成績(jī)?cè)u(píng)定表見(jiàn)下表：成績(jī)?cè)u(píng)定表序號(hào)評(píng)分標(biāo)準(zhǔn)分值評(píng)分1任務(wù)需求的明確和實(shí)現(xiàn)策略確定202能夠掌握順序查找；二分查找。603任務(wù)完成程度20備注合計(jì)：滿分100分，權(quán)重0.6教師簽名：教學(xué)反思

10.5遞歸算法《信息技術(shù)——office2016+計(jì)算思維》授課導(dǎo)航第10章算法思維與應(yīng)用10.5遞歸算法授課時(shí)間授課地點(diǎn)內(nèi)容摘要本任務(wù)需要實(shí)現(xiàn)課程成績(jī)統(tǒng)計(jì)的制作，包括知識(shí)點(diǎn)解析和任務(wù)實(shí)現(xiàn)，總結(jié)提高。包含以下內(nèi)容：1.設(shè)計(jì)遞歸模型子程序2.設(shè)計(jì)遞歸main子圖教學(xué)目標(biāo)知識(shí)目標(biāo)1.熟悉設(shè)計(jì)遞歸模型子程序的方法。2.明確任務(wù)的要求及實(shí)現(xiàn)方法。技能目標(biāo)能掌握：設(shè)計(jì)遞歸模型子程序；設(shè)計(jì)遞歸main子圖。教學(xué)設(shè)備教學(xué)多媒體設(shè)備，計(jì)算機(jī)材料準(zhǔn)備教學(xué)課件、軟件；視頻教學(xué)資料、網(wǎng)絡(luò)教學(xué)資源。教法案例教學(xué)法、啟示法、直觀教學(xué)法、歸納總結(jié)法等。學(xué)法合作學(xué)習(xí)法、自主學(xué)習(xí)法等。教學(xué)重點(diǎn)1.了解設(shè)計(jì)遞歸模型子程。教學(xué)難點(diǎn)1.設(shè)計(jì)遞歸main子圖。備注

教學(xué)環(huán)節(jié)教學(xué)內(nèi)容與教師活動(dòng)學(xué)生活動(dòng)組織教學(xué)課前準(zhǔn)備好多媒體課件，上課時(shí)引導(dǎo)學(xué)生就坐，宣布課堂紀(jì)律。課前預(yù)習(xí)10.5.1算法分析【問(wèn)題6】年齡問(wèn)題：5個(gè)人坐在一起論年齡，問(wèn)第5個(gè)人多少歲，他說(shuō)比第4個(gè)人大2歲。問(wèn)第4個(gè)人多少歲，他說(shuō)比第3個(gè)人大2歲。問(wèn)第3個(gè)人多少歲，他說(shuō)比第2個(gè)人大2歲。問(wèn)第2個(gè)多少歲，他說(shuō)比第1個(gè)人大2歲。問(wèn)第1個(gè)人多少歲，他說(shuō)10歲。請(qǐng)問(wèn)第5個(gè)人幾歲？【問(wèn)題7】求n的階乘：f(n)=1*2*3*4*…*n。1．問(wèn)題分析這兩個(gè)問(wèn)題很簡(jiǎn)單，對(duì)于問(wèn)題7在前面已經(jīng)用循環(huán)結(jié)構(gòu)實(shí)現(xiàn)了，對(duì)于問(wèn)題6同樣可以借助循環(huán)結(jié)構(gòu)實(shí)現(xiàn)。但在沒(méi)有學(xué)習(xí)循環(huán)結(jié)構(gòu)之前，剛遇到這兩個(gè)問(wèn)題時(shí)，會(huì)怎樣去思考呢？我們會(huì)發(fā)現(xiàn)這兩個(gè)問(wèn)題都有同樣的特點(diǎn)：對(duì)于問(wèn)題6，要求第5個(gè)人的年齡，就要先求出第4個(gè)人的年齡，而第4個(gè)人的年齡求法和第5個(gè)人的年齡求法類似，如此類推可得到一個(gè)遞推關(guān)系：age(n)=age(n-1)+2(n>1)對(duì)于問(wèn)題7，要求n的階乘，就要先求出n-