第二單元算法的效率【單元整體構想】一、單元內容簡介求解同一個問題，可能會有多種算法，但是解決同一個問題的多種算法，效率可能是不一樣的。不同的算法在考慮問題求解正確的基礎上，還需要分析問題求解的效率。本單元安排了“算法的效率”內容，在算法的描述、算法的執行等內容的基礎上，采用多種算法來解決同一個問題，體現算法執行的不同效率。本單元通過多種算法的執行及評估，讓學生意識到評價算法的標準除了正確性和有效性以外，執行效率也是一個需要關注的因素，幫助學生初步養成運用算法的思維習慣，形成設計與分析簡單算法的能力。二、單元設計的望遠鏡思維經過五年級的學習，學生已經能根據簡單問題的描述，進行抽象建模，采用恰當的方式描述算法，初步具備了信息處理的能力。經過六年級上第一單元的學習，學生已經知道在計算機中實現算法的一般步驟,通過問題健找、抽象與建模、設計算法、驗證與優化算法等過程，己經對算法與程序的關系有了具體的體驗。在此基礎上，本單元將“算法的描述”“算法的執行”和“算法的效率”三個部分有機貫穿于各個算法問題的討論，通過觀察并體驗采用不同算法解決同一個問題在時間效率上的差別。此外，本單元與此后要學習的第三單元“算法的影響”相關聯。通過分析信息社會中各種與算法有關的應用，讓學生感受到人們對這些應用有一個共同要求，即在用戶可以接受的時間內給出正確的結果。好的算法能在給定的資源條件下（例如存儲空間、網絡帶寬等），助力達成目標，或者在達成目標的前提下少用其他資源，因而具有價值。三、單元設計的放大鏡思維本單元的知識內容在設計上繼續圍繞“算法”這條核心邏輯主線，融合“數據”“信息處理”等多條邏輯主線螺旋上升。本單元圍繞“同一個問題可以采用多種算法來解決，而不同的算法可能具有不同的效率”和“解決問題的一般步驟包括抽象、分解、建模和制訂解決方案”等大概念，共設計5節課，安排了猜數字和“韓信點兵”等游戲，對同一個問題設計多種不同算法，如猜數字可分別采用順序查找和二分法查找算法解決，“韓信點兵”可分別采用枚舉、篩選、同余算法解決，并針對不同算法，討論算法評價的方法。通過本單元的學習，能幫助學生學會比較不同算法的效率，體驗算法效率的差別，樹立算法效率的意識。本單元各課內容如下表所示:課序課題簡介第8課算法的多樣性分析猜數字游戲問題、設計解決問題的多種算法、驗證解決問題的多種算法。

