資源簡介

(共18張PPT)
對象 數字 關 系
C+C+A=C+10
B+A+1=B+10
B+1=A
C+A=10
A+1=10
B+1=A
A=9
B=8
C=1
A
B
C
未知
未知
未知
？
（5+6-3）×3=24
6×（5-3÷3）=24
6×（3×3-5）=24
（6-3）×（5+3）=24
3×5+3+6=24
5×6-3-3=24
怎么樣才能把所有解法都找出來呢？
獲得所有可能的答案
算法
執教者：
要在手機聯系人里找到某個人，通常情況下，你會怎么做？
w
分治法（分而治之）
把一個復雜的問題分成兩個或n個相同或相似的子問題，再把子問題分成更小的子問題，直到最后子問題可以簡單的直接求解，原問題的解就是子問題的解的合并。
分治法（分而治之）
首字母分類查找
從30張面值不等的鈔票中抽出10張，怎樣才能獲得最多的價值？
貪心算法
做出當前的最優選擇。就是通過局部的最優選擇獲得整體的最優選擇。
每次都選擇現下的鈔票中面值最大的，最后拿到的就是最優解。
解析法
枚舉法
分治法
貪心算法
動態規劃算法
經過大量的實踐，人們發現了算法某些共性的規律，總結了經典的算法思想。合理地選擇經典算法思想，可以為具體問題的解決設計出更加精妙的算法。
……
“雞兔同籠”問題需要在一定范圍內尋找正確解，可以使用枚舉法。
枚舉法的思想是 ，如果滿足正確解的條件就采納，否則繼續枚舉，做到不遺漏、不重復。
在班級名單中查找符合條件的名字，通常我們會怎么做？
認識枚舉法
一
有序地嘗試每一種可能的解
9○ 13 ○ 7=100
填上合適的＋－×÷使得等式成立。
玩24點游戲時在頭腦中羅列各種可能的算式
在一篇文章中摘錄好詞好句
用一串沒有標記的鑰匙打開教室的門，通常你會怎么做？
認識枚舉法
一
如果讓計算機通過枚舉法，從一串鑰匙中找到打開教室對應的那一把鑰匙，我們需要告訴計算機什么信息它才能停止查找？
如果這把鑰匙能打開教室門，
就不用再往下嘗試了。
正確解的判斷條件
一共有幾把鑰匙【這樣，計算機就知道一共要試幾次了】
確定枚舉的范圍
枚舉法的關鍵
否
否
是
是
是
枚舉法流程圖
認識枚舉法
一
為什么在登錄網站、APP、ATM自動柜員機時，系統要限制用戶輸入密碼的次數？
認識枚舉法
一
為什么在登錄網站、APP、ATM自動柜員機時，系統要限制用戶輸入密碼的次數？
為了保護財產安全，防止犯罪分子利用枚舉法的思想破解密碼。
算法框架的確定
二
在明確枚舉法算法思想的基礎上，使用具體的計算模型，合理選擇控制結構，可以得到解決具體問題的算法框架，最終解決問題，找到答案。
雞兔同籠計算模型
ji+tu=35
ji×2+tu ×4=94
0≤ji≤35 0≤tu≤35
確定枚舉的范圍
正確解的判斷條件
使用循環結構在0-35之間枚舉ji或tu。
使用分支結構判斷是否滿足正確解的條件
如果……那么……
重復執行……
兔的只數（tu）
雞的只數（ji）
總腳數
是否滿足正確解條件
兔的只數（tu）
0
1
2
35
35-0
35-1
35-2
0≤ji≤35 0≤tu≤35
枚舉兔的數量，完成表格的填寫。
ji+tu=35
ji×2+tu×4=94
確定枚舉的范圍
正確解的判斷條件
……
12
……
35-12
35-35
……
……
70
72
74
……
94
……
140
×
×
×
……
√
×
×
雞兔同籠
算法的描述
三
描述算法時，要精準地描述算法的每一步驟，明確算法的輸入和輸出。對于大部分算法來說，輸入數據是必要的，但是有的算法不需要輸入數據或者算法本身給定了初始條件。比如雞兔同籠的問題，就可以把tu的值初始化為0，因為是從0開始羅列的。
枚舉兔的數量，“雞兔同籠”算法描述：
1.兔子只數從0開始羅列。
2.確定枚舉范圍：兔子是在羅列范圍內嗎？
3.如果超出羅列范圍，那么結束；如果沒有超出羅列范圍，那么計算雞的數量。
4.正確解的判斷條件：兔子和雞的只數符合條件嗎？
5.如果符合條件，那么輸出兔子和雞的只數；
6.如果不符合條件，那么羅列下一個。
算法的描述
三
除了枚舉兔的數量，還可以枚舉哪些數量？
兔的腳數 4 8 …… 48 …… 92
雞的腳數 （94-4）÷2 （94-8）÷2 …… （94-48）÷2 …… （94-92）÷2
總只數 46 45 …… 35 …… 23
是否滿足正確解條件 × × …… √ …… ×
枚舉法
1.枚舉法的思想是 地嘗試 的解。
2.枚舉法的關鍵是① 。
② 。
有序
每一種可能
確定枚舉的范圍
正確解的判斷條件中小學教育資源及組卷應用平臺
第3課 算法設計
預設教學目標：
1.了解算法思想的概念，能夠對問題選擇合適的算法思想。
2.了解經典算法中分治法、貪心算法和枚舉法的概念；
3.能清楚枚舉法的概念和過程，學會使用枚舉法進行算法設計。
預設教學重點與難點：
用枚舉法進行算法設計。
預設教學課時：
1課時
預設教學準備：
課件、課本、學生練習學案等
預設教學過程：
一、課題導入
【探索】
1.上一節課我們學習了抽象與建模，知道了抓住問題的核心，理清關鍵要素之間的關系，有助于問題的解決。
請你來看這道數學題。
課件出示：破譯字母算式
解決這個問題主要的方法和步驟是怎么樣的呢？算一算，寫一寫。
學生思考并回答。
課件出示表格。
這個問題需要知道的目標是？（ABC）現在我們知道它們分別代表什么數字嗎？（未知）那它們之間有沒有關系呢？想一想列豎式計算中，它們之間會是什么關系呢？
學生回答，課件出示。
根據列出來的關系，是不是就能馬上解決這個問題了？（出示結果）
2.再看一道常見的計算24點游戲題，誰來說一說，你會怎么計算呢？
學生回答。
題目問有幾種湊成24點的方法？怎么樣才能把所有解法都找出來呢？就這需要我們通過算法來獲取所有可能的答案。
3.揭題：
今天這節課我們就一起來學習第三課：算法設計。
二、新知建構
【各種經典算法】
1.說到算法，經典算法有很多種，我們日常生活中就經常會用到。
比如：要在手機聯系人里找到某個人，通常情況下，你會怎么做？
學生回答。
是的，要是查找“王紅”這個人，會先去找他姓“王”的首字母“w”，然后再查找“王紅”這個人。這種方法就是分治法，簡而言之就是分而治之，就是把一個復雜的問題分成兩個或n個相同或相似的子問題，再把子問題分成更小的子問題，直到最后子問題可以簡單的直接求解，原問題的解就是子問題的解的合并。
比如：我們在查英文字典時，要想查找單詞zoo，會先找到字母“z”,再去查找單詞“zoo”,利用首字母分類查找的算法就是分治法。
2.貪心算法
如果從30張面值不等的鈔票中抽出10張，怎樣才能獲得最多的價值？
每次都選擇現下的鈔票中面值最大的，最后拿到的就是最優解。
這種算法就是貪心算法，做出當前的最優選擇。就是通過局部的最優選擇獲得整體的最優選擇。平時生活中找零錢用的就是貪心算法，比如50元錢買了三塊錢的東西，我們一般會找兩個20元的，一個5元的和一個2元的。
3.經典的算法還有很多，比如解析法、枚舉法、動態規劃算法等。經過大量的實踐，人們發現了算法某些共性的規律，總結了經典的算法思想。合理地選擇經典算法思想，可以為具體問題的解決設計出更加精妙的算法。
“雞兔同籠”問題需要在一定范圍內尋找正確解，可以使用枚舉法。
今天我們重點來學習枚舉法。
【認識枚舉法】
1. 在班級名單中查找符合條件的名字，通常我們會怎么做？
是的，從第一個名字開始，一個一個往下找，這種做法就是有序地嘗試每一種可能的解，這也是枚舉法的思想。枚舉法，有個近義詞叫列舉，就是把所有的可能一個一個羅列出來，如果滿足正確解的條件就采納，否則繼續枚舉，做到不遺漏、不重復。
它在生活有著廣泛的應用，如玩24點游戲時在頭腦中羅列各種可能的算式；在一篇文章中摘錄好詞好句；做這樣的數學題等等。
2. 用一串沒有標記的鑰匙打開教室的門，通常你會怎么做？
學生回答。
如果讓計算機通過枚舉法，從一串鑰匙中找到打開教室對應的那一把鑰匙，我們需要告訴計算機什么信息它才能停止查找？
（如果這把鑰匙能打開教室門，就不用再往下嘗試了。）就這是在告訴計算機正確解的判斷條件，不然計算機怎么知道找到怎樣一把鑰匙才可以解決問題呀。
除了這個關鍵，還要告訴計算機有幾把鑰匙，這樣計算機就知道一共需要嘗試幾次了，不然一串鑰匙試完了再試一遍，那就沒完沒了了。就這是在確定枚舉的范圍。
確定枚舉的范圍和正確解的判斷條件是使用枚舉法的關鍵。
3.同學們，你知道怎樣用流程圖來表示枚舉法嗎？
首先需要給定一個范圍，在范圍內進行查找，如果符合條件就把這個數據輸出，否則就繼續往下找，直到找完范圍內所有的數據就結束。
請你試一試，用拖動的方式，將枚舉法的流程圖補充完整。
學生練習。
反饋結果。
4.想一想
我們認識了枚舉法，知道了枚舉法的基本思想和關鍵，那么請你想一想：為什么在登錄網站、APP、ATM自動柜員機時，系統要限制用戶輸入密碼的次數？
學生回答。
是的。為了保護財產安全，防止犯罪分子利用枚舉法的思想破解密碼。
【算法框架的確定】
1.在明確了枚舉算法思想的基礎上，使用具體的計算模型，在合理選擇控制結構，就可以得到解決具體問題的算法框架，最終解決問題，找到答案。
我們繼續上一節的“雞兔同籠”問題，這是上一節課我們最后建立的計算模型。其中ji和tu的取值范圍是0-35，這就是枚舉的范圍；而ji+tu=35；ji×2＋tu×4=94就是正確答案的判斷條件。判斷對錯，那就要用到如果……那么……，這是一種分支結構；枚舉范圍在0-35之間，就要重復嘗試36次，從0開始，直到35結束，這就是循環結構。
2.現在我們跟隨著計算機來一起進行羅列，為了能看得更加清楚，我們用表格來進行羅列，出示表格。
由于ji+tu是35，那么我們選擇其中動物來進行羅列，比如羅列兔子的只數，從0開始，那么雞的只數就是35減去兔子的只數。
課件出示，學生邊回答，邊展示。
【算法的描述】
1. 算法的框架確定好后，我們再用流程圖來描述算法。
描述算法時，要精準地描述算法的每一步驟，明確算法的輸入和輸出。對于大部分算法來說，輸入數據是必要的，但是有的算法不需要輸入數據或者算法本身給定了初始條件。比如雞兔同籠的問題，就可以把tu的值初始化為0，因為是從0開始羅列的。
2.課件呈現“雞兔同籠”問題的算法流程圖。
對照自然語言描述呈現流程圖。
3.除了枚舉兔的數量，還可以枚舉哪些數量呢？
（雞的數量）
其實只要通過雞兔同籠的數據關系，我們知道，只要知道雞的數量，就能計算出其他的數量，所以除了可以枚舉雞的數量，或者兔的數量，雞腳、兔腳的數量都能枚舉，只不過枚舉的范圍和判斷的條件可能會發生相應的變化。
請你試一試，枚舉雞的數量，進行表格的羅列和流程圖的描述。
學生練習。
三、課堂小結
今天我們一起學習了算法設計，了解了一些經典的算法，比如分治法、貪心算法等，重點學習了枚舉算法。
1.枚舉法的思想是 地嘗試 的解。
2.枚舉法的關鍵是① 。
② 。
四、課后練習【機動安排】
利用枚舉法設計百錢買百雞的算法，填寫百錢百雞的表格填寫。
21世紀教育網 www.21cnjy.com 精品試卷·第 2 頁 （共 2 頁）
21世紀教育網(www.21cnjy.com)(共4張PPT)
班級： 學號： 姓名：
雞的只數（ji） ……
兔的只數（tu） ……
總腳數 ……
是否滿足正確解條件 ……
枚舉雞的數量，試著將流程圖框拖動到右邊對應的框中，將流程圖補充完整。
公雞只數（g） 0 0 …… 20
母雞只數（m） 0 1 ……
小雞只數（x） 100-0-0 ……
總價錢 100/3
是否滿足正確解條件 × ……

展開更多......

收起↑