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

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

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

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

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

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

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

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

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

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