第9課算法的評價方法學習算法評價的方法、體驗算法評價。第10課“韓信點兵”枚舉法的實現抽象與建模、枚舉算法設計、篩選算法的程序實現。第11課“韓信點兵”篩選法的實現抽象與建模、篩選算法設計、篩選算法的程序實現。第12課“韓信點兵”同余法的實現抽象與建模、同余法設計、同余法的程序實現。【單元目標設計】素養目標在典型的信息科技應用場景中，嘗試采用不同方法解決同一個問題，熟悉一些常用經典算法的程序實現和執行過程；能針對不同的輸入數據的規模，分析解決問題的不同算法在時間效率上的高低。邏輯主線單元主要涉及的大概念.邏輯主線單元主要涉及的大概念.同一個問題可以采用多種算法來解決，而不同的算法可能具有不同算法的效率。.解決問題的一般步驟包括抽象、分解、建模和制訂解決方案。單元目標描述.通過分析生活中的具體問題解決實例，認識到解決同一個問題可能存在多種算法。.通過同一個問題的多種算法驗證，認識到不同的算法存在運行效率上的差異。.通過估算算法的時間復雜度，理解影響算法運行時間的因素，能根據簡單問題求解的需要設計合適的算法。【單元評價設計】本單元的評價可以基于真實的生活問題創設情境，圍繞“能采用多種算法解決問題，并對多種算法進行效率分析”展開。一、最終評價任務設計在進行大掃除時，要把甲、乙兩個班的學生分成若干個人數相同的小組，并且使每個小組都是同一個班的學生。每個小組最多有幾名學生？實踐：請用多種算法來解決問題。二、評價量規設計可根據學生的回答情況進行評價，如算法描述、算法實現、算法多樣性等方面。評價內容評分指標（評價內容評分指標（5分）得分利用算法解決問題具備按照抽象建模、設計算法、驗證算法的步驟解決問題的意識。算法的多樣性解決該問題可采用多種算法，如枚舉、輾轉相除法、更相減損術等。算法的實現能利用流程圖或程序實現算法。算法的效率具備算法效率意識，能根據問題解決需要選擇合適的算法解決問題【單元過程設計】一、單元問題設計問題一：猜數字游戲，你能用多種算法來解決嗎？設計意圖：猜數字游戲是前面幾節課探究過的問題，學生已經熟知該情境。通過類似的驅動性問題，一方面引發學生回顧前面學習過的內容，歸納問題解決的思維與方法；另一方面激發學生思考解決該問題的其他算法，引導學生感知解決同一個問題可能有多種算法。學生回答的引導方向：學生可回顧前幾節課中解決猜數字問題的思想與方法,就是模擬了整個猜數字游戲的過程，所猜數字可隨機輸入。因此，就所猜數字輸入的先后次序可引入一定的規則，如依次輸入、取中間數輸入等。問題二：你覺得怎樣的算法才是“好”的算法？設計意圖：對算法“好”和“差”的思考，一方面激發學生探究算法的本質，理解利用算法解決問題需要滿足正確、有效、高效等相關要求；另一方面引發學生關注算法評價要素，意識到算法效率也是一個需要關注的要素，以及算法效率可以從“時間”和“空間”兩個方面衡量。學生回答的引導方向：利用算法求解問題，首先要確保所采用的算法能正確解決問題；其次要能在一定時間內完成，且執行速度越快越好，存儲空間越少越好，即占用的資源越少越好，等等。二、單元學習策略本單元的學習要融入具體問題的解決過程。教材中通過猜數字游戲、“韓信點兵”等問題讓學生經歷抽象建模、設計算法、驗證算法、優化算法等環節，體驗算法的多樣性，并意識到算法的效率。在實際教學中，教師可以根據學生與學校的實際情況對問題進行適當簡化，鼓勵學生發現、分析問題，以解決問題為導向設計算法、學習新知、探索實踐等。課題 第8課算法的多樣性.通過設計猜數字的算法，理解順序查找和二分查找的思想，地川口廠樹立使用多種方法解決同一個問題的意識。教學目標.通過驗證猜數字游戲的算法，初步掌握順序查找和二分查找的程序設計方法，提高算法實現的能力。教學重點設計猜數字游戲的多種算法。教學難點實現及驗證猜數字游戲的多種算法。.網絡教室、PythOn編程環境。環境與素材2.童童家到學校的圖片。.猜數字游戲的二分查找程序。教學過程一、討論下圖中，童童從學校到家有哪幾條路線可走？二、建構現實中，解決一個問題的算法往往具有多樣性，即可用不同的算法來解決同一個問題。例如，解決問題猜數字游戲問題，除了前面學過的算法外，還可以采用順序查找和二分查找算法。1.問題分析猜數字游戲中，同學A輸入數字的過程其實是一個“查找”問題，即在1-100范圍內查找目標數da,可采用多種不同的策略來解決。例如：策略一：按順序依次查找。依次將L2,3, 99,100(或IO0,99,98,???,2,1)與da比較，直到找到為止。策略二：取中間數查找。1-100范圍內的數是依次增加的，依據該有序性可依次取中間數來查找。先取ITOO的中間數50與da比較，若da等于50,則查找成功；若da小于50,則取1-49的中間數25與da比較；若da大于50,則取51T00的中間數

