4.3非數(shù)值計(jì)算-二分查找+++課件【知識(shí)精講精研】教科版（2019）高中信息技術(shù)必修1

4.3非數(shù)值計(jì)算——二分查找高中信息技術(shù)二分查找算法介紹二分查找算法及其應(yīng)用的教學(xué)分析二分查找算法的Python實(shí)現(xiàn)二分查找算法的應(yīng)用實(shí)例課堂練習(xí)與課后預(yù)習(xí)作業(yè)課堂總結(jié)與教學(xué)反思01二分查找算法介紹計(jì)算思維選擇合適的方法解決問(wèn)題，通過(guò)邏輯判斷和數(shù)學(xué)運(yùn)算來(lái)確定查找路徑。信息意識(shí)能夠敏銳地判斷信息價(jià)值，了解哪些數(shù)據(jù)是有序的，哪些數(shù)據(jù)是隨機(jī)的，從而選擇合適的算法進(jìn)行查找。數(shù)字化學(xué)習(xí)與創(chuàng)新能夠運(yùn)用數(shù)字化工具自主學(xué)習(xí)和合作學(xué)習(xí)，通過(guò)編程實(shí)現(xiàn)二分查找算法。在二分查找算法中，需要遵守以下信息安全意識(shí)與能力。核心素養(yǎng)信息安全意識(shí)與能力不得在未經(jīng)授權(quán)的情況下查看或修改數(shù)據(jù)信守道德與倫理準(zhǔn)則注意保護(hù)個(gè)人隱私不進(jìn)行惡意攻擊或未經(jīng)授權(quán)的查找遵守信息法律法規(guī)了解分治思想：通過(guò)案例分析，讓學(xué)生了解分治策略的思想和適用場(chǎng)景。掌握二分查找算法：通過(guò)編程實(shí)現(xiàn)二分查找算法，并能夠分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度。解決實(shí)際問(wèn)題：能夠運(yùn)用二分查找算法解決實(shí)際問(wèn)題，如查找IP地址、搜索網(wǎng)站等。培養(yǎng)信息安全意識(shí)：能夠了解信息安全的常見(jiàn)威脅和防范措施，如病毒、黑客等。在二分查找算法中，需要通過(guò)對(duì)數(shù)組進(jìn)行劃分、比較和判斷來(lái)實(shí)現(xiàn)查找，因此需要學(xué)生具備一定的數(shù)學(xué)基礎(chǔ)和邏輯思維能力。同時(shí)，還需要學(xué)生具備一定的編程能力和信息安全意識(shí)，以更好地應(yīng)用二分查找算法解決實(shí)際問(wèn)題。課程標(biāo)準(zhǔn)要求02二分查找算法及其應(yīng)用的教學(xué)分析能力目標(biāo)培養(yǎng)學(xué)生運(yùn)用二分查找算法解決實(shí)際問(wèn)題的能力，提高學(xué)生的計(jì)算思維和數(shù)字化學(xué)習(xí)與創(chuàng)新的能力。教學(xué)目標(biāo)情感態(tài)度和價(jià)值觀目標(biāo)培養(yǎng)學(xué)生的信息意識(shí)，讓學(xué)生認(rèn)識(shí)到信息價(jià)值的重要性。培養(yǎng)學(xué)生的信息安全意識(shí)與能力，遵守信息法律法規(guī)、信守道德與倫理準(zhǔn)則。知識(shí)目標(biāo)讓學(xué)生了解二分查找算法的原理和實(shí)現(xiàn)方法，掌握二分查找算法的步驟和流程。教材內(nèi)容本節(jié)內(nèi)容為二分查找算法及其應(yīng)用，包括二分查找算法的原理、實(shí)現(xiàn)方法、步驟和流程，以及二分查找算法的應(yīng)用實(shí)例。重點(diǎn)難點(diǎn)二分查找算法的原理和實(shí)現(xiàn)方法是本節(jié)的重點(diǎn)，而如何應(yīng)用二分查找算法解決實(shí)際問(wèn)題則是本節(jié)的難點(diǎn)。教學(xué)內(nèi)容分析教學(xué)重點(diǎn)01讓學(xué)生掌握二分查找算法的原理和實(shí)現(xiàn)方法，理解二分查找算法的步驟和流程。教學(xué)重難點(diǎn)教學(xué)難點(diǎn)02如何應(yīng)用二分查找算法解決實(shí)際問(wèn)題，提高學(xué)生的計(jì)算思維和數(shù)字化學(xué)習(xí)與創(chuàng)新的能力。教學(xué)策略03通過(guò)問(wèn)題解決法、案例分析法等教學(xué)方法，引導(dǎo)學(xué)生自主學(xué)習(xí)、合作學(xué)習(xí)，通過(guò)觀察、思考、實(shí)踐等方式，讓學(xué)生更好地理解和掌握二分查找算法及其應(yīng)用。通過(guò)設(shè)計(jì)問(wèn)題、引導(dǎo)學(xué)生解決問(wèn)題的方式，讓學(xué)生自主探究、合作學(xué)習(xí)，培養(yǎng)學(xué)生的問(wèn)題解決能力和計(jì)算思維。教學(xué)方法問(wèn)題解決法通過(guò)分析二分查找算法在實(shí)際問(wèn)題中的應(yīng)用案例，讓學(xué)生更好地理解二分查找算法的應(yīng)用場(chǎng)景和實(shí)現(xiàn)方法。案例分析法通過(guò)小組討論的方式，鼓勵(lì)學(xué)生交流意見(jiàn)、互相學(xué)習(xí)，提高學(xué)生的自主學(xué)習(xí)和合作學(xué)習(xí)能力。小組討論法03二分查找算法的Python實(shí)現(xiàn)在上面的代碼中，我們首先定義了兩個(gè)變量`low`和`high`，它們分別表示要查找的范圍的下界和上界。然后，我們使用一個(gè)循環(huán)來(lái)不斷縮小查找范圍，直到找到要查找的元素或者范圍為空。在每次循環(huán)中，我們計(jì)算中間位置`mid`，并將數(shù)組中`mid`位置的元素與要查找的元素進(jìn)行比較。如果它們相等，則返回`mid`。如果`A[mid]`小于要查找的元素，則說(shuō)明要查找的元素在`mid`的右側(cè)，因此將`low`更新為`mid1`。如果`A[mid]`大于要查找的元素，則說(shuō)明要查找的元素在`mid`的左側(cè)，因此將`high`更新為`mid-1`。這樣就可以不斷縮小查找范圍。代碼實(shí)現(xiàn)二分查找算法不僅可以用于數(shù)值計(jì)算，還可以用于非數(shù)值計(jì)算。例如，在字符串匹配中，可以使用二分查找算法來(lái)快速查找指定的字符串。此外，還有許多其他的場(chǎng)景可以使用二分查找算法來(lái)提高查找效率。知識(shí)拓展04二分查找算法的應(yīng)用實(shí)例這是一個(gè)非常經(jīng)典的二分查找應(yīng)用實(shí)例。游戲規(guī)則如下。計(jì)算機(jī)隨機(jī)生成一個(gè)1到1000之間的整數(shù)。玩家每次輸入一個(gè)整數(shù)，如果這個(gè)數(shù)比計(jì)算機(jī)生成的數(shù)大，則計(jì)算機(jī)提示“大了”，如果這個(gè)數(shù)比計(jì)算機(jī)生成的數(shù)小，則計(jì)算機(jī)提示“小了”。如果玩家猜中了這個(gè)數(shù)，則游戲結(jié)束，否則繼續(xù)猜。在這個(gè)游戲中，玩家需要使用二分查找的思想，每次取中間的數(shù)進(jìn)行比較，不斷縮小猜數(shù)的范圍，最終猜中答案。猜數(shù)字小游戲0102030405補(bǔ)全翻字典程序在這個(gè)程序中，二分查找的思想被廣泛應(yīng)用于查找字典中的詞匯。在相應(yīng)部分內(nèi)進(jìn)行二分查找，不斷縮小查找的范圍，直到找到要查找的詞為止。然后在詞典中以第一個(gè)字母或者拼音為索引，查找相應(yīng)的部分。這是一個(gè)類似的問(wèn)題，可以適用于中文詞典的查找。具體步驟如下。首先確定查找的詞的第一個(gè)字母或者拼音。漢諾塔問(wèn)題首先確定漢諾塔的層數(shù)和盤子數(shù)量：其次將最底層的盤子分為兩部分，一部分是已經(jīng)疊好的盤子，另一部分是需要移動(dòng)的盤子。然后將需要移動(dòng)的盤子再分為兩部分，一部分是已經(jīng)疊好的盤子，另一部分是需要移動(dòng)的盤子。以此類推，直到最后將所有的盤子移動(dòng)到目標(biāo)塔為止。05課堂練習(xí)與課后預(yù)習(xí)作業(yè)課堂練習(xí)與課后預(yù)習(xí)作業(yè)課堂練習(xí)dictionary,targetwhileleft<=right。ifdictionary[mid]==target。returnmid找到目標(biāo)，返回其索引。示例用法dictionary={'apple':1,'banana':2,'orange':3,'pear':4}。result=binary_search。補(bǔ)全翻字典程序在Python中，我們可以使用二分查找算法來(lái)快速查找字典中的鍵或值。下面是一個(gè)簡(jiǎn)單的補(bǔ)全翻字典程序的示例代碼。03printf"Movedisk{n}from{source}to{target}"。課堂練習(xí)與課后預(yù)習(xí)作業(yè)課堂練習(xí)01dictionary,targetwhileleft<=right。ifdictionary[mid]==target。returnmid找到目標(biāo)，返回其索引。02printf"Movedisk{n}from{source}to{target}"。課堂練習(xí)與課后預(yù)習(xí)作業(yè)課堂練習(xí)該程序使用遞歸實(shí)現(xiàn)漢諾塔問(wèn)題的解決。當(dāng)盤子數(shù)量大于1時(shí)，程序?qū)?wèn)題分解為兩個(gè)子問(wèn)題。首先將上面的n-1個(gè)盤子從源柱子移動(dòng)到輔助柱子上，然后將最后一個(gè)盤子從源柱子移動(dòng)到目標(biāo)柱子上，最后再將n-1個(gè)盤子從輔助柱子移動(dòng)到目標(biāo)柱子上。當(dāng)盤子數(shù)量為1時(shí)，程序直接將盤子從源柱子移動(dòng)到目標(biāo)柱子上。請(qǐng)注意，該程序僅輸出盤子的移動(dòng)步驟，如果需要完整的解決方案，可以修改代碼以記錄每個(gè)步驟的時(shí)間和所需的總時(shí)間。分組討論：漢諾塔問(wèn)題：漢諾塔問(wèn)題是經(jīng)典的遞歸問(wèn)題之一，涉及到二分查找算法的應(yīng)用。該問(wèn)題包括三個(gè)柱子和若干個(gè)不同大小的盤子，開(kāi)始時(shí)所有盤子按大小順序堆疊在第一個(gè)柱子上，目標(biāo)是把這些盤子移動(dòng)到第三個(gè)柱子上，并且在移動(dòng)過(guò)程中每次只能移動(dòng)一個(gè)盤子，并且不能把一個(gè)較大的盤子放在一個(gè)較小的盤子上。下面是一個(gè)簡(jiǎn)單的Python代碼示例，用于解決漢諾塔問(wèn)題。課堂練習(xí)與課后預(yù)習(xí)作業(yè)課堂練習(xí)n,source,target,auxiliary。defhanoif"Movedisk{n}from{source}to{target}"。printfrom{source}to{target}"。f"Movedisk課堂練習(xí)與課后預(yù)習(xí)作業(yè)課堂練習(xí)n-1,auxiliary,target,source。hanoiprinthanoif"Movedisk{n}from{source}to{target}"。n-1,auxiliary,target,source。03課堂練習(xí)與課后預(yù)習(xí)作業(yè)課堂練習(xí)0201dictionary={'apple':1,'banana':2,'orange':3,'pear':4}。result=binary_search。課堂練習(xí)與課后預(yù)習(xí)作業(yè)課堂練習(xí)auxiliary="B"輔助柱子。hanoi。n,source,target,auxiliary。該程序使用遞歸實(shí)現(xiàn)漢諾塔問(wèn)題的解決。當(dāng)盤子數(shù)量大于1時(shí)，程序?qū)?wèn)題分解為兩個(gè)子問(wèn)題。首先將上面的n-1個(gè)盤子從源柱子移動(dòng)到輔助柱子上，然后將最后一個(gè)盤子從源柱子移動(dòng)到目標(biāo)柱子上，最后再將n-1個(gè)盤子從輔助柱子移動(dòng)到目標(biāo)柱子上。當(dāng)盤子數(shù)量為1時(shí)，程序直接將盤子從源柱子移動(dòng)到目標(biāo)柱子上。請(qǐng)注意，該程序僅輸出盤子的移動(dòng)步驟，如果需要完整的解決方案，可以修改代碼以記錄每個(gè)步驟的時(shí)間和所需的總時(shí)間。示例用法target="C"目標(biāo)柱子06課堂總結(jié)與教學(xué)反思你學(xué)到了哪些新的概念和方法？：通過(guò)本節(jié)課的學(xué)習(xí)，學(xué)生應(yīng)該能夠理解二分查找算法的基本思想、工作原理以及在非數(shù)值計(jì)算中的應(yīng)用。此外，學(xué)生還可能會(huì)學(xué)到一些其他的方法，例如迭代法等。你如何理解分治策略和二分查找算法的關(guān)系。分治策略是一種解決問(wèn)題的基本方法，它將一個(gè)復(fù)雜的問(wèn)題分解為若干個(gè)較小的、相似的子問(wèn)題，然后分別解決這些子問(wèn)題，最后將子問(wèn)題的解組合起來(lái)形成原問(wèn)題的解。二分查找算法是分治策略的一個(gè)典型應(yīng)用，它將有序數(shù)組分成兩半，然后在其中一半繼續(xù)查找，直到找到目標(biāo)元素或確定目標(biāo)元素不存在為止。學(xué)生總結(jié)鞏固本節(jié)課的知識(shí)本節(jié)課的優(yōu)點(diǎn)本節(jié)課的優(yōu)點(diǎn)包括：引入了猜數(shù)字小游戲，激發(fā)了學(xué)生的學(xué)習(xí)興趣。通過(guò)舉例、分組討論等方式幫助學(xué)生理解和掌握知識(shí)。讓學(xué)生了解了分治策略和二分查找算法的關(guān)系及其在實(shí)際