資源簡介

第三課：精準的查找算法
教學內容：
查找算法是我們日常生活中經常使用的一種算法。本課選取了其中最常用順序查找法和二分查找法。通過運用所學的兩種查找算法解決問題，學生不僅能強化對這些算法的理解，還能提升自身的邏輯思維能力。
教學目標：
掌握順序查找法和二分查找法的算法原理。
選擇合適的算法解決簡單問題,
教學重點：
(1)順序查找法的原理。
(2)二分查找法的原理。
教學難點：
選擇合適的算法解決簡單問題
教學過程：
情境導入
師：同學們，在上課之前我們來玩個游戲吧，猜整數游戲，我們來找幾個個同學，分別來扮演出題人、證明人和競猜人，有沒有同學想主動參與的？請舉手。
生：……
師：好，大家都很積極踴躍的參與，角色已經選好了，接下來我們來看一下游戲規則，請看大屏幕：出題人從 1~100中選擇一個整數，并告訴證明人，而競猜人則嘗試猜出選定的整數。誰能用最少的次數猜中該數，誰就是贏家。
生：……
師：游戲中猜整數的過程就是查找的過程，查找的次數與查找算法直接相關。查找算法是在數據中查找特定元素或滿足特定條件的算法，其目標是高效地找到數據中的位置或確認數據是否存在，主要包括順序查找法、二分查找法等。
二：順序查找法
師：猜整數游戲設定了從 1~100整數的數據序列，出題人從中隨機選取一個數字作為目標。對于競猜人而言，為了確保能夠排查每一個可能的數字直至找到正確答案，最直接且直觀的策略是從數字1開始逐一猜測，持續進行直到成功猜中目標整數。我們來看一下這個游戲的算法，請看大屏幕。
師：接下來請大家根據這個流程圖，補全順序查找法猜整數游戲的程序，并且調試運行。
師：巡視指導
師：在理想情況下，運用順序查找法猜整數游戲需要幾次可以猜中 在最差情況下，需要幾次可以猜中
生：……
師：大家的想法很好，除了從開頭的數字開始查找之外，順序查找法也可以從末尾的數字開始，請同學們修改程序，實現從數字100開始自動查找的功能。
生：
師：順序查找法以簡單直觀和通用性強而著稱。但在數據量較大時，查找效率相對較低。
三、二分查找法
師：在猜整數游戲中，為了確保能夠快速猜中整數，競猜人需要從序列的-端開始逐個猜測。為了提高該游戲的趣味性，將游戲規則修改為:每當競猜人報出一個數字后，證明人會提供反饋，告訴競猜人所猜的整數是比目標數高了還是低了。那么，競猜人又該如何以最少的次數猜中目標數呢 接下來，請同學們通過小試身手來研究這個問題。
師：在1~100整數范圍內，若目標數是59，最快多少次能猜中
競猜人說出1~100之間的中間整數____。證明人回答“猜小了”猜數人舍棄所有比中間數小的數字。
2、競猜人在剩下的數字中繼續說出中間整數____。證明人回答“猜大了”，競猜人再次舍棄所有比中間數大的數字。
3、繼續重復以上步驟,直至找到目標數，總共猜了幾次。
生：做題中……
師：由此可以看出，每次猜整數時都會舍棄一半的數據，這種算法被稱為二分查找法。二分查找法，也稱折半查找法，是一種在有序數據集中查找特定元素的算法。它通過不斷縮小查找范圍來提高效率，在計算機科學和數學領域都有廣泛的應用。
師：同桌兩人相互使用二分查找法嘗試猜整數游戲，體會二分查找法的含義。接下來補全人機猜整數游戲的程序。我們從數字1~100范圍內選擇一個整數，讓計算機來猜。補全下列程序，并調試運行。然后回答下面這個問題：二分查找法猜整數游戲在理想情況下，最少幾次可以猜中 最差情況下，最多幾次可以猜中
生：編寫程序。
師：巡視指導。
師：與順序查找算法不同，二分查找法要求待查找的數據必須是已經排序的序列，如1~100的整數序列，就是一個有序序列，因此可以應用二分查找法進行快速查找。
師：二分查找法因其高效性和出色的穩定性，在多個領域得到廣泛應用。其核心思想就是一分為二。在實際操作中，我們經常利用這一思想，將復雜的大問題分解成一系列結構相似但規模更小的子問題，這些子問題相對簡單，更易于解決。最終，將這些子問題的解整合起來，就能得到原問題的解。這種分解與整合的過程不僅降低了問題的復雜性，也提高了解決問題的效率。
四、查找算法的應用
師：某工廠生產了一批螺母，共計1000個。其中有一個螺母存在質量超標的情況。由于這批螺母的形狀和大小完全一致，工廠需要尋找一個有效的方法來精準識別出這個質量異常的螺母。組內討論是否可以利用一架天平找出質量異常的螺母？我們左邊這部分同學使用順序查找法，右邊使用二分查找法，然后分別填寫在最好和最壞情況下，兩種算法找到質量異常的螺母分別比較了多少次
五、總結
無論是順序查找法還是二分查找法，它們并無絕對的優劣之分，不應片面認為哪一種絕對優于另一種，這與排序算法的選擇原則存在顯著差異。排序算法的目標單一且明確，即實現數據的排序，因此必須根據任務的具體規模和需求選擇最合適的算法不同算法間的性能差異往往十分顯著。今天的課就到這里了，請大家做一下這兩道題來鞏固一下。
六、挑戰自我
1、小睿有10張數字卡片，他想快速找出最小的一張，應用排序方法的一項是(）
A.順序查找法
C.枚舉算法
B.二分查找法
D.選擇排序
2、在找出超重螺母的場景中，我們可以使用“三分法”的算法:先拿出一個螺母，將剩下的螺母平均分為3份，任取兩份進行稱量，可以大幅減少比較次數。根據以上說明，繪制出相應算法的流程圖。

展開更多......

收起↑