75與da比較……如此反復，直到找到為止。在1-100范圍內查找目標數37的過程如下所示：目標數為37,初始范圍為I-Ioo1 2 ??? 49 519899100I中間數第一次比較：37<50,范圍調整為1-491 2 - 24 26???474849I中間數第二次比較：37>25,范圍調整為26-4926 27 ??? 36 38???474849I中間數第三次比較：37-37,查找成功【小知識】計算機中的“查找”指根據根據所給條件找出滿足條件的的對象，即在存儲存儲的一批數據內找出出一個特定的數據，或者確定在這批數據內是否存在這樣的數據。【試一試】采用“按順序依次查找”的策略，在1-100范圍內查找數37,一共需比較多少次？.解決問題的多種算法設計根據解決問題采用的策略，將其設計成算法。例如，上述猜數字游戲就可將“按順序依次查找”設計成順序查找算法，“取中間數查找”設計成二分查找算法。算法一：順序查找。假設目標數為37,并用變量da表示，取到的數用變算法二：二分查找。假設目標數為37,并用變量da表示，計算得到的中間值用變量cai表示，用變量cz和zz表示可取數的范圍，初始查找范圍為1-100,則CZ的初值為LZZ的的終值為100。對應的算法流程圖如下:CHD.解決問題的多種算法驗證上述問題兩種算法可以通過編寫程序或流程圖的的執行進行驗證。算法一的程序驗證：da=37cai=lwhilecai<101:ifcai==da:Print（"找到的數為："，cai）breakelse:cai=cai+lbreak語句的作用是終止所在的的循環。【想一想】上述程序中，若變量da的值為137,則程序運行結果是什么？若要顯示對應提示，則應如何修改程序？算法二的流程圖驗證：根據上述算法二的流程圖，可通過表格的形式列出變量cz、ZZ和Cai的值來驗證算法。循環輪次caiZZI■■通過3次循環，找到數37。【試一試】若變量da的值為137,請用表格的形式列出變量cz、ZZ和Cai的值。三、練習在上述算法一中，若變量Cai的取值依次為100,99,???,2,1,則相應的算法和程序如何修改？參考答窠：流程圖修改：[99]程序修改：da=37cai=100whilecai>0:ifcai==da:Print（"找找到到的數為："，cai）breakelse:cai=cai'l課后反思/評價標準課題 第9課算法的評價方法教學目標教學重點教學難點環境與素材教學目標教學重點教學難點環境與素材.通過給算法加計數變量等操作，比較語句的執行次數，深入理解算法的時間復雜度，形成算法效率的意識。初步掌握算法效率評價的方法。多種算法的效率比較。.網絡教室、PythOn編程環境。.多種算法的效率比較。教學過程一、討論解決某個問題可能會有多種不同的算法，如何評價算法的“好”與“差”呢？算法具有多樣性，但如何知道我所設計的算法好不好呢？對算法的評價是有一定標準的。二、建構針對某個問題，可以設計多個算法來解決，但不同算法的效率是有差異的。算法有“好”與“差”之分，在一定條件下，當然要選擇“好”的算法。.算法評價的方法“好”的算法，除了符合“正確性、有效性”等標準外，還需要有較高的算法運行效率，即算法運行所消耗的時間較短。一般情況下，算法運行需要的時間與待求問題的規模有關，如通過循環的方式求100個人的總分與求1000個人的總分，循環體執行的次數是不一樣的,執行時間顯然有差別。估算該算法的運行時間，可以在問題規模相同的情況下,將算法中循環語句的執行次數作為度量標準。例如，用順序查找算法在1-100內查找數37的程序如下：da=37cai=lwhiIecai<101:ifcai==da:Print（"找到的數為："，cai）breakelse:cai=cai+l上述程序在執行時，變量cai的數值決定了循環語句while會執行的次數，當變量Cai的值變為37時，WhiIe語句總的執行次數為37。【試一試】修改上述程序，增加一個變量Ci來統計While語句的執行次數，并顯示數值。.算法評價體驗解決同一個問題的不同算法，在執行時的運行時間是有一定差異的。同樣是在ITOO范圍內查找目標數37,利用二分查找算法時，中間值依次取50、25、37,也就是說，循環只需執行3次，與順序查找算法相比，循環少執行34次，顯然運行時間更短。【想一想】在ITOOO范圍內查找目標數37,利用二分查找算法，循環執行的次數是多少？三、練習在IToO范圍內，分別采用順序查找和二分查找算法查找目標數1、50和100,估算循環的執行次數。目標數查找算法循環執行次數1順序二分50順序二分順序100二分參考答案:目標數查找算法循環執行次數1順序1二分650順序50二分1順序100100二分7課后反思/評價標準課題 第10課“韓信點兵”枚舉法的實現教學目標.理解枚舉算法的思想，掌握枚舉算法解決問題的一般過程。.通過使用枚舉算法解決“韓信點兵”問題，掌握枚舉算法的程序實現。教學重點掌握枚舉算法解決問題的一般過程。教學難點掌握枚舉算法的程序實現。環境與素材.網絡教室、PythOn編程環境。.“韓信點兵”相關圖片、視頻等素材。教學過程一、探索你知道“韓信點兵”的故事嗎？韓信是怎么快速算出士兵的總人數的？韓信帶領一隊士兵，3個3個數，余2個；5個5個數，余3個；7個7個數，余2個。一共有多少人呢？人數可能是23,128,233,338,443,548,653,758 二、建構“韓信點兵”故事是一個有超的猜數游戲。其求解的算法有多種，如枚舉法。.問題描述相傳有一次，韓信帶領1500名士兵去打仗。戰后，死傷四五百人。剩下的士兵中，他命令士兵3人一排，結果多出2人；接著命令土兵5人一排，結果多出3人；又命令士兵7人一排，結果又多出2人。韓信馬上算出人數：我軍還有1073名勇士!假如由你來“點兵”，你將采用何種算法？.抽象與建模韓信點兵的過程可表示為數的除法運算。÷3=Δ 2÷5=O 3 f□=?□÷7=O……2“口”指剩下的士兵總數，用變量X來表示。根據“死傷四五百人”可知，變量X的范圍為1000-1100,且同時滿足“x除以3余數為2、X除以5余數為3、X除以7余數為2”這三個條件。可建立如下模型：枚舉X在100OTlOO范圍內的每一個值，判斷條件“x除以3余數為2、X除以5余數為3、X除以7余數為2”是否同時滿足，滿足條件的X就是要求的解。即：當x=1000時，條件"x除以3余數為2、X除以5余數為3、X除以7余數為2”是否同時滿足？當X=100l時，條件"x除以3余數為2、X除以5余數為3、X除以7余數為2”是否同時滿足？當X=IlOO時，條件"x除以3余數為2、X除以5余數為3、X除以7余數為2”是否同時滿足？.算法設計根據上述抽象與建模,解決“韓信點兵”問題可采用枚舉法。X依次取100O-IlOO范圍內的值，采用循環結構；判斷條件“x除以3余數為2、X除以5余數為3、X除以7余數為2”是否同時滿足，可以采用分支結構。檢母靠法農林Bl.算法的程序實現在Python中，求余數的運行符為“％”，即表達式x%y的功能是“用x除以y,取余數”，如“5%2”的結果就是1。因此，條件“x除以3余2”就可以表示為：x%3==2o要判斷多個條件是否同時滿足，需要用“and”邏輯運行符，條件“x除以3余數為2、X除以5余數為3、X除以7余數為2”就可表示為：x%3==2andx%5==3andx%7==2。上述算法用Python語言編寫的程序如下：x=1000whilex<1101:ifx%3==2andx%5=3andx%7==2:Print（"剩余的士兵數為：”，x）x=x+l三、練習假如“韓信點兵”的問題描述修改為：韓信帶領1500名士兵去打仗。戰后，死傷一二百人。剩下的士兵中，他命令士兵3人一排，結果多出1人；接著命令士兵5人一排，結果多出4人；又命令士兵7人一排，結果多出3人。問：剩下的士兵一共多少人？請你利用枚舉算法解決上述問題。參考答案：X=1300whilex<1401:ifx%3==landx%5==4andx%7==3:Print（"剩余的士兵數為：”，x）breakx==x+l課后反思/評價標準課題 第11課“韓信點兵”篩選法的實現教學目標.理解篩選法的思想，掌握用篩選法解決問題的一般過程。.通過使用篩選法解決“韓信點兵”問題，掌握篩選法的程序實現，進一步體會算法的多樣性。教學重點掌握用篩選法解決問題的一般過程。教學難點掌握篩選法的程序實現。環境與素材.網絡教室、PythOn編程環境。.“韓信點兵”相關圖片、視頻等素材。教學過程一、探索完成下表，你能得出符合條件的最小被除數是多少嗎？除數余數被除數的可能值325、8、11、14、17、20、23、26 5372二、建構“韓信點兵”問題還可以用篩選法來求解。.抽象與建模“韓信點兵”問題中，剩下的士兵總數用變量X來表示。變量X的范圍為1000-1100,且需同時滿足“X除以3余數為2、X除以5余數為3、X除以7余數為2”三個條件。由此，可建立如下模型：在100OTlOO這些數中，分別利用上述三個條件逐一進行篩選，最終剩下來的值就是所求解。即先根據“x除以3余數為2”條件，刪除1000-1100中不滿足該條件的數，篩選出滿足該條件的數；再根據“x除以5余數為3”條件，在上述篩選出的數中，刪除不滿足該條件的數，篩選出滿足該條件的數；最后根據“x除以7余數為2”條件，將篩選出來的數中不滿足該條件的數刪除，滿足該條件的數篩選出來。篩選過程示意圖如下所示：第一次篩選：根據“x除以3余數為2”條件IoOol1001∣10Q2j；104WK)?ajlθ?4∣ 10沖07110沖073[卜09小間1明1100∣TOC\o"1-5"\h\z×××× ×× ×X第二次篩選：根據“X除以5余數為3”條件1000∣1001∣1002∣"∣1042∣1043∣1044∣'"∣1070∣10711072∣1073~∣10971096∣1099∣110C∣

