資源簡介

(共19張PPT)
4.3 非數值計算
—— 猜數字游戲
教 學
目 標
通過分析問題-設計算法-編程實現-測試運行的解決問題的過程，能夠根據具體問題設計合適的算法形成解決問題的方案。
了解分治算法的優缺點及其在生活中的應用。
通過“猜數字小游戲”,了解分治思想，并運用二分查找解決實際問題。
課 前 復 習
1.random.randint(1,10)的作用是：（ ）
知識點檢測
A.從1-10之間隨機生成一個整數 B.生成1-10之間所有整數
C.從1-9之間隨機生成一個整數 D.生成1-9之間所有整數
A
range(m,n)==>生成[m，n)之間的所有整數。
random 是一個生成隨機數的模塊，randint()是random 的一個函數，用于生成一個隨機整數，使用之前需要導入random （import random）。
random.randint(m,n)=>從[m,n]之間隨機生成一個整數。
猜 數 字 游 戲
運行”猜數字游戲“，嘗試描述游戲功能及實現步驟
如何編寫代碼實現游戲？
1.系統隨機生成一個數字
2.猜數字，猜對則跳出程序，否則繼續猜測，直至5次后跳出，輸出這個數字。
思考：
猜 數 字 游 戲
如何編寫代碼實現游戲？
1.計算機隨機生成一個數
m=random.randint(1,100)
3.輸入要猜的數字
t = int(input("請輸入你猜的數："))
2.要猜幾次？
for i in range(5):
4.比較m與t
若5次之內猜中，跳出循環
否則輸出沒有猜中，游戲結束。
終止循環語句
break
猜 數 字 游 戲
import ① # 導入隨機數模塊
m=random.randint(1,100)
for i in range(5):
t = int(input("請輸入你猜的數："))
if t > m:
print("大了")
② t < m:
print("小了")
else:
print("恭喜你,答對了！")
③
if t!=m:
print("這個數是：",m)
print("5次沒有猜中，游戲結束")
是
否
是
否
是
否
任務一：將程序補充完整
一
分 治 算 法
”猜數字游戲“，如何猜的又快又準
枚 舉 算 法
二 分 查 找
效率低
一
分 治 算 法
二分查找實際上就是分治策略的典型運用
大事化小，小事化了
分 治 算 法
一
分 治 算 法
左邊界low
右邊界high
目標數x
中間數
mid=(low+high)//2
若中間數mid比目標數x大，則區間變為左半區間，右邊界更新為high=mid-1, low不變。
左邊界
low
右邊界
high
目標數x
中間數
Mid
(low+high)//2
若中間數mid比目標數x小，則區間變為右半區間，左邊界更新為low=mid+1, high不變。
一
分 治 算 法
目標數:9
1 2 3 4 5 6 7 8 9 10
low=1
high=10
mid=(1+10)//2=5 <9
6 7 8 9 10
low=mid+1 →6
high=10
mid=8 <9
9 10
low=mid+1→9
high=10
mid=9 =9
第一輪
第二輪
第三輪
最壞的情況需要查找n次滿足: 2n>N(N為查找的總數量)
一
分 治 算 法
再次運行”猜數字游戲”，體驗利用二分查找實現最快的找到數字“
任務二：
一
分 治 算 法
二分法查找最快需要幾步？
x = int(input("請輸入要查找的100以內的整數:"))
step = 0 # 記錄查找次數
low = 1 # 目標區域左邊界
high = 100 # 目標區域右邊界
while(low <= high):
mid = (low+high)//2 # 中間值
step = step+1 # 查找次數加
if mid > x:
high = ① # 右邊界前移
② mid < x:
low = mid+1 # 左邊界后移
else:
break # 找到目標數據，退出循環
print("查找次數為：", ③)
任務三：將程序補充完整。統計二分法查找次數
二分查找的前提：
被查找的數據必須是有序的!
一
分 治 算 法
如何對一組無序的數據如何進行排序呢？
lst=[9，6 ，45，23，48，7]
優點：效率高
缺點：
二
遞 歸 算 法
lst=[9，6 ，45，23，48，7]
9
[6,7]
[45,23,48]
[ ]
[7]
[23,45,48]
[6,7]
[6,7,9,23,45,48]
6
45
[23]
[48]
1.取一個數作為基數：如9
2.將大于基數的數和小于基數的數分成兩個數組：left=[6,7],right=[45,23,48]
3.分別對left和right重復執行1，2，直到列表元素小于等于一個元素為止
4.將left+基數+right 合并
----分
----治
----合
遞 歸 算 法
二
遞 歸 算 法
9
[6,7]
[45,23,48]
[ ]
[7]
[23,45,48]
[6,7]
[6,7,9,23,45,48]
6
45
[23]
[48]
直接或間接地調用自身的方法稱為遞歸。可以將遞歸簡單類比為具有自相似性重復的事物。
遞 歸
二
遞 歸 算 法
遞歸的基本思想是把規模較大的問題層層轉化為規模較小的同類問題求解。可用“分”，“治”，“合”三個字概括
遞歸的基本思想
遞推關系
遞歸的條件
邊界條件
+
len(lst) <= 1
quickSort(left) + lst[0:1] + quickSort(right)
猜 數 字 游 戲
任務四：將程序補充完整，實現遞歸排序
def quickSort(lst):
right=[]
left=[]
if len(lst) ①:
return lst
for i in lst[1:]:
if i >= lst[0]:
right.append(i)
②:
left.append(i)
return quickSort(left) + lst[0:1] + quickSort(right)
lists = [4, 6, 9, 1, 8, 7, 2, 5, 4, 0]
print("排序前: " , lists)
print("排序后: " , ③)
課 堂 小 結
THE END

展開更多......

收起↑