資源簡介

(共19張PPT)
微項目2
用枚舉算法尋求問題多解
Phthon編程------枚舉算法
學習目標
1.通過對枚舉對象、范圍、條件的構造，體驗枚舉算法解決問題的思想。
2.借助枚舉算法解決問題的思想，尋找解決問題的多種答案組合。（培養計算思維）
把問題的所有可能解都一一列舉出來，并按照問題要求的條件逐個判斷每個答案是否是正確的解，這就是枚舉算法。
在本項目中，我們將借助計算機的高速運算能力，采用枚舉算法通過逐一嘗試，最終得出求解結果。
枚舉就是將問題所有可能的答案一一列舉，然后根據條件判斷各個答案是否合適，保留合適的，丟棄不合適的，做到既不遺漏也不重復。
要使用枚舉算法，首先要確定枚舉對象、枚舉范圍和判定條件。
(1)通過確定枚舉范圍列舉該問題所有可能的解;
(2)應用判定條件，驗證每一個方案是不是問題真正的解。
循環結構
選擇結構
變量
枚舉對象
判定條件
枚舉范圍
枚舉算法
活動一：快速尋找有規律的數據
同學們有沒有玩過一種叫作“拍7”的游戲
假設一起游戲的有33人，請記錄經過3輪報數后拍手的數據。
游戲規則:把從1開始的自然數中含“7”的數稱作“明7”;把不含“7”且是“7”的倍數的數稱作“暗7”。從1開始輪流報數，輪到報“明7”或“暗7”的人，不能出聲，只拍一下手。
1.做游戲
找規律
“拍7” 流程圖
確定枚舉的對象、范圍和條件
枚舉對象
判定條件
枚舉范圍
1~100的的自然數
循環結構
選擇結構
變量
變量i
明7 （含有7）
暗7 （能被7整除）
當數據越來越大，就越難發現“明7和“暗7”，這時，不防使用枚舉算法，借助Phthon程序快速找出想要的結果。
思考：
假如報數到100，
如何確定 枚舉的對象 ？
枚舉范圍 ？
判定條件 ？
2.用程序尋找答案
#!/usr/bin/en python3
n=100
for i in range(1,n+1):
print(i)
枚舉1~100的程序基本結構如下： 使用什么結構？
（1）確定枚舉的對象、 范圍和條件
#!/usr/bin/envpython3
n=100
for i in range(1,n+1):
if "7" in str(i): # 找出所有的 明"7",即含7的數
print("找到明7數字字:",i)
（2）.編寫程序判斷“明7”
#!/usr/bin/env python3
n=100
for i in range(1,n+1):
if "7" in str(i) or i%7==0 :
print("找到的拍手數 數: ",i)
“暗7”： 如何判斷暗7？ 完善程序設計
（3）.增加 “暗7” 的判定條件
請嘗試補全下面程序代碼中缺少的枚舉范圍和判定條件，用枚舉算法尋找遺忘的旅行箱密碼。
for x in range(100, ): #三位密碼的范圍
if and
print(x)
3.用枚舉算法找回忘記的密碼
借助枚舉算法可以嘗試尋找遺忘的記憶。
某人將自己密碼旅行箱的密碼遺忘了。經過討論，有的人認為密碼是生日，有的人認為是電話號碼……各種猜測激活了當事人的記憶，記起當時設置的密碼是一個三位自然數，并且密碼個位數是8，其他位含有1但是不能確定在哪一位置。
3.用枚舉算法找回忘記的密碼
提示信息:
① 通過取余運算%判斷個位數。如x%10==8成立，則可判斷個位數為8。
② 借助邏輯運算符“and”可以判斷復雜情況。
③ 可使用整除運算取得該自然數的前兩位數，利用in判斷前兩位中是否有1。
活動2:一一列舉可行的解決方案
日常生活中，一些問題的解決往往具有多種方案組合，可以用枚舉算法尋找答案。
現有足量的1克、2克、5克、10克砝碼，共允許取用40枚砝碼，現在有100克食鹽，要求每種砝碼至少使用1枚，共有多少種稱量方案
1.分析問題，確定枚舉范圍
枚舉對象可以確定為4種質量的砝碼。每種砝碼至少使用1枚，因此數量都不小于1，以下列出大概取值范圍。
用a表示10克砝碼的枚數，大概取值范圍是1~10。
用b表示5克砝碼的枚數，大概取值范圍是1~20。
用c表示10克砝碼的枚數，大概取值范圍是1~40。
用d表示5克砝碼的枚數，大概取值范圍是1~40。
枚舉的對象、范圍
確定枚舉的對象、范圍和條件
枚舉對象
判定條件
枚舉范圍
確定枚舉的對象、范圍和條件
枚舉對象
判定條件
枚舉范圍
a:1~10
b:1~20
c:1~40
d:1~40
循環結構
選擇結構
變量
變量 a, b,c,d
a+b+c+d=40
10×a+5×b+2×c+d=100
#!/usr/bin/env python3
j=0 #記錄方案數量
for a in range(1,11): #10克砝碼的范圍
for b in range(1,21): #5克砝碼的范圍
for c in range(1,41): #2克砝碼的范圍
for d in range(1,41): #1克砝碼的范圍
if a+b+c+d==40 and 10*a+5*b+2*c+d==100:
print(a,b,c,d)
j+=1
print(j,"種方案")
水仙花數是各位數字的立方之和等于該數本身，如153=1 +5 +3 。請求出所有三位數的水仙花數。
請參考程序進行枚舉實驗，要特別注意體驗通過取整除、取余的方式獲取數位的技巧。
技術實驗: 尋找水仙花數
#!/usr/bin/env python3
#尋找三位數中的水仙花數
for i in range(100,1000):
a =i // 100
b =i // 10% 10
c=i%10
if i == a ** 3 + b ** 3 + c ** 3:
print(i)
課堂小結
1、什么是枚舉算法？枚舉算法的3要素的構成
2、枚舉算法和循環結構的關系？
3、枚舉算法主要適合解決哪類問題？利用了計算機的哪種優勢？

展開更多......

收起↑