××× ×X××× XXXX第三次篩選：根據“X除以7余數為2”條件10001∞1IOra∣1O42∣1O43∣1O44∣p07C107110721073 110971099109911OO∣×××XXX××× XXXX.算法設計根據上述的抽象與建模，用篩選法解決“韓信點兵”問題的算法如下：(1)用a存儲IoOoTU)O范圍內的數;(2)在a中刪除不滿足“x除以3余數為2”條件的數；(3)在a中刪除不滿足“x除以5余數為3”條件的數；(4)在a中刪除不滿足“x除以7余數為2”條件的數；(5)找出a中剩下的數。.算法的驗證利用Python語言編寫程序，對上述算法進行局部驗證。例如，顯示IooO-IIoo范圍內滿足“x除以3余數為2”條件的數，對應的程序及運行結果如下所示：程序運行結果x=1000100110041007101010131016whilex<1101:101910221025102810311034ifx%3==2:103710401043104610491052105510581061106410671070print(x,end="n)107310761079108210851088x=x+l109110941097HOO代碼λprint(x,end="“)”中的end"”表示Print()輸出后不換行而輸出空格。【想一想】在上述算法中，若對調步驟(2)和步驟(4),對算法效率有何影響？三、練習編程實現：在1000-1100范圍內將滿足“x除以7余數為2”條件的數顯示出來。參考答案：X=100Owhilex<l100:ifx%7==2:Print(X,end=”")x=x+l課后反思/評價標準

