資源簡介

(共16張PPT)
分析問題
分析出已知條件、求解目標和已知與未知的關系。
設計算法
然后推導構建出解析式。
編程調試
最后將數學解析式轉換成程序表達式，進行編程實現并調試。
解析算法
基于解析算法的問題解決
課堂小結
2.4 常見算法的程序實現
1.基于解析算法的問題解決
2.基于枚舉算法的問題解決
體驗探索
雞兔同籠
問題描述 ：一個籠子里面關了雞和兔子（雞有 2 只腳，兔子有 4 只腳，沒有殘疾的），上有35個頭，下有94只足，問籠子里面有多少只雞，有多少只兔子。
解析算法
1）分析問題
已知條件：假設雞有x只,兔子有y只，頭a有35個，足b有94足
求解 ：x,y值
二者之間的關系：x+y=a 2x+4y=b
2）設計算法
解析式x=2a-b//2 y=b//2-a
3）編程測試
a=35
b=94
x=2*a-b//2
y=b//2-a
print("雞有：",x,"只")
print("兔子有：",y,"只")
雞 兔 頭的數量 腳的數量
1 1 1+1=2 1*2+1*4=6
1 2 1+2=3 1*2+2*4=10
1 3 1+3=4 1*2+3*4=14
…… …… …… ……
34 1 34+1=35 34*2+1*4=72
窮舉法（枚舉法）解決雞兔同籠問題
一一列舉可能的解，即枚舉范圍是多少？比如雞是1~34只
逐一檢測可能的解，判定條件是什么？比如頭的數量1+3=4 腳的數量 1*2+1*4=6
1.分析問題
2.設計算法
一一列舉 循環
逐一檢測 分支
開始
雞從1-34序列中依次取數
兔子的數量=35-雞
2*雞+兔子*4==94
輸出雞和兔子的數量
結束
False
False
True
True
for chicken in range(1,35):
for rabbit in range(1,35):
if (chicken+rabbit==35 and 2*chicken+4*rabbit==94):
print("雞有",chicken,"只。")
print("兔子有",rabbit,"只。")
3.編程調試
優化程序
for chicken in range(1,35):
for rabbit in range(1,24):
if (chicken+rabbit==35 and 2*chicken+4*rabbit==94):
print("雞有",chicken,"只。")
print("兔子有",rabbit,"只。")
　　枚舉算法，也稱枚舉法是依據問題的已知條件，確定答案的大致范圍，在此范圍內逐一列舉出它所有可能的情況的方法。在列舉過程中，既不能遺漏，也不能重復，通過逐一判斷，驗證哪些情況滿足問題的條件，從而得到問題的答案。
2.4.2 基于枚舉算法的問題解決
１.基本概念
枚舉算法解題的基本思路：
（1）確定枚舉對象、范圍和判定條件。
（2）逐一枚舉可能的情況并驗證每個情況是否符合條件。
枚舉算法的思想：
一一列舉
逐一檢驗
開始
枚舉值在給定范圍嗎？
取下一個枚舉值
枚舉值符合條件嗎？
輸出該枚舉值
結束
False
False
True
True
循環
分支
問題：票據上有一個4位數字組成的編號，甲說：數字編號的前兩位數字相同，但都不是零；乙說：數字編號的后兩位數字是相同的，但與前兩位不同；丙說：數字編號是一個整數的平方。根據以上線索推斷出編號。
例1 票據中模糊數字推斷問題
假設四個數字應是AABB，其中A≠ 0，A≠B，且AABB是一個整數的二次方。
已知條件
求解目標
二者的關系
票據中的數字。
要求解的4位數字的編號必須同時滿足所有的已知條件。
分析問題
設計算法
根據問題分析，只要一一列舉出4位數字AABB中A與B的所有可以組合，保證A≠B且A ≠0,再驗證二次方問題，就可以得到問題的解。因此，該問題可使用枚舉算法求解完成，其算法的流程圖如右所示：
結束
開始
A=1
A<10
K=1000A+100A+10B+B
C=sqrt(k)的整數部分
A ≠B
c*c=k
輸出票據編號k
B=B+1
B=0
B<10
A=A+1
False
False
False
False
True
True
True
編程實現與調試
import math
A=1
while A<10:
B=0
while B<10:
if A!=B:
k=A*1000+A*100+B*10+B
c=int(math.sqrt(k))
if c*c==k:
print("票據編號是：",k)
B=B+1
A=A+1
保存文件，調試程序
枚舉算法要注意的問題：
題解的可能范圍，不重不漏
考慮優化算法，縮小枚舉范圍，提高解決問題的效率。
尋找1000以內的所有素數
實踐活動
編程求解1000以內的所有素數。素數是在大于1的自然數中，除了1和它本身以外不再有其他因數的數，如2，3，5，7，11，……
1.分析該問題的枚舉范圍和驗證條件。
2.用流程圖描述問題求解的算法，并編程實現。
3.教學資源平臺中提供了本題的兩種不同的算法方案（算法A和算法B）,任選一中自己設計的算法進行對比分析，完成表2.4.1。思考其中哪種算法能更高效地解決問題，為什么？
（詳見P75頁內容或學習單）
練習提升
2.韓信是漢初著名軍事家，傳說他統計士兵數目有個獨特的方法。例如，先令士兵排成5列縱隊，結果余1人；接著，命令士兵排成6列縱隊，結果余5人；再命令士兵排成7列縱隊，結果余4人；最后，命令士兵排成11列縱隊，結果余10人。這樣他便知道士兵的總人數了。這種計數的方法被后人稱為“韓信點兵”。試編寫程序計算士兵的數目。
結合學習單中的程序代碼繪制流程圖
如何避免？
思考兩個問題：
　　1.能不能運用今天所學知識任意破解別人的密碼？
　　2.如何保護自己的密碼安全？
課堂總結
枚舉算法思想在生活中解決問題的適用情況及特點：
　　1.求解的答案數量有限。
　　2.所有的可能情況都符合一定的規則。

展開更多......

收起↑