資源簡(jiǎn)介

(共36張PPT)
第5單元 第1課
圖書的查找算法
（湘科版）五年級(jí)
下
1
核心素養(yǎng)目標(biāo)
3
新知講解
5
拓展延伸
7
板書設(shè)計(jì)
2
新知導(dǎo)入
4
課堂練習(xí)
6
課堂總結(jié)
課后作業(yè)
8
01
核心素養(yǎng)目標(biāo)
信息意識(shí)
計(jì)算思維
數(shù)字化學(xué)習(xí)與創(chuàng)新
信息社會(huì)責(zé)任
分析算法效率對(duì)系統(tǒng)資源消耗的影響，理解“時(shí)間換空間”的優(yōu)化思想，能通過高效算法快速處理海量數(shù)據(jù)。
能通過修改代碼參數(shù)，驗(yàn)證二分查找中數(shù)據(jù)集有序性的必要性，會(huì)用調(diào)試工具觀察查找過程中中間位置的變化規(guī)律。
會(huì)計(jì)算特定數(shù)據(jù)集下兩種算法的最大/最小比較次數(shù)，掌握二分查找的"分治策略"，理解線性時(shí)間復(fù)雜度。
通過對(duì)比順序查找與二分查找的特點(diǎn)，體會(huì)數(shù)據(jù)結(jié)構(gòu)對(duì)算法效率的重要性，理解數(shù)據(jù)有序性對(duì)查找效率的影響。
02
新知導(dǎo)入
活動(dòng)背景
生活中，我們經(jīng)常會(huì)遇到一些查找問題。比如，在《新華字典》中查找生字，在班級(jí)花名冊(cè)中查找某位同學(xué)的姓名，在手機(jī)通訊錄中查找手機(jī)號(hào)等。在圖書借閱系統(tǒng)中，輸入書名、圖書編碼或作者姓名，計(jì)算機(jī)就會(huì)幫我們快速查找想要的圖書。那么，計(jì)算機(jī)是如何實(shí)現(xiàn)查找的呢？
計(jì)算機(jī)的查找邏輯本質(zhì)上是對(duì)人類智慧的延伸——用結(jié)構(gòu)化存儲(chǔ) 和數(shù)學(xué)規(guī)律 替代了手工翻找的低效過程。
02
新知導(dǎo)入
活動(dòng)目標(biāo)
1、了解查找的基本種類和方法。
2、理解順序查找和二分查找算法的基本思想。
3、體驗(yàn)二分查找算法的程序?qū)崿F(xiàn)。
02
新知導(dǎo)入
03
新知講解
一、查找的基本種類
從被查找對(duì)象的角度來看，如果被查找對(duì)象是無序的，稱為無序查找。如果被查找對(duì)象本身是有序的，稱為有序查找。
03
新知講解
下面兩種查找，哪種是有序查找，哪種是無序查找？
開動(dòng)腦筋
左側(cè)的洗牌動(dòng)作代表撲克牌處于隨機(jī)無序狀態(tài)，屬于無序查找
右側(cè)的小男孩旁邊的對(duì)話框顯示中英文單詞的對(duì)應(yīng)關(guān)系是有序查找。
03
新知講解
二、查找的基本方法
查找的算法有很多種，生活中常見的有順序查找算法和二分查找算法。
◆順序查找
順序查找算法是一種簡(jiǎn)單的查找算法，既可用于無序查找，也可用于有序查找，但查找效率比較低。其基本過程是：從第一個(gè)對(duì)象開始，逐一查找，直到找到符合條件的對(duì)象或找遍全部對(duì)象。
03
新知講解
采用順序查找法，從左至右逐一查找和比較，記錄查找數(shù)據(jù)。
探究實(shí)踐
03
新知講解
查找編號(hào)為“6”的書，進(jìn)行了 次比較。
查找編號(hào)為“5”的書，進(jìn)行了 次比較。
查找編號(hào)為“2”的書，進(jìn)行了 次比較。
從10本不同的書里找1本書，最少需要 次比較，最多需要 次比較。
探究實(shí)踐
1
5
10
1
10
03
新知講解
◆二分查找算法
對(duì)于有序?qū)ο螅覀兛梢圆捎枚植檎宜惴ǎㄟ^逐步縮小查找范圍的過程，大大提高了查找效率。
03
新知講解
（1）用下式計(jì)算中間位置:中間位置=(首位置+尾位置)-2。如果計(jì)算結(jié)果為非整數(shù)，取整數(shù)部分。
（2）將編號(hào)“16”與中間位置6的編號(hào)“14”進(jìn)行比較。16>14，將查找范圍縮小到位置6的右側(cè)。
（3）將編號(hào)“16”與中間位置9的編號(hào)“18”進(jìn)行比較。16<18，將查找范圍縮小到位置9的左側(cè)。
（4）將“16”與中間位置7的編號(hào)“16”進(jìn)行比較。兩者相等，查找完成。
03
新知講解
在以上的例子中，使用順序查找和二分查找各需要比較多少次才能找到編號(hào)為“20”的這本書
開動(dòng)腦筋
查找方法 比較次數(shù)
順序查找（從左至右） 10次
二分查找 3次
03
新知講解
開動(dòng)腦筋
1. 順序查找
查找過程：從位置1開始逐個(gè)比較編號(hào)，直到找到目標(biāo)編號(hào)20。
依次比較：3→7→9→11→13→14→16→17→18→20 （第10次命中）
比較次數(shù)：10次 （編號(hào)20位于第10個(gè)位置）
2. 二分查找
前提條件：數(shù)據(jù)已按升序排列（滿足二分查找要求）。
查找過程：
第1次比較：中間位置6（編號(hào)14），14 < 20 → 向右半部分繼續(xù)查找。
第2次比較：中間位置9（編號(hào)18），18 < 20 → 向右半部分繼續(xù)查找。
第3次比較：中間位置10（編號(hào)20），命中目標(biāo)。
比較次數(shù)：3次
03
新知講解
二分查找算法的基本思想是在一組有序的數(shù)據(jù)中，通過將目標(biāo)數(shù)據(jù)與中間位置的數(shù)據(jù)進(jìn)行比較，可將待查找的范圍縮小為之前的一半，直到找到要查找的數(shù)據(jù)，或者查找范圍被縮小為0(沒有找到)。
重點(diǎn)
03
新知講解
三、二分查找算法的程序?qū)崿F(xiàn)
用程序?qū)崿F(xiàn)猜幸運(yùn)數(shù)字游戲。在猜幸運(yùn)數(shù)字游戲的程序中，為了簡(jiǎn)化程序，數(shù)的大小與數(shù)的位置相關(guān)聯(lián)，如數(shù)字“1”排在第一位。
03
新知講解
1、兩人一組玩猜幸運(yùn)數(shù)字游戲，規(guī)則如下:甲同學(xué)在紙上寫下1~100中間的任意數(shù)字作為幸運(yùn)數(shù)字，讓乙同學(xué)來猜這個(gè)數(shù)字。乙同學(xué)用二分查找的方法猜測(cè)幸運(yùn)數(shù)字,甲同學(xué)提示乙同學(xué)猜測(cè)的數(shù)字比幸運(yùn)數(shù)字大或小，直到猜中為止。
探究實(shí)踐
03
新知講解
2、運(yùn)行猜幸運(yùn)數(shù)字游戲程序，與計(jì)算機(jī)玩猜幸運(yùn)數(shù)字游戲。
探究實(shí)踐
03
新知講解
03
新知講解
3、修改查找范圍，運(yùn)行程序，記錄不同查找范圍下查找次數(shù)的變化。
查找范圍大小（元素?cái)?shù)量） 查找次數(shù)（比較次數(shù)） 關(guān)鍵操作說明
10 4 每次折半，最多需 log2(10)≈3.32 → 4次
20 5 log2(20)≈4.32 → 5次（向上取整）
50 6 log2(50)≈5.64 → 6次
100 7 log2(100)≈6.64 → 7次
200 8 log2(200)≈7.64 → 8次
500 9 log2(500)≈8.96 → 9次
04
課堂練習(xí)
一、選擇題
1、二分查找算法的前提條件是什么？（ ）
A. 數(shù)據(jù)必須存儲(chǔ)在鏈表中 B. 數(shù)據(jù)必須是無序的
C. 數(shù)據(jù)必須是有序的 D. 數(shù)據(jù)必須全部是數(shù)字
2、在一個(gè)包含10個(gè)元素的有序數(shù)組中，二分查找最多需要多少次比較？( )
3次 B. 4次 C. 5次 D. 10次
3、下列哪種場(chǎng)景最適合使用二分查找？( )
A. 在未排序的購物清單中找商品
B. 在按姓名排序的電話簿中查號(hào)碼
C. 在隨機(jī)洗牌的撲克牌中找特定花色
D. 在無序的班級(jí)名單中查找學(xué)生
C
B
B
04
課堂練習(xí)
4、圖書館有10本書按編號(hào)從小到大排列（1,3,5,7,9,11,13,15,17,19），用二分法找編號(hào)13的書，需要比較幾次（ ）
A. 1次 B. 2次 C. 3次 D. 4次
5、小明在玩具箱里找紅色樂高積木，他從第一個(gè)玩具開始一個(gè)一個(gè)檢查，直到找到紅色積木。這種查找方法叫什么？（ ）
A. 快速查找 B. 順序查找 C. 密碼查找 D. 魔法查找
二、判斷題
1、順序查找算法可以用于鏈表結(jié)構(gòu)的數(shù)據(jù)，但二分查找不能直接用于鏈表。（ ）。
D
√
B
04
課堂練習(xí)
三、操作題
動(dòng)手制作“有序魔法書
任務(wù)：剪下10張紙片，分別寫上數(shù)字：6、2、9、15、4、12、7、1、10、5。
將這些數(shù)字按 從小到大排列 ，用膠水粘成一行，制作成“魔法書頁”。用“二分查找小秘籍”找到數(shù)字7。
第1步：找到中間的數(shù)字（如果偶數(shù)個(gè)，選左邊）。
第2步：如果中間數(shù)=7，成功！如果中間數(shù)<7，向右找；如果中間數(shù)>7，向左找。
重復(fù)直到找到7，記錄比較次數(shù)。
05
拓展延伸
計(jì)算機(jī)的“烹飪步驟”
算法是解決問題的明確指令集合，如同菜譜指導(dǎo)烹飪。例如：導(dǎo)航軟件中的路徑規(guī)劃算法（輸入起點(diǎn)終點(diǎn)，輸出最優(yōu)路線）、短視頻推薦算法（分析用戶行為，輸出個(gè)性化內(nèi)容）。算法的五大特性：有窮性、確定性、可行性、輸入、輸出。
05
拓展延伸
分治算法
將大問題拆解為相似小問題，分別解決后合并結(jié)果。經(jīng)典案例：歸并排序（將數(shù)組拆分成單元素再合并排序）、快速排序（選基準(zhǔn)值分左右區(qū)間）。應(yīng)用場(chǎng)景：大規(guī)模數(shù)據(jù)排序、地圖導(dǎo)航中的區(qū)域路徑規(guī)劃。
05
拓展延伸
自我復(fù)制的魔法
遞歸是函數(shù)調(diào)用自身的過程，依賴內(nèi)存棧臨時(shí)保存狀態(tài)。例如：計(jì)算斐波那契數(shù)列（F(n)=F(n-1)+F(n-2)）、遍歷文件夾目錄樹。注意：遞歸需設(shè)置終止條件，否則會(huì)導(dǎo)致棧溢出（如無限循環(huán)調(diào)用）。
05
拓展延伸
貪心策略的取舍
每一步選擇局部最優(yōu)解，期望達(dá)到全局最優(yōu)。例如：零錢兌換（優(yōu)先用最大面額硬幣）、哈夫曼編碼（構(gòu)建最優(yōu)前綴樹）。局限性：貪心策略未必全局最優(yōu)，如旅行商問題（TSP）中可能得到較差解。
05
拓展延伸
連接萬物的紐帶
圖論算法處理節(jié)點(diǎn)與邊的關(guān)系。經(jīng)典算法：廣度優(yōu)先搜索（BFS）找最短步數(shù)、深度優(yōu)先搜索（DFS）解決迷宮問題。現(xiàn)實(shí)應(yīng)用：社交網(wǎng)絡(luò)好友推薦（六度空間理論）、物流網(wǎng)絡(luò)優(yōu)化（最小生成樹）。
05
拓展延伸
數(shù)字世界的守護(hù)者
加密算法保障信息安全。對(duì)稱加密（AES：加密解密同一密鑰）速度快，非對(duì)稱加密（RSA：公鑰加密私鑰解密）更安全。應(yīng)用場(chǎng)景：HTTPS通信、比特幣交易中的SHA-256哈希算法。
06
課堂總結(jié)
1
引入新知內(nèi)容
圖書的查找算法
2
學(xué)習(xí)查找的基本種類
3
學(xué)習(xí)查找的基本方法
4
完成課題練習(xí)
5
進(jìn)行相關(guān)知識(shí)拓展
1
2
3
4
5
07
板書設(shè)計(jì)
圖書的查找算法
1、進(jìn)行新知引入
2、學(xué)習(xí)查找的基本種類
3、學(xué)習(xí)查找的基本方法
4、完成課堂練習(xí)
5、進(jìn)行知識(shí)拓展
課后作業(yè)。
1、二分查找算法的具體應(yīng)用。
08
課后作業(yè)
1、采用二分查找算法，從“1、2、3、4、5、6、7、8、9、10”中查找一個(gè)數(shù)，最少比較次數(shù)為 ，最多比較次數(shù)為 。
在 1到10的有序數(shù)組 中使用二分查找：
最少比較次數(shù)：1次
（當(dāng)目標(biāo)值恰好是中間元素時(shí)，例如查找數(shù)字5或6，第一次比較即命中。）
最多比較次數(shù)：4次
（例如查找數(shù)字10：需比較5→8→9→10，共4次。）
08
課后作業(yè)
2、二分查找算法中的二分思想在生活中也有類似的應(yīng)用。假如有 20枚相同的硬幣，其中有一枚因質(zhì)量不合格，比其他的硬幣輕一些，想一想如何用一臺(tái)天平快速地找出那枚不合格的硬幣。
從 20枚硬幣 中找出質(zhì)量不合格的硬幣，最少需要 3次稱量。
第一次稱量：將20枚硬幣分為 7枚、7枚、6枚，稱量前兩組7枚。若兩邊平衡 ，不合格硬幣在剩下的6枚中。若一邊較輕/較重 ， 不合格硬幣在該邊的7枚中。
第二次稱量：
如果剩余6枚 ， 分成 2枚、2枚、2枚，稱量前兩組2枚。如果剩余7枚 ， 分成 3枚、3枚、1枚，稱量前兩組3枚。
第三次稱量：
對(duì)剩余2~3枚稱量，直接比較單枚或兩兩對(duì)比，最終確定不合格硬幣。
https://www.21cnjy.com/recruitment/home/fine

展開更多......

收起↑