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