4.2迭代法教學(xué)設(shè)計(jì)人教-中圖版高中信息技術(shù)選擇性必修1數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)

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