第4章算法與數(shù)據(jù)結構4.2迭代法教學設計教學背景信息科技是現(xiàn)代科學技術領域的重要部分，主要研究以數(shù)字形式表達的信息及其應用中的科學原理、思維方法、處理過程和工程實現(xiàn)。當代高速發(fā)展的信息科技對全球經(jīng)濟、社會和文化發(fā)展起著越來越重要的作用。義務教育信息科技課程具有基礎性、實踐性和綜合性，為高中階段信息技術課程的學習奠定基礎。信息科技課程旨在培養(yǎng)科學精神和科技倫理，提升自主可控意識，培育社會主義核心價值觀，樹立總體國家安全觀，提升數(shù)字素養(yǎng)與技能。教材分析本節(jié)課的教學內容選自人教/地圖出版社選擇性必修1數(shù)據(jù)與數(shù)據(jù)結構第4章算法與數(shù)據(jù)結構4.2迭代法。學情分析此節(jié)課針對的對象是高二年級的學生。學生學習過信息技術基礎知識，對計算機、網(wǎng)絡、物聯(lián)網(wǎng)等技術有基本了解:已經(jīng)學習了Python語言的基本概念，并掌握了基本的結構和算法;對現(xiàn)代生活中的信息系統(tǒng)有所觀察和積累。本章通過“編寫對弈程序”項目，引領同學們開展自主選題，建議從確定主題、選擇數(shù)據(jù)結構、設計算法和編寫程序等幾個方面入手，完成小組項目，發(fā)布應用程序，詳細記錄研究過程并形成研究報告。教學目標1.體驗迭代法解決問題的過程，能解決實際問題，發(fā)展計算思維。2.通過體驗排序與查找過程，能對具體問題進行抽象，合理選擇數(shù)據(jù)結構，設計算法解決問題。教學重點與難點教學重點:體驗迭代法解決問題的過程，能解決實際問題，發(fā)展計算思維。教學難點:通過體驗排序與查找過程，能對具體問題進行抽象，合理選擇數(shù)據(jù)結構，設計算法解決問題。教學方法與教學手段案例分析法、講授法、任務驅動法。教學過程問題導入體驗探索背單詞小明制訂了一個英語學習計劃，其中一項內容是背單詞：第1天背1個單詞，第2天背2個單詞，第3天背3個單詞......即每天都比前一天多背1個單詞，如圖4.2.1所示。經(jīng)過100天的努力，小明覺得收獲頗豐。思考：1.經(jīng)過100天后，小明總共背了多少單詞？你是如何算出來的？2.這個事例對你有什么啟發(fā)？迭代法的概念與特征《荀子·勸學》中有云“不積跬步，無以至千里；不積小流，無以成江海。”要解決復雜問題，可以從簡單的小問題開始，一步一步推進，最終解決復雜問題。背單詞計數(shù)問題正是這樣一個通過不斷解決小問題，進而求解整個問題的典型示例。思考活動設計背單詞計數(shù)問題的算法使用計算機解決背單詞計數(shù)問題，需要為這一問題設計算法。思考：如何設計算法實現(xiàn)背單詞計數(shù)問題的求解？例1：背單詞計數(shù)。首先，將背單詞的過程描述如下：第1天背了1個單詞，累計背了1個單詞；第2天背了2個單詞，比第1天多背1個單詞，累計背了1+2=3個單詞；第3天背了3個單詞，比第2天多背1個單詞，累計背了（1+2）+3=6個單詞；第4天背了4個單詞，比第3天多背1個單詞，累計背了（1+2+3）+4=10個單詞；......第100天背了100個單詞，比第99天多背1個單詞，累計背了（1+2+3+...+99）+100=5050個單詞。這一過程可用表4.2.1記錄。表4.2.1背單詞過程記錄表時間當天背的單詞數(shù)比前一天多背的單詞數(shù)累計背的單詞數(shù)第1天111第2天211+2第3天311+2+3第4天411+2+3+4............第100天10011+2+3+4+...+100通過分析，可以得到如下結論（設n為1～100的自然數(shù)）：第n天背的單詞數(shù)為n；每天都比前一天多背1個單詞，即每天背單詞的增量為1；從第1天至第n天，總共背單詞數(shù)就為1+2+3+...+n。當n=100時，就可以統(tǒng)計出100天背的單詞總數(shù)。通過分析發(fā)現(xiàn)，背單詞的計數(shù)問題可抽象并轉化為連續(xù)自然數(shù)求和問題。要使用計算機解決該問題，就要先選擇合適的數(shù)據(jù)結構，再設計算法。方案一：設計數(shù)組a，用循環(huán)將1至n依次存入數(shù)組，然后設計變量sum保存總和（初值為0），再把數(shù)組的每一個元素和sum相加，最后，sum值就是所求的結果。方案二：使用變量sum保存總和（初值為0），再使用另一個循環(huán)變量i，讓循環(huán)變量從1增加至100（步長為1），循環(huán)過程中執(zhí)行sum與i相加。當循環(huán)結束時，sum值就是最終的結果。算法流程如圖4.2.2所示。在求解背單詞計數(shù)問題過程中，sum的值不斷增加（也稱為累加），而且每一次都用變量的舊值遞推出變量的新值，直至得到最終的結果。這種不斷用變量的舊值遞推新值的過程稱為迭代法，也稱輾轉法。使用迭代法解決問題需要具備三個要件：確定迭代變量、建立迭代關系式和確定迭代的終止條件。確定迭代變量用迭代法解決問題時，迭代過程中至少存在一個直接或間接地不斷由舊值推出新值的變量，這個變量就是迭代變量。在背單詞計數(shù)問題中，sum的新值由舊值不斷推出，因而sum就是迭代變量，它的初值為0，終值就是計算的最終結果。建立迭代關系式迭代關系式指迭代變量由前一個值推出其下一個值的公式（或關系）。建立迭代關系式是解決迭代問題的關鍵。在背單詞計數(shù)問題中，迭代關系式就是sum值的累加關系式：sum=sum+i確定迭代的終止條件通常，迭代的實現(xiàn)要使用循環(huán)，為防止循環(huán)無休止地重復執(zhí)行下去，必須設置終止條件。在背單詞計數(shù)問題中，使用了for循環(huán)，循環(huán)條件是循環(huán)變量i≤n。因此，終止條件就是循環(huán)變量i＞n。例2：求解擴展后的正三角形個數(shù)。（參見教材P119）所示，由多個這樣的正三角形可拼成邊長為2、3、4個單位的正三角形，如圖4.2.5（參見教材P119）所示。如果要拼合成邊長為n的正三角形，需要多少個邊長為1個單位的正三角形？這里，用f(n)表示拼成邊長為n的正三角形所需邊長為1個單位的正三角形的數(shù)量。顯然，f(1)=1。通過觀察，不難發(fā)現(xiàn)：由邊長為1個單位的正三角形，拼成邊長為2個單位的正三角形，可視為增加2個藍色正三角形和1個橘色正三角形，如圖4.2.5(a)所示。因而，f(2)=f(1)+2+1=4；由邊長為2個單位的正三角形，拼成邊長為3個單位的正三角形，可視為增加3個藍色正三角形和2個橘色正三角形，如圖4.2.5(b)所示。因而，f(3)=f(2)+3+2=9；由邊長為3個單位的正三角形，拼成邊長為4個單位的正三角形，可視為增加4個藍色正三角形和3個橘色正三角形，如圖4.2.5(c)所示。因而，f(4)=f(3)+4+3=16；......同樣地，由邊長為n1個單位的正三角形，拼成邊長為n個單位的正三角形，可視為增加n個藍色正三角形和n1個橘色正三角形。因而，f(n)=f(n1)+n+n1=f(n1)+2n1。這一過程可以用表4.2.2表示。由此可見，擴展后的正三角形個數(shù)能夠用迭代法求解，其迭代關系式為f(n)=f(n1)+2n1，且f(1)=1。迭代法的應用迭代法除了可以解決前面提到的背單詞計數(shù)、求最大公因數(shù)、求算術平方根近似值等問題外，其思想還可以用來解決計算機科學中的排序和查找等問題。思考活動設計排序算法某校高一年級組織了7名學生參加演講比賽，這7名學生的選手編號分別為1～7號。在觀眾投票環(huán)節(jié)，選手們獲得的票數(shù)如表4.2.3所示。表4.2.3參賽選手得票數(shù)統(tǒng)計表選手編號1號2號3號4號5號6號7號觀眾投票數(shù)523746331240思考：如果需要用計算機按照得票數(shù)對參賽選手們進行排序，如何設計算法?互聯(lián)網(wǎng)的信息量非常大，比如在如圖4.2.7所示的購物應用中，輸入“算法”查找到6005條與“算法”有關的圖書資料信息。要從中找到一本最貼近需求的書，往往需要對這些列出的數(shù)據(jù)按照一定的規(guī)則進行重新排列。例如，按照銷量、價格、好評或者出版時間等排列。這個過程就是排序，而排序所依據(jù)的數(shù)據(jù)項稱為關鍵字。排序是計算機中經(jīng)常進行的一種操作，其作用是將一組“無序”的數(shù)據(jù)元素序列按關鍵字的順序（升序或降序），調整為“有序”的數(shù)據(jù)元素序列。為方便學習，我們約定數(shù)據(jù)元素存儲在數(shù)組中，排序關鍵字為整型數(shù)據(jù)，對數(shù)據(jù)序列進行升序排列。冒泡排序在眾多排序算法中，冒泡排序是最為常見的排序算法之一。它的基本思想是：兩兩比較相鄰元素，如果反序則交換這兩個元素，直到整個序列沒有反序的元素為止。如何根據(jù)冒泡排序的基本思想，對表4.2.3中的數(shù)據(jù)進行排序？顯然，這個排序問題中的關鍵字是票數(shù)值。為簡單起見，數(shù)組中只存儲選手們獲得的票數(shù)。設數(shù)組名為a，則排序前的數(shù)組a如圖4.2.8（參見教材P123）所示。根據(jù)冒泡排序的基本思想，整個排序過程分析如下：第1趟冒泡排序從第1個關鍵字開始，依次比較相鄰的兩個關鍵字，如果第一個關鍵字大于第二個關鍵字，則交換這兩個關鍵字。第1趟冒泡排序過程如圖4.2.9（參見教材P123）所示。7個關鍵字經(jīng)過6次兩兩比較后，第1趟冒泡排序結束。排序結果是最大關鍵字“46”被交換到a[6]。第2趟冒泡排序只需要對前6個關鍵字進行比較。完整的冒泡排序過程，如圖4.2.10所示。觀察上述排序過程可以發(fā)現(xiàn)，7個數(shù)據(jù)元素需要進行6趟冒泡排序。第1趟需要對7個數(shù)據(jù)元素進行6次比較，而后的每一趟中需要比較的元素個數(shù)比上一趟少1。因此，每一趟中的元素比較次數(shù)也比上一趟少1次。所以，如果待排序列中有n個數(shù)據(jù)元素，則需要進行n1趟冒泡排序，第i趟排序中的元素比較次數(shù)為ni（1≤i≤n1）。冒泡排序的基本過程如下：1.比較第1個和第2個元素，如果第1個比第2個大，就交換這兩個元素。再比較第2個和第3個元素，如果第2個比第3個大，就交換這兩個元素。依此類推，最后比較倒數(shù)第二個元素和最后一個元素，如果倒數(shù)第二個元素比最后一個元素大，就交換這兩個元素。此為第1趟排序，第1趟排序結束后，最后一個元素就是所有元素中最大的。2.按照第1趟排序的方法，對除最后一個元素外的其他所有元素進行第2趟排序。依此類推，持續(xù)對個數(shù)越來越少的元素進行比較，直到第n1趟結束為止。在這種排序方法中，數(shù)值較大的數(shù)據(jù)元素會像“冒泡”一樣經(jīng)由交換“浮”到數(shù)組的末端，冒泡排序法因此而得名。實踐活動冒泡排序算法的編程實現(xiàn)與優(yōu)化1.編寫程序，用冒泡排序算法實現(xiàn)演講比賽選手排序。2.仔細研究圖4.2.10（參見教材P123）中冒泡排序每一趟的過程，可以發(fā)現(xiàn)第4趟沒有發(fā)生數(shù)組元素的交換，說明此時數(shù)組已經(jīng)是有序的，無須再進行第5趟和第6趟排序。請根據(jù)這一發(fā)現(xiàn)，編寫程序，優(yōu)化冒泡排序算法。順序查找順序查找指在一個無序（或有序）數(shù)組中，從頭到尾逐一進行比較，找出關鍵字與給定值相同的數(shù)組元素。如果找到，則查找成功，返回該數(shù)組元素的下標；否則，查找失敗，返回“1”。小明最近迷上了詩詞。他制作了大量詩詞卡片以便隨時吟誦，并對每張卡片都進行了編號。部分卡片的編號存于如圖4.2.11所示的數(shù)組中?，F(xiàn)在，他要查找編號為“77”的卡片。如果采用順序查找法，應該如何查找呢？按照順序查找法的思路，從下標為“0”的元素開始，逐一訪問這個數(shù)組的所有數(shù)據(jù)元素，并與關鍵字“77”進行比較。如果相等，查找成功，并返回該元素的下標；如果不相等，就繼續(xù)向前查找，當數(shù)組中沒有元素可以訪問時，說明數(shù)組中沒有元素“77”，查找失敗，返回“1”。實踐活動順序查找算法的實現(xiàn)1.按照順序查找法的思路，填寫表4.2.4。表4.2.4順序查找過程步數(shù)數(shù)組下標關鍵字與給定值“77”是否相等1023否2175否2.編程實現(xiàn)順序查找算法，并輸入數(shù)據(jù)，驗證其正確性。3.小明和小清各自用Python語言編寫了兩個不同的順序查找函數(shù)，小清覺得自己的算法比小明的更加實用一些。請設計一個方案，編寫程序體驗這兩段程序的運行效果，分析哪一個算法更加合適，并闡明理由。項目實施設計算法一、項目活動（參見教材P113），列舉其中需要使用算法解決的問題，并設計算法。例如，對表4.1.3（參見教材P113）中問題3“對弈雙方落子的實現(xiàn)”的分析如下：對弈的每一方落子相當于改變該點位對應的二維數(shù)組中元素的值。落子后要檢查該方是否滿足五子相連的條件，滿足就是該方獲勝，對弈結束；若不滿足，對方繼續(xù)落子......重復此過程。對弈的過程就轉化為對弈結束條件是否滿足的判定，即設計五子棋判勝算法。設計五子棋判勝算法，首先要了解五子棋判勝和判負的規(guī)則，以最簡單的判勝規(guī)則——五子相連為例，即相連的同一顏色棋子數(shù)等于5時即為獲勝。假如一方在棋盤上落子后獲勝，那么，必然會出現(xiàn)以下四種相連情況之一：在同一行上，五子相連；在同一列上，五子相連；從左上至右下方向，五子相連；從右上至左下方向，五子相連。五子相連的判勝算法即逐一判斷上述四種情況是否存在，如存在，則提示落子方獲勝，對弈結束。如果四種情況都不存在，即落子方?jīng)]有取勝，則對弈繼續(xù)。用數(shù)組a[14][14]表示棋盤，落子點位對應數(shù)組元素a[m][n]，使用循環(huán)巧妙改變m和n的值，即可判斷棋子相連的情況。二、項目檢查設計已確定主題的主要算法，并編程實現(xiàn)。課后作業(yè)1.若用鏈表存儲表4.2.3（參見教材P118）所示的演講比賽選手們的得票