課題 第12課“韓信點兵”同余法的實現教學目標.了解同余法的思想，掌握用同余法解決問題的一般過程。.通過使用同余法解決“韓信點兵”問題，掌握同余法的程序實現，進一步體會算法的多樣性。教學重點掌握用同余法解決問題的一般過程。教學難點掌握同余法的程序實現。環境與素材.網絡教室、PythOn編程環境。.“韓信點兵”相關圖片、視頻等素材。教學過程一、探索完成下表，你發現了什么現象？能得出什么結論？被除數除數余數233235237128312851287233323352337二、建構“韓信點兵”問題除了通過枚舉、篩選的算法思想來解決外，還可以依據同余的算法思想來解決。《孫子算經》中曾記載著利用同余思想求解的方法，這種方法被稱為“中國剩余定理工【小知識】數學上，兩個整數除以同一個整數，若余數相同，則對于除數，這兩個整數相同。.抽象與建模在韓信點兵過程，剩下的士兵總數用變量X表示。變量X的范圍為1000-1100,且需同時滿足“x除以3余數為2、X除以5余數為3、X除以7余數為2”三個條件。由此，可建立如下模型：根據同余思想，可先找出同時滿足“x除以3余數為2、X除以5余數為3、X除以7余數為2”三個條件的任意一個數，如233,然后將該數加減3、5、7的最小公