第8單元 第3課《算法應(yīng)用重效率》教案 【黔教版】《信息科技》五下VIP

第3課《算法應(yīng)用重效率》教學(xué)設(shè)計課題算法應(yīng)用重效率單元第八單元學(xué)科信息科技年級五年級下核心素養(yǎng)目標(biāo)信息意識：具備理解數(shù)據(jù)如何被拆分、傳遞和利用，以便更高效地完成任務(wù)的意識，明白數(shù)據(jù)集的分割可以使處理任務(wù)更具效率和可擴(kuò)展性。計算思維：明白分而治之的原理，形成在面對復(fù)雜問題時，將大問題拆解為易于處理的子問題，并且利用算法來高效地解決這些問題的思維。數(shù)字化學(xué)習(xí)與創(chuàng)新：能夠?qū)⒁粋€復(fù)雜的學(xué)習(xí)內(nèi)容劃分為多個小部分，每個部分可以獨(dú)立地解決保證學(xué)習(xí)效率的提高和創(chuàng)新思維的培養(yǎng)。信息社會責(zé)任：在進(jìn)行數(shù)據(jù)分割處理時應(yīng)確保不會泄露個人信息或帶來不公平的偏見。教學(xué)重點(diǎn)學(xué)會運(yùn)用分而治之的思維解決繁雜問題。教學(xué)難點(diǎn)能夠運(yùn)用所學(xué)知識內(nèi)容提高算法應(yīng)用的效率。教學(xué)過程教學(xué)環(huán)節(jié)教師活動學(xué)生活動設(shè)計意圖導(dǎo)入新課板書課題。1、活動背景媽媽購物結(jié)算時，收款員忘了給某個物品消磁，我用更快的方法找到了沒有消磁的物品。用算法高效解決問題，離不開我們的思考。2、新知導(dǎo)入觀看視頻學(xué)習(xí)新知引入，觀看教學(xué)視頻。用提問的方式引入課題，增強(qiáng)課堂互動性。將學(xué)生的注意吸引到課堂。講授新課新知講解：一、分解問題日常生活中，有時可以采用分而治之的思想解決問題。活動：找出沒有消磁的物品小智的媽媽在超市采購了24件物品，可是出門的時候發(fā)現(xiàn)收款員忘了給某個物品消磁(圖8-3-1)。1.比較下面兩種做法，你覺得哪種做法更好，為什么?(1)逐一將物品通過檢驗機(jī);(2)取一半物品過檢驗機(jī)，將發(fā)出警報的這堆物品繼續(xù)分一半過檢驗機(jī)，以此類推。逐一將物品通過檢驗機(jī)和取一半物品過檢驗機(jī)并將發(fā)出警報的物品繼續(xù)分一半過檢驗機(jī)這兩種做法相比較，通常第二種做法更好。原因在于：逐一檢驗需要檢驗每一個物品，當(dāng)物品數(shù)量較多時，檢驗的工作量和時間成本會顯著增加。而取一半物品過檢驗機(jī)，將發(fā)出警報的這堆物品繼續(xù)分一半過檢驗機(jī)，以此類推，這種方法類似于折半的思想，能夠快速縮小可能存在問題的物品范圍，減少檢驗的工作量和時間。2.與“用折半查找猜數(shù)”相比較，上面的做法(2)有哪些不同??操作對象不同：第二種方法的操作對象是實(shí)際的物品，目的是找出可能存在問題（發(fā)出警報）的物品；而折半查找猜數(shù)的操作對象是數(shù)字，目的是在一個給定的數(shù)字范圍內(nèi)找出目標(biāo)數(shù)字。?判斷依據(jù)不同：第二種方法是根據(jù)檢驗機(jī)發(fā)出的警報來判斷物品是否有問題；折半查找猜數(shù)是根據(jù)猜測的數(shù)字與目標(biāo)數(shù)字的大小關(guān)系（“高了”或“低了”）來縮小猜測范圍。與將物品逐一通過檢驗機(jī)相比，每次取一半物品通過檢驗機(jī)解決問題的效率更高。類似地，在現(xiàn)實(shí)生活中，我們可以將一個大規(guī)模的問題分解為若干個規(guī)模較小的相同子問題，各個子問題形式相同，解決的方法也一樣。拓展閱讀分治思想分治算法的基本思想是：將一個復(fù)雜的問題分為若干個子問題來進(jìn)行求解，然后綜合各個子問題得到復(fù)雜問題的最終答案;如果這些子問題仍難以解決，可以再把它們分為若干個更小的子問題，直至可以直接求出答案為止。二、分析已知條件對同一個問題分析的深度不同，設(shè)計出的算法效率會不同嗎?活動：優(yōu)化猜數(shù)算法小智媽媽讓小智猜自行車的價格，價格范圍在1000元以內(nèi)。在小智猜價格的過程中，媽媽會根據(jù)小智猜的價格進(jìn)行相應(yīng)的提示，“高了”或“低了”。小智打算繼續(xù)用折半查找，但是他猜的第一個數(shù)字卻是650。你知道這是為什么嗎?你覺得小智這樣修改猜數(shù)算法的優(yōu)勢是什么?答：小智原本打算用折半查找法，正常情況下在價格范圍1000元以內(nèi)，第一次猜測的數(shù)字應(yīng)該是500（1000的一半向下取整）。他猜650可能是因為他沒有嚴(yán)格按照折半查找的規(guī)則來，也有可能是他憑借自己的直覺或者對自行車價格有一定的預(yù)估，認(rèn)為價格可能在650元左右。如果小智堅持嚴(yán)格按照折半查找法，優(yōu)勢在于可以更高效地縮小價格范圍。每次猜測都能將可能的價格區(qū)間縮小一半，從而以最快的速度逼近正確答案。估算自行車的價格范圍后，合理調(diào)整猜數(shù)范圍，有助于減少猜測次數(shù)。活動：探析問題理解對算法效率的影響有若干只雞、兔同在一個籠子里，從上面數(shù)，有35個頭;從下面數(shù)有94只腳。請問：雞和兔各多少?1.嘗試?yán)斫馊鐖D8-3-2所示的三個程序，分析算法設(shè)計的緣由，并填寫表8-3-1。表8-3-1算法設(shè)計分析程序算法緣由為算法提供的已知條件算法所做的處理(a)通過設(shè)定變量來計算雞和兔的數(shù)量?？傤^數(shù)為35，總腳數(shù)為94設(shè)定變量總腳數(shù)為94，總頭數(shù)為35，然后通過變量運(yùn)算來求解雞和兔的數(shù)量。(b)通過設(shè)定變量來計算雞和兔的數(shù)量?？傤^數(shù)為35，總腳數(shù)為94設(shè)定變量總腳數(shù)為94，總頭數(shù)為35，然后通過變量運(yùn)算來求解雞和兔的數(shù)量。(c)通過循環(huán)和條件判斷來計算雞和兔的數(shù)量。總頭數(shù)為35，總腳數(shù)為94設(shè)定變量總頭數(shù)為35，總腳數(shù)為94，然后通過循環(huán)和條件判斷來求解雞和兔的數(shù)量。2.你認(rèn)為哪個算法效率更高?請分析其效率高的原因。認(rèn)為程序(a)和(b)的效率更高。原因如下：程序(a)和(b)：這兩個程序通過簡單的變量運(yùn)算來求解雞和兔的數(shù)量，算法簡單直接，計算量較小，效率較高。?程序(c)：該程序通過循環(huán)和條件判斷來求解，雖然也能得到正確結(jié)果，但循環(huán)和條件判斷的增加會導(dǎo)致計算量增大，效率相對較低。綜上所述，程序(a)和(b)的算法效率更高，因為它們采用了更直接和簡單的計算方法。拓展閱讀枚舉思想將所有可能的候選答案一一列舉，然后驗證該候選答案是否為正確的解。將所有候選答案驗證后，就可以找出正確的解(或無解)。在解決某些問題時，可能沒有辦法按一定的規(guī)律從眾多的候選答案中找出正確的解，就可以采用枚舉思想。當(dāng)問題規(guī)模很大時，采用人工方式很難處理，可以用計算機(jī)驗證每一個候選答案，從而求解問題，使用枚舉算法時，需要明確問題的答案范圍，避免無效搜索，從而提高算法的效率。解決問題時，分析問題的已知條件及內(nèi)在邏輯，建立前提條件與結(jié)果之間的關(guān)系，通過數(shù)學(xué)表達(dá)式的計算實(shí)現(xiàn)問題求解，有助于提高求解問題的效率。三、課堂練習(xí)完成教材19—21頁相關(guān)課堂練習(xí)題。四、拓展延伸1、優(yōu)化分而治之算法避免重復(fù)計算：如果在分解子問題的過程中，出現(xiàn)了重復(fù)計算的情況，可以通過記憶化（memoization）來緩存已經(jīng)計算過的結(jié)果，減少不必要的計算。例如，在合并排序（MergeSort）中，可以通過使用指針而不是重復(fù)排序來減少合并過程中的時間復(fù)雜度。合并過程優(yōu)化：有些分而治之問題的合并步驟可能存在重復(fù)計算，可以通過優(yōu)化合并策略來減少計算量。例如，合并兩個已排序的數(shù)組時，可以通過指針來遍歷兩個數(shù)組，而不是重新計算每一對元素的合并。平衡子問題的大?。悍侄沃惴ǖ男释ǔＲ蕾囉谧訂栴}的規(guī)模平衡。過大的子問題可能會導(dǎo)致合并過程繁重，而過小的子問題可能使得遞歸的深度增大。合理分割子問題的大小可以減少計算量和遞歸的深度，進(jìn)而提高效率。并行化計算：如果可以對子問題的計算和合并過程進(jìn)行并行化處理，尤其是在多核處理器上，將顯著提高整體效率。例如，MapReduce是一種典型的分而治之方法，通過并行處理多個子問題來提高效率。2、分而治之算法在實(shí)際中的應(yīng)用圖像處理：在圖像處理領(lǐng)域，分而治之算法常用于圖像分割、邊緣檢測等任務(wù)。例如，快速傅里葉變換（FFT）就使用了分而治之的方法，它將計算大規(guī)模傅里葉變換的問題拆解成多個小規(guī)模的傅里葉變換，極大提高了計算效率。計算幾何：計算幾何中的許多經(jīng)典問題都可以通過分而治之進(jìn)行解決。例如，最近點(diǎn)對問題（找出平面中最近的兩點(diǎn)）通常使用分而治之的策略，先將點(diǎn)集分成兩個子集，遞歸計算子集中的最近點(diǎn)對，再合并子集的解。排序與搜索：例如，歸并排序（MergeSort）和快速排序（QuickSort）都屬于分而治之算法，特別適用于大規(guī)模數(shù)據(jù)的排序。快速排序通過將數(shù)組分為小于和大于基準(zhǔn)元素的兩部分，然后遞歸排序這些部分，達(dá)到優(yōu)化排序的效果。3、動態(tài)規(guī)劃與分而治之的區(qū)別與聯(lián)系相同點(diǎn)：都是將大問題拆解成更小的子問題，遞歸地求解子問題，最終合并子問題的解得到原問題的解；都可以通過分解問題，減少計算復(fù)雜度，尤其在處理重疊子問題時，可以減少不必要的計算。不同點(diǎn)：子問題的重疊性：分而治之算法通常是將一個問題分解成不重疊的子問題，而動態(tài)規(guī)劃則通常是將問題分解成有重疊子問題。動態(tài)規(guī)劃通過存儲子問題的解（通常使用表格），避免重復(fù)計算，而分而治之算法則不一定需要存儲中間結(jié)果。子問題的合并方式：在分而治之中，子問題的解通常是通過遞歸調(diào)用合并的，而動態(tài)規(guī)劃通過逐步構(gòu)造最優(yōu)解的表格來避免遞歸，直接從小到大計算出最終解。算法結(jié)構(gòu)：分而治之是通過遞歸來求解子問題，而動態(tài)規(guī)劃則是通過迭代的方式來逐步解決子問題。動態(tài)規(guī)劃常常依賴于自底向上的構(gòu)建方式，而分而治之則是自頂向下的遞歸求解。五、小結(jié)與評價1、單元拓展解決同一個問題有不同的算法，不同算法的效率可能不同，我們應(yīng)該從效率出發(fā)選擇高效算法。你想挑戰(zhàn)下面的哪個任務(wù)?試試你的本領(lǐng)吧。任務(wù)一：我國古代數(shù)學(xué)家張丘建在《算經(jīng)》一書中曾提出過著名的“百錢買百雞”問題:雞翁一，值錢五;雞母一，值錢三;雞雛三，值錢一;百錢買百雞，則翁、母、雛各幾何?嘗試使用枚舉法得到答案并優(yōu)化算法。任務(wù)二：小慧的妹妹將聲母卡的順序打亂了。以小組為單位，探究將聲母卡排序的算法，幫助她重新排序，并比較不同算法效率的高低。任務(wù)三：利用“計時器”可以觀察算法運(yùn)行的時間。嘗試執(zhí)行“連加”程序，輸入不同的數(shù)據(jù)，觀察運(yùn)行過程以及結(jié)果。想一想，在“連加”程序里，所輸入的數(shù)值與“和的累加”算法步驟的執(zhí)行次數(shù)、運(yùn)行時間有什么關(guān)系?答：執(zhí)行次數(shù)關(guān)系：“和的累加”算法通常是一個簡單的循環(huán)累加過程。假設(shè)輸入的數(shù)據(jù)個數(shù)為n，在基本的累加算法中，循環(huán)的次數(shù)就等于n。也就是說，輸入數(shù)值的個數(shù)越多，“和的累加”算法中循環(huán)步驟的執(zhí)行次數(shù)就越多。?運(yùn)行時間關(guān)系：一般情況下，隨著輸入數(shù)值的增加，“和的累加”算法的運(yùn)行時間會相應(yīng)增加。因為更多的輸入意味著更多的計算步驟，計算機(jī)需要花費(fèi)更多的時間來完成這些操作。2、單元閱讀并行計算提高算法效率在使用計算機(jī)解決復(fù)雜計算問題時，通常會采用并行計算。它的基本思想是用多個處理器來協(xié)同求解同一問題，即將被求解的問題分解成若干個部分，各部分均由一個獨(dú)立的處理機(jī)來并行計算。并行計算系統(tǒng)既可以是專門設(shè)計的、含有多個處理器的超級計算機(jī)也可以是以某種方式互連的若干臺獨(dú)立計算機(jī)構(gòu)成的集群。并行計算是提高計算機(jī)系統(tǒng)計算速度和處理能力的一種有效手段。貴州省首個超算中心(貴安超算中心)，采用并行計算，具備每秒1.3億億次的超算能力。排序算法的重要性排序算法在計算機(jī)科學(xué)中有著非常重要的應(yīng)用，其主要原因在于它可以有效地對大量數(shù)據(jù)進(jìn)行整理，使得數(shù)據(jù)檢索、分析和處理更為高效。提高搜索效率:對數(shù)據(jù)進(jìn)行排序后，可以使用二分查找等高級搜索算法在數(shù)據(jù)中快速查找特定元素，大大提高了搜索效率。簡化數(shù)據(jù)處理過程:對數(shù)據(jù)進(jìn)行排序，可以簡化合并排序、快速排序等算法的處理過程，提高其性能。優(yōu)化數(shù)據(jù)傳輸效率:在網(wǎng)絡(luò)傳輸中，數(shù)據(jù)通常需要按照一定的順序進(jìn)行傳輸。對數(shù)據(jù)進(jìn)行排序，可以有效地減少數(shù)據(jù)傳輸量，提高數(shù)據(jù)傳輸效率增強(qiáng)數(shù)據(jù)安全性:在加密和解密數(shù)據(jù)的過程中，排序算法也扮演著重要的角色。例如，加密和解密算法通常需要將數(shù)據(jù)進(jìn)行排序，以便更好地處理數(shù)據(jù)。提高數(shù)據(jù)處理速度:在處理大量數(shù)據(jù)時，排序算法可以有效地提高數(shù)據(jù)處理速度。例如，在進(jìn)行機(jī)器學(xué)習(xí)和數(shù)據(jù)分析時，排序算法可以使得數(shù)據(jù)處理過程更加高效。3、單元評價本單元我們通過對猜數(shù)、消磁物品查驗、雞兔同籠等問題的不同算法進(jìn)行分析與比較，感受了解決問題時需要考慮算法的效率。在學(xué)習(xí)過程中，你有哪些收獲呢?表現(xiàn)得怎么樣?請就本單元學(xué)習(xí)作出評價!4、單元練習(xí)1.你認(rèn)同下面哪些說法?(1)解決同一問題有多種算法，應(yīng)該具有采用高效算法解決問題的意識。(2)算法中某些步驟的執(zhí)行次數(shù)與問題的規(guī)模有關(guān)，通過比較不同數(shù)據(jù)規(guī)模下算法步驟的執(zhí)行次數(shù)變化趨勢，可以比較算法的效率。(3)應(yīng)該選擇效率高的算法，而不必考慮已知問題中的已知條件。答：認(rèn)同（1）。解決同一問題確實(shí)有多種算法，例如在查找元素時，有順序查找、折半查找等算法。不同的算法在時間復(fù)雜度、空間復(fù)雜度等方面存在差異，采用高效算法可以更快速地解決問題，節(jié)省資源和時間，所以應(yīng)該具有采用高效算法解決問題的意識。2.說說你的發(fā)現(xiàn)與思考。對本年級所學(xué)課程內(nèi)容進(jìn)行回顧，選擇你感興趣的案例，思考是否有更高效的算法解決該案例，為什么?5、學(xué)習(xí)評價請從解決問題有多種算法、“數(shù)”出算法中某些步驟的執(zhí)行次數(shù)、探究問題規(guī)模對算法效率的影響、算法應(yīng)用需要重視效率及小組合作等方面，評價本單元的學(xué)習(xí)表現(xiàn)。答：“數(shù)”出算法中某些步驟的執(zhí)行次數(shù)。這有助于我們深入了解算法的運(yùn)行過程和性能。通過精確地統(tǒng)計某些關(guān)鍵步驟（如循環(huán)次數(shù)、比較次數(shù)、賦值次數(shù)等）的執(zhí)行次數(shù)，我們可以量化算法的工作量。例如在一個簡單的查找算法中，統(tǒng)計比較操作的次數(shù)，就能知道在不同數(shù)據(jù)規(guī)模下該算法需要多少次比較才能找到目標(biāo)元素。6、單元總結(jié)本單元我們通過理解算法邏輯、“數(shù)”出算法步驟執(zhí)行次數(shù)、分析問題規(guī)模對算法執(zhí)行步驟的影響，找到了比較高效的猜數(shù)算法，解決了小智想在猜數(shù)游戲中獲勝的需求。在學(xué)習(xí)過程中，我們懂得了解決同一問題有多種算法，明白了算法中某些步驟的執(zhí)行次數(shù)與問題的規(guī)模有關(guān)，能夠判斷解決同一問題的不同算法在效率上的高